Necesito un algoritmo para encontrar en un grafo bipartito un emparejamiento que sature todos los vértices de grado máximo. ¿Cómo puedo encontrar dicho algoritmo?
Respuestas
¿Demasiados anuncios?
decibyte
Puntos
59
Por lo que tengo entendido, lo que has descrito es el problema de encontrar la coincidencia b perfecta. Quizá quieras buscarlo en Google. No existe una página de wikipedia para este problema, pero sí alguna literatura de investigación. Echa un vistazo a esta página personal: www.cs.umd.edu/~bert. Este tipo estaba haciendo esto un poco.
La parte no trivial de esta cuestión consiste en demostrar la existencia de dicho emparejamiento. Sea $G$ sea un grafo bipartito $G$ con grado máximo $\Delta$ y que $S$ sea el conjunto de vértices de grado $\Delta$ . Crear un bipartito $\Delta$ - regular gráfico $G'$ de $G$ añadiendo aristas "ficticias" (y también vértices ficticios, si es necesario, para equilibrar el grafo). La afirmación clave es que todas las aristas de $G'$ que inciden en $S$ son aristas no ficticias y no es difícil ver por qué (¡Ejercicio!).
Por el teorema de Hall para grafos bipartitos regulares, $H$ tiene una correspondencia perfecta, digamos $M'$ . Ahora, basta con eliminar las aristas ficticias de $M'$ para obtener el $M$ . De la afirmación clave anterior se deduce que $M$ es efectivamente una coincidencia en $G$ y satura todo $S$ .
En cuanto al algoritmo, el único paso no trivial en la prueba anterior es encontrar una coincidencia perfecta en un grafo regular. Se trata de un problema de optimización estándar, con una serie de bonitos algoritmos; véase la página de wikipedia para más detalles.
