lunes, enero 16

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.



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




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?



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.



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.



¿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: 

Fuentes y más información: 

3 comentarios:

  1. profe alex excelente blog es de mucha utilidad...quisiera hacerle una consulta y que me ayudara con un tema de algortimos de grafos.....le hablo desde colombia....en realidad necesito ejercicios resueltos de esta tematica ya que estoy realizando un objeto de aprendizaje para una materia llamada estructura de datos ...mi correo es unorio2@hotmail.com yo se que este no es el medio pero no se como conseguir su correo....le agradeceria enormemente su ayuda en lo que sea posible desde COLOMBIA un estudiante mas.....gracias

    ResponderEliminar
  2. buenas tardes, queria consultarle si me podria otorgar algunos ejemplos sobre la aplicacion de la Teoria de grafos en el uso del matlab, Gzuck-7@hotmail.com

    ResponderEliminar
    Respuestas
    1. disculpe no se si me pueden ayudar con ejemplos de la teoria de grafos aplicados en matlab gracias....mi correo es giovanny.pedroza.a@gmail.com

      Eliminar

¿Buscas algún tema que no encuentras en el blog?, avísame para incluirlo.