Pareo

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 27 de marzo de 2022; las comprobaciones requieren 2 ediciones .

En la teoría de grafos, un conjunto de aristas coincidentes o independientes en un gráfico es un conjunto de aristas no adyacentes por pares.

Definición

Sea un gráfico G = ( V , E ), un M coincidente en G es un conjunto de aristas no adyacentes por pares, es decir, aristas que no tienen vértices comunes, es decir . $\forall e,f\in M:e\cap f=\emptyset$

Definiciones relacionadas

Una coincidencia máxima es una coincidencia M en un gráfico G que no está contenido en ninguna otra coincidencia de este gráfico, es decir, es imposible agregarle un solo borde que no sea adyacente a todos los bordes de la coincidencia. En otras palabras, una coincidencia M de un gráfico G es máxima si cualquier borde en G tiene una intersección no vacía con al menos un borde de M. A continuación se muestran ejemplos de coincidencias máximas (bordes rojos) en tres gráficos [1] .

La coincidencia más grande (o coincidencia de tamaño máximo [2] ) es la coincidencia que contiene el número máximo de bordes. El número de coincidencia [3] de un gráfico es el número de aristas en la coincidencia más grande. Un gráfico puede tener un conjunto de coincidencias más grandes. Además, cualquier coincidencia más grande es máxima, pero ningún máximo será el más grande. Las siguientes tres figuras muestran las coincidencias más grandes en las mismas tres columnas [1] . $\nu (G)$ $GRAMO$

Algunos autores utilizan el término "coincidencia máxima" para la coincidencia más grande [4] [5] [6] [7] .

Un emparejamiento perfecto (o de 1 factor ) es un emparejamiento en el que participan todos los vértices del gráfico. Es decir, cualquier vértice del gráfico incide exactamente en un borde incluido en la coincidencia. La figura (b) en la figura anterior es un ejemplo de tal coincidencia. Cualquier combinación perfecta es más grande y máxima. Una combinación perfecta es también un recubrimiento de cantos del tamaño mínimo. En el caso general , donde es el número de cubierta de borde del gráfico , en otras palabras, el tamaño de la coincidencia más grande no excede el tamaño de la cubierta de borde más pequeña. $\ nu (G) \ leq \ rho (G)$ $\rho (G)$ $GRAMO$

Un emparejamiento casi perfecto es un emparejamiento en el que no participa exactamente un vértice. Esto puede suceder si el gráfico tiene un número impar de vértices. En la figura anterior, la coincidencia en la columna (c) es casi perfecta. Si para algún vértice de la gráfica hay una coincidencia casi perfecta que no contiene exactamente ese vértice, la gráfica se llama factor crítico .

Sea dada una M coincidente .

un camino alterno es un camino en el que los bordes pertenecen alternativamente a la coincidencia y no pertenecen a ella.
un camino de aumento (o camino de aumento) es un camino alterno que comienza y termina con vértices libres (es decir, que no participa en la coincidencia).

El lema de Berge establece que un emparejamiento es máximo si y solo si no hay un camino complementario.

Propiedades

El número de emparejamientos perfectos en un grafo bipartito es igual al permanente de su matriz de adyacencia .
En cualquier gráfico sin vértices aislados, el número de coincidencias y el número de cobertura de borde suman el número de vértices [8] .
- En particular, si hay una coincidencia perfecta, entonces ambos números son | v | / 2.

Si A y B son dos coincidencias máximas, entonces | un | ≤ 2| segundo | y | segundo | ≤ 2| Un |. Para ver esto, tenga en cuenta que cada borde de B \ A se puede emparejar con dos bordes de A \ B como máximo, ya que A es una coincidencia. Sin embargo, cada arista A \ B es conjugada con la arista B \ A ya que B es máxima. Como consecuencia, $|A\setminus B|\leq 2|B\setminus A|$

A continuación tenemos

|A|=|A\cap B|+|A\setminus B|\leq 2|B\cap A|+2|B\setminus A|=2|B|

En particular, esto implica que cualquier coincidencia máxima es una aproximación de 2 de la coincidencia más grande, así como una aproximación de 2 de la coincidencia máxima mínima. Esta desigualdad es exacta. Por ejemplo, si G es un camino con 3 aristas y 4 vértices, el tamaño mínimo de la coincidencia máxima es 1 y el tamaño de la coincidencia más grande es 2.

Polinomio de correspondencias

La función generadora del número de coincidencias de k -aristas en un gráfico se denomina polinomio coincidente . Sea G un gráfico y m k el número de coincidencias de k aristas. El polinomio coincidente del gráfico G es

\sum _{{k\geq 0}}m_{k}x^{k}

Hay otra definición del polinomio coincidente

\sum _{{k\geq 0}}(-1)^{k}m_{k}x^{{n-2k}}

donde n es el número de vértices en el gráfico. Ambas definiciones tienen sus propias áreas de aplicación.

Algoritmos y complejidad computacional

La coincidencia más grande en un gráfico bipartito

A menudo surgen problemas de correspondencia cuando se trabaja con gráficos bipartitos . Encontrar la coincidencia más grande en un gráfico bipartito [9] es quizás el problema más simple. El algoritmo de ruta de relleno lo obtiene al encontrar la ruta de relleno de cada vértice y agregarla a la coincidencia si se encuentra una ruta . Una solución alternativa es que la coincidencia se complementará siempre que haya caminos complementarios en expansión: $G=(V=(X,Y),E)$ $x\en X$ $Y$

instalar _ $M=\emptyset$
Si bien hay rutas de reabastecimiento en expansión : ${\ estilo de visualización P}$
1. $M=M\o más E(P)$

Una ruta de aumento es una ruta de la forma que es verdadera para . Una ruta de aumento se llama ruta de expansión si . $v_{0},\{v_{0},v_{1}\},v_{1},\{v_{1},v_{2}\},v_{2},\puntos,v_ {l-1},\{v_{l-1},v_{l}\},v_{l}$ $\{v_{i-1},v_{i}\}\in M\Leftrightarrow \{v_{i},v_{i+1}\}\notin M$ $0\leqslant i\leqslant l$ $v_{0},v_{l}\notin M$

Lema: para cualquier gráfico , la coincidencia y la ruta completando la coincidencia y es válida . Demostración: Sea , y el vértice inicial de , por lo que y , y el último vértice de , por lo que y , y un vértice intermedio de , por lo que . De esto se deduce que se agregará una arista más al gráfico de la que se quitará. ${\ estilo de visualización G = (V, E)}$ ${\ estilo de visualización M}$ ${\ estilo de visualización P}$ $M\o más E(P)$ $|M\o más E(P)|=|M|+1$ $G'=(V,M)$ $G''=(V,M\o más E(P))$ $v$ ${\ estilo de visualización P}$ ${\ estilo de visualización \ delta _ {G'} (v) = 0}$ ${\ estilo de visualización \ delta _ {G''} (v) = 1}$ ${\ estilo de visualización w}$ ${\ estilo de visualización P}$ ${\ estilo de visualización \ delta _ {G'} (w) = 0}$ ${\ estilo de visualización \ delta _ {G''} (w) = 1}$ ${\ estilo de visualización u}$ ${\ estilo de visualización P}$ ${\ estilo de visualización \ delta _ {G'} (u) = \ delta _ {G''} (u) = 1}$

Lema: para cualquier grafo y coincidencias tales que lo siguiente sea cierto: el grafo contiene un mínimo de caminos de finalización que no se cruzan en los vértices con respecto a . Demostración: Sea and , mientras que realmente and and sigue . Sea para las componentes conexas del gráfico . De sigue ${\ estilo de visualización G = (V, E)}$ ${\ estilo de visualización M}$ ${\ estilo de visualización N}$ ${\ estilo de visualización |M|<|N|}$ $H=(V,M\oplus N)$ ${\ estilo de visualización | N | - | M |}$ ${\ estilo de visualización M}$ $GRAMO$ $G_{M}=(V,M)$ ${\ estilo de visualización G_ {N} = (V, N)}$ ${\ estilo de visualización \ delta (G_{M}) \ subconjunto \ {0,1 \}}$ ${\ estilo de visualización \ delta (G_{N}) \ subconjunto \ {0,1 \}}$ ${\ estilo de visualización \ delta (H) \ subconjunto \ {0,1,2 \}}$ $G_{i}=(V,E_{i})$ $1\leqslant i\leqslant g$ ${\ estilo de visualización H}$ ${\ estilo de visualización \ delta (H) \ subconjunto \ {0,1,2 \}}$

${\ Displaystyle G_ {i}}$ es un vértice aislado o
${\ Displaystyle G_ {i}}$ es un ciclo de longitud uniforme, o
${\ Displaystyle G_ {i}}$ es un camino de longitud uniforme, o
${\ Displaystyle G_ {i}}$ es un camino de longitud impar

Los vértices en provienen alternativamente de y . Dejar ${\ Displaystyle G_ {i}}$ ${\ estilo de visualización M}$ ${\ estilo de visualización N}$ ${\displaystyle d(G_{i})=|E_{i}\cap N|-|E_{i}\cap M|\subconjunto \{-1,0,1\))$

, pero solo si es un camino de aumento. y esto significa que debe haber un mínimo de componentes con y, en consecuencia, caminos complementarios. De acuerdo con la definición de componentes conexas, tales caminos complementarios no se intersecarán en los vértices. ${\ estilo de visualización d (G_ {i}) = 1}$ ${\ Displaystyle G_ {i}}$ $\sum _{i=1}^{g}d(G_{i})=|N\setminus M|-|M\setminus N|=|N|-|M|$ ${\ estilo de visualización | N | - | M |}$ ${\ Displaystyle G_ {i}}$ ${\ estilo de visualización d (G_ {i}) = 1}$

Puedes encontrar la ruta complementaria así:

Dado un gráfico bipartito y un . ${\ Displaystyle G = (V, W, E)}$ ${\ estilo de visualización M}$
Crear donde $G'=(V\taza W,E'\taza E'')$
1. ${\displaystyle E'=\{(v,w)\mid \{v,w\}\in E\setminus M\land v\in V\land w\in W\))$
2. ${\displaystyle E''=\{(w,v)\mid \{v,w\}\in M\land v\in V\land w\in W\))$
La búsqueda de un camino complementario se reduce a buscar de vértice libre a vértice libre . ${\ estilo de visualización G'}$ ${\ estilo de visualización v \ en V}$ ${\ estilo de visualización w \ en W}$

Dado que la ruta de aumento se puede encontrar en tiempo DFS, el tiempo de ejecución del algoritmo es . Esta solución es equivalente a agregar una superfuente con aristas en todos los vértices y una superreserva con aristas en todos los vértices (la transformación del gráfico tomará , y encontrar el flujo máximo desde hasta . de la coincidencia más grande será igual a El algoritmo basado en el Hopcrofttiempo - Karp es algo más rápido . el algoritmo es más lento [11] $O(|E|)$ ${\ estilo de visualización O (| V || E |)}$ $s$ $X$ $t$ $Y$ $O(n+m)$ $s$ $t$ $X$ $Y$ $O({\raíz cuadrada {V}}E)$ $O(V^{{2.376}})$

En un gráfico bipartito ponderado

En un gráfico bipartito ponderado , a cada borde se le asigna un peso. Un emparejamiento de peso máximo en un gráfico bipartito [9] se define como un emparejamiento para el cual la suma de los pesos de los bordes del emparejamiento tiene un valor máximo. Si el gráfico no es un bipartito completo , los bordes que faltan se agregan con peso cero. El problema de encontrar tal correspondencia se conoce como problema de asignación . El notable algoritmo húngaro resuelve el problema de asignación y fue uno de los primeros algoritmos de optimización combinatoria . El problema se puede resolver utilizando una búsqueda de ruta más corta modificada en el algoritmo de ruta aumentada. Si se utiliza el algoritmo Bellman-Ford , el tiempo de ejecución será , o el precio de la ventaja se puede desplazar para alcanzar el tiempo cuando se aplica el algoritmo de Dijkstra con un montón de Fibonacci [12] . [13] $O(V^{2}E)$ $O(V^{2}\log {V}+VE)$

Mayores coincidencias

Existe un algoritmo de tiempo polinomial para encontrar la coincidencia más grande o la coincidencia de peso máximo en un gráfico no bipartito. Siguiendo a Jack Edmonds , se llama el método de ruta, árbol y color o simplemente el algoritmo de coincidencia de Edmonds . El algoritmo usa arcos bidireccionales . Se puede utilizar una generalización de la misma técnica para encontrar el máximo conjunto independiente en grafos sin garras . El algoritmo de Edmods se mejoró posteriormente a tiempo de ejecución , que corresponde a algoritmos para gráficos bipartitos [14] . Otro algoritmo (aleatorizado) desarrollado por Mucha y Sankovsim (Mucha, Sankowski) [10] , basado en el producto rápido de matrices , da complejidad . $O(\raíz cuadrada{V}E)$ $O(V^{{2.376}})$

Coincidencias máximas

La coincidencia máxima se puede encontrar con un algoritmo codicioso simple . La coincidencia máxima más grande es la coincidencia más grande que se puede encontrar en tiempo polinomial. Implementación usando pseudocódigo:

Cuenta dada . $G=(V,E)$
instalar _ $M=\emptyset$
Siempre que el conjunto no esté vacío: $mi$
1. Elige _ ${\ estilo de visualización e \ en E}$
2. instalar _ $M=M\taza \{e\}$
3. instalar _ ${\displaystyle E=\{e'\in E\mid e'\cap e=\emptyset \))$
sacar _ $METRO$

Sin embargo, no se conoce ningún algoritmo de tiempo polinomial que encuentre la coincidencia máxima más pequeña , es decir, la coincidencia máxima que contiene el menor número posible de aristas.

Tenga en cuenta que la coincidencia más grande de k aristas es un conjunto dominante de aristas con k aristas. Por el contrario, dado un conjunto mínimo dominante de aristas con k aristas, podemos construir la coincidencia más grande con k aristas en tiempo polinomial. Por lo tanto, el problema de encontrar el tamaño mínimo de la coincidencia máxima es equivalente al problema de encontrar el conjunto dominante de borde mínimo [15] . Ambos problemas de optimización se conocen como NP-hard , y sus versiones de reconocimiento son ejemplos clásicos de problemas NP-completos [16] . Ambos problemas se pueden aproximar por un factor de 2 con el tiempo polinomial: solo encuentre un M máximo arbitrario que coincida [17] .

Tareas de enumeración

El número de coincidencias en un gráfico se conoce como índice Hosoyya . Calcular este número es #P-completo . El problema sigue siendo #P-completo en el caso especial de enumerar coincidencias perfectas en un gráfico bipartito , ya que calcular el permanente de una matriz aleatoria 0-1 (otro problema #P-completo) es lo mismo que calcular el número de coincidencias perfectas en un gráfico bipartito con una matriz dada como matriz de adyacencia . Sin embargo, existe un esquema de aproximación de tiempo polinomial aleatorio para calcular el número de coincidencias en un gráfico bipartito [18] . Un maravilloso teorema de Casteleyn que establece que el número de coincidencias perfectas en un gráfico plano se puede calcular exactamente en tiempo polinomial utilizando el algoritmo FKT .

¡¡ El número de coincidencias perfectas en un gráfico completo K n (con n par ) viene dado por el factorial doble ( n − 1)!! [19] . El número de coincidencias en un gráfico completo sin límite, para que la coincidencia sea perfecta, viene dado por los números de teléfono [20] .

Encontrar todos los bordes, combinar los bordes

Uno de los principales problemas en la teoría de coincidencias es encontrar todas las aristas que puedan extenderse a la coincidencia más grande. El mejor algoritmo determinista para resolver este problema se ejecuta en el tiempo [21] . Existe un algoritmo aleatorio que resuelve el problema en el tiempo [22] . En el caso de un gráfico bipartito, puede encontrar la coincidencia más grande y usarla para encontrar todos los bordes de coincidencia máxima en tiempo lineal [23] ; que resultará para grafos bipartitos generales y para grafos bipartitos densos con . Si se conoce de antemano una de las coincidencias más grandes [24] , el tiempo total de ejecución del algoritmo será . $O(VE)$ ${\tilde {O}}(V^{{2.376}})$ $O(V^{{1/2}}E)$ $O((V/\log V)^{{1/2}}E)$ $E=\Theta (V^{2})$ $O(V+E)$

Características y observaciones

El teorema de König establece que en grafos bipartitos, el tamaño de la coincidencia más grande es igual al tamaño de la cubierta de vértice más pequeña . De esto se deduce que para grafos bipartitos, los problemas de encontrar la cobertura de vértice más pequeña , el conjunto independiente más grande y el bilique de vértice máximo se pueden resolver en tiempo polinomial .

El teorema de Hall (o teorema de la boda) proporciona una caracterización de gráficos bipartitos que tienen coincidencias perfectas, mientras que el teorema de Tutt proporciona una caracterización de gráficos arbitrarios.

Una coincidencia perfecta genera un subgrafo regular de 1 que se expande, es decir, un factor de 1 . En general, un subgrafo regular k generador es un factor k .

Aplicaciones

La fórmula estructural de Kekule de los compuestos aromáticos consiste en la combinación perfecta de su esqueleto de carbono , lo que muestra la ubicación de los dobles enlaces en la estructura química . Estas estructuras llevan el nombre de Friedrich August Kekule , quien demostró que el benceno (en términos de teoría de grafos, es un ciclo de 6 vértices) puede representarse como tal estructura [25] .

El índice de Hosoyya es el número de emparejamientos no vacíos más uno. Se utiliza en química computacional y matemática para estudiar compuestos orgánicos.

Véase también

borde para colorear
Conjunto Independiente
Descomposición de Dalmage-Mendelsohn
Coincidencia estable
Coincidencia óptima
Gráfico sesgado simétrico
Glosario de términos de teoría de grafos

Notas

↑ 1 2 Stanislav Okulov. Matemáticas discretas. Teoría y práctica de la resolución de problemas en informática. Guía de estudio . — Litros, 2014-02-07. - S. 186. - 428 pág. — ISBN 9785457534674 .
↑ Alan Gibbons, Algorithmic Graph Theory, Cambridge University Press, 1985, Capítulo 5.
↑ Evstigneev V. A., Kasyanov V. N. Poset serie-paralelo // Diccionario de gráficos en informática / Editado por el prof. Viktor Nikolaevich Kasyanov. - Novosibirsk: LLC "Siberian Scientific Publishing House", 2009. - V. 17. - (Diseño y optimización de programas). - ISBN 978-591124-036-3 .
↑ Fuad Aleskerov, Ella Khabina, Dmitry Schwartz. Relaciones binarias, gráficas y decisiones colectivas . — Litros, 2016-01-28. - T. 22. - 343 pág. — ISBN 9785457966925 .
↑ Rubchinsky A. A. Modelos matemáticos discretos. Conceptos Iniciales y Problemas Estándar . — Directmedia, 2014-08-06. - S. 136. - 269 pág. — ISBN 9785445838029 .
↑ Leonid Gladkov, Vladimir Kureichik, Viktor Kureichik. Algoritmos genéticos . — Litros, 2016-01-28. - S. 276. - 367 pág. — ISBN 9785457965997 .
↑ Leonid Gladkov, Vladimir Kureichik, Viktor Kureichik, Pavel Sorokoletov. Métodos bioinspirados en optimización . — Litros, 2016-01-28. - S. 330. - 381 pág. — ISBN 9785457967472 .
↑ Tibor Gallai. Über extreme Punkt- und Kantenmengen // Ann. Universidad ciencia budapest Secta Eötvös. Matemáticas.. - 1959. - Vol . 2 . — págs. 133–138 .
↑ 1 2 Douglas Brent Oeste. Introducción a la Teoría de Grafos. — 2do. - Prentice Hall, 1999. - ISBN 0-13-014400-2 .
↑ 1 2 M. Mucha, P. Sankowski. Coincidencias máximas mediante eliminación gaussiana // Proc. 45º Simposio IEEE. Fundamentos de la Informática . - 2004. - S. 248-255 .
↑ Bala G. Chandran, Dorit S. Hochbaum. Mejoras prácticas y teóricas para el emparejamiento bipartito utilizando el algoritmo de pseudoflujo . - 2011. - arXiv : 1105.1569 . .
↑ M. Fredman, R. Tarjan. Montones de Fibonacci y sus usos en algoritmos de optimización de red mejorados // Journal of the ACM . - 1987. - T. 34 , núm. 3 . — S. 596–615 .
↑ Rainer Burkard, Mauro Dell'Amico, Silvano Martello. Problemas de asignación . - Filadelfia: SIAM, Society for Industrial and Applied Mathematics, 2009. - pp 77-79 , 98. capítulo 4.1.3 Notas históricas, libros y encuestas, capítulo 4.4.3 Implementaciones eficientes
↑ Silvio Micali, Vijay Vazirani. Un algoritmo para encontrar la coincidencia máxima en gráficos generales // Proc. 21º Simposio IEEE. Fundamentos de la Informática . - 1980. - S. 17-27 . -doi : 10.1109/ SFCS.1980.12 . $\scriptstyle O({\sqrt {|V|}}\cdot |E|)$
↑ Yannakakis Mihalis, Gavril Fanica. Conjuntos que dominan los bordes en gráficos // SIAM Journal on Applied Mathematics. - 1980. - T. 38 , núm. 3 . — S. 364–372 . -doi : 10.1137/ 0138030 .
↑ Michael R. Garey, David S. Johnson. Computadoras e intratabilidad: una guía para la teoría de la integridad NP . - WH Freeman, 1979. - ISBN 0-7167-1045-5 . . El conjunto dominante de aristas se analiza en el caso de los problemas de conjuntos dominantes, Problema GT2 en el Apéndice A1.1. La coincidencia máxima de tamaño mínimo es el problema GT10 en el Apéndice A1.1.
↑ Giorgio Ausiello, Pierluigi Crescenzi, Giorgio Gambosi, Viggo Kann, Alberto Marchetti-Spaccamela, Marco Protasi. Complejidad y Aproximación: Problemas de Optimización Combinatoria y sus Propiedades de Aproximabilidad. — Springer, 2003. El conjunto mínimo de aristas dominantes es un problema de GT3 en el Apéndice B (página 370). La coincidencia máxima de tamaño mínimo es la tarea GT10 en el Apéndice B (página 374). Consulte también Conjunto dominante de borde mínimo Archivado el 5 de septiembre de 2013 en Wayback Machine y Coincidencia máxima mínima Archivado el 6 de marzo de 2014 en Wayback Machine en el compendio web Archivado el 2 de octubre de 2013 en Wayback Machine .
↑ Ivona Bezáková, Daniel Štefankovič, Vijay V. Vazirani, Eric Vigoda. Aceleración del recocido simulado para los problemas de conteo combinatorios y permanentes // SIAM Journal on Computing . - 2008. - T. 37 , núm. 5 . - S. 1429-1454 . -doi : 10.1137/ 050644033 .
↑ David Callan. Un estudio combinatorio de identidades para el doble factorial . - 2009. - arXiv : 0906.1317 .
↑ Problemas extremos para índices topológicos en química combinatoria // Journal of Computational Biology . - 2005. - T. 12 , núm. 7 . — S. 1004–1013 . -doi : 10.1089/ cmb.2005.12.1004 .
↑ Marcelo H. de Carvalho, Joseph Cheriyan. Un algoritmo para descomposiciones de oído de gráficos cubiertos por coincidencia // Proc. Simposio ACM/SIAM sobre Algoritmos Discretos (SODA). - 2005. - S. 415-423 . $O(VE)$
↑ Michael O. Rabin, Vijay V. Vazirani. Coincidencias máximas en gráficas generales mediante aleatorización // J. de Algoritmos. - 1989. - T. 10 . — S. 557–567 .
↑ Tamir Tassa. Encontrar todos los bordes con coincidencia máxima en un gráfico bipartito // Ciencias de la computación teórica . - 2012. - T. 423 . — S. 50–58 . -doi : 10.1016/ j.tcs.2011.12.071 .
↑ Aris Gionis, Arnon Mazza, Tamir Tassa. k -Revisión de la anonimización // Conferencia Internacional sobre Ingeniería de Datos (ICDE) . - 2008. - S. 744-753 .
↑ Véase, por ejemplo, Nenad Trinajstić, Douglas J. Klein, Milan Randić. Sobre algunos problemas resueltos y no resueltos de teoría química de grafos . - 1986. - T. 30 , núm. S20 . — S. 699–742 . -doi : 10.1002/ qua.560300762 .

Lectura para leer más

László Lovász, Michael D. Plummer. Teoría del emparejamiento. - Holanda Septentrional, 1986. - ISBN 0-444-87916-1 .
Introducción a los Algoritmos. - segundo. - MIT Press y McGraw-Hill, 2001. - ISBN 0-262-53196-8 .

SJ Cyvin, Iván Gutman. Estructuras de Kekule en Hidrocarburos Bencenoides. — Springer-Verlag, 1988.
Marek Karpinski, Wojciech Rytter. Algoritmos paralelos rápidos para problemas de correspondencia de gráficos . - Oxford University Press, 1998. - ISBN 978-0-19-850162-6 .

Enlaces

Un ejemplo de cómo resolver un problema en YouTube . Archivado el 22 de marzo de 2016 en Wayback Machine .
Un algoritmo para encontrar la coincidencia más grande en un gráfico bipartito . Archivado el 7 de enero de 2012 en Wayback Machine .
Una biblioteca de gráficos con implementación de coincidencia de cardinalidad máxima basada en Hopcroft-Karp y Push-Relabel. Archivado el 25 de octubre de 2005 en Wayback Machine .