Teoria de Grafos y Ejercicios Resueltos (II)

Conexión en Grafos No Dirigidos

Definición de grafo Conexo. Teoremas sobre conexión. Clases de equivalencia. Componentes conexas.

Árboles.

Definición de Árbol.Caracterización. Propiedades. Árbol generador de mínimo coste. Grafos ponderados. Algoritmo de Kruskal.

Árboles Dirigidos con Raíz.

Grafo subyacente.

Problema de la Asignación y su Relación con Teoría de Grafos.

Problema 01: Se tiene que elegir a cuatro miembros de la unidad de docentes de Matemáticas del FI para formar parte de las comisiones siguientes: Comisión de Proyectos, Comisión Docente, Comisión Permanente, Comisión de Planes de estudio. La mencionada unidad está formada por siete profesores, que mantienen su posibilidad para pertenecer a una u otra. ¿Cuál sería una posible asignación que respete las posibilidades del profesorado?

Problema 02: En el grupo PL1 de prácticas de laboratorio de la asignatura EMI2 se van a hacer prácticas por parejas, por lo que se solicita a los 16 alumnos que, previo acuerdo entre ellos, indiquen con quienes les gustaría formar pareja. ¿Será posible establecer 8 parejas para las prácticas que respeten las preferencias de los alumnos?

Los Emparejamientos en la Teoría de Grafos.

Definiciones. Ejemplos. Tipos de emparejamientos. Vértices M-saturado, M-insaturados.

Perfeccionar un Emparejamiento en la Teoría de Grafos.

¿Qué es perfeccionar un emparejamiento?. Caminos M-alternados. Proceso de perfeccionamiento.

Resultados sobre Emparejamientos en la Teoría de Grafos.

Teorema del matrimonio. Algoritmo Húngaro. Algoritmo de Edmods(I). Algoritmo Kuhn-Munkres

Algoritmo para Emparejamientos Máximos de Peso Máximo.

Problema de los ciclistas. Aplicación del Algoritmo Kuhn-Munkres, uso de una aplicación en Java.

Algoritmos de Emparejamientos Máximos de peso máximo en Grafos Bipartidos.

Algoritmo Kuhn-Munkres. Algoritmos de Edmonds(II).

Ejemplo: Se tiene que formar un equipo de futbol, se tiene cinco jugadores españoles y tres extranjeros, y hay cinco puestos para cubrir. No puede jugar más de un jugador no español. Se tiene ademas la información de los puestos que pueden jugar los jugadores y su rendimiento.

Recubrimiento en la Teoría de Grafos.

¿Qués un recubrimiento?. Relación entre recubrimiento y emparejamiento. Aplicación. Recubrimiento trivial. ¿Que relación hay entre recubrimiento y emparejamiento?. Teorema de Koning.

Aplicación: En la Feria de Muestras, cuyo plano se reproduce abajo, se van a instalar cámaras de vigilancia en los cruces de los pasillos. Cada cámara cubrirá todos los pasillos que concurren en el cruce donde se sitúe. ¿Cuántas cámaras colocarías, y en dónde, de manera que se minimicen los costes de instalación y todo el recinto quede vigilado?

Relacionado: 

Teoria de Grafos y Ejercicios Resueltos (I)

Fuentes y más información: 

http://www.youtube.com/user/valenciaupv/