Gráfica bipartita

Gráfico dividido en dos conjuntos independientes.

Ejemplo de gráfico bipartito sin ciclos

Un gráfico bipartito completo con m = 5 y n = 3

El gráfico de Heawood es bipartito.

En el campo matemático de la teoría de grafos , un grafo bipartito (o bigrafo ) es un grafo cuyos vértices se pueden dividir en dos conjuntos disjuntos e independientes y , es decir, cada arista conecta un vértice en con otro en . Conjuntos de vértices y generalmente se denominan partes del gráfico. De manera equivalente, un gráfico bipartito es un gráfico que no contiene ciclos de longitud impar . ^{[1] [2]} ${\displaystyle U}$ ${\displaystyle V}$ ${\displaystyle U}$ ${\displaystyle V}$ ${\displaystyle U}$ ${\displaystyle V}$

Los dos conjuntos y pueden considerarse como una coloración del gráfico con dos colores: si se colorean todos los nodos en azul y todos los nodos en rojo, cada borde tiene puntos finales de diferentes colores, como se requiere en el problema de coloración del gráfico. ^{[3] [4]} Por el contrario, tal coloración es imposible en el caso de un gráfico no bipartito, como un triángulo : después de que un nodo se colorea de azul y otro de rojo, el tercer vértice del triángulo se conecta a los vértices de ambos colores, impidiendo que se le asigne cualquiera de los colores. ${\displaystyle U}$ ${\displaystyle V}$ ${\displaystyle U}$ ${\displaystyle V}$

A menudo se escribe para denotar un gráfico bipartito cuya partición tiene las partes y , denotando los bordes del gráfico. Si un grafo bipartito no es conexo , puede tener más de una bipartición; ^[5] en este caso, la notación es útil para especificar una bipartición particular que puede ser importante en una aplicación. Si , es decir, si los dos subconjuntos tienen igual cardinalidad , entonces se llama gráfico bipartito equilibrado . ^[3] Si todos los vértices del mismo lado de la bipartición tienen el mismo grado , entonces se llama biregular . ${\displaystyle G=(U,V,E)}$ ${\displaystyle U}$ ${\displaystyle V}$ ${\displaystyle E}$ ${\displaystyle (U,V,E)}$ ${\displaystyle |U|=|V|}$ ${\displaystyle G}$ ${\displaystyle G}$

Ejemplos

Al modelar relaciones entre dos clases diferentes de objetos, los gráficos bipartitos suelen surgir de forma natural. Por ejemplo, un gráfico de jugadores y clubes de fútbol, ​​con una ventaja entre un jugador y un club si el jugador ha jugado para ese club, es un ejemplo natural de red de afiliación , un tipo de gráfico bipartito utilizado en el análisis de redes sociales . ^[6]

Otro ejemplo donde los gráficos bipartitos aparecen naturalmente es en el problema de optimización ferroviaria ( NP-completo ), en el que la entrada es un horario de trenes y sus paradas, y el objetivo es encontrar un conjunto de estaciones de tren lo más pequeño posible, de modo que cada El tren visita al menos una de las estaciones elegidas. Este problema se puede modelar como un problema de conjunto dominante en un gráfico bipartito que tiene un vértice para cada tren y cada estación y una arista para cada par de estaciones y un tren que para en esa estación. ^[7]

Un tercer ejemplo está en el campo académico de la numismática. Las monedas antiguas se elaboran utilizando dos impresiones positivas del diseño (el anverso y el reverso). Los gráficos que producen los numismáticos para representar la producción de monedas son gráficos bipartitos. ^[8]

Ejemplos más abstractos incluyen los siguientes:

• Cada árbol es bipartito. ^[4]
• Los gráficos de ciclos con un número par de vértices son bipartitos. ^[4]
• Todo gráfico plano cuyas caras tengan longitud par es bipartito. ^[9] Casos especiales de esto son los gráficos de cuadrícula y los gráficos cuadrados , en los que cada cara interior consta de 4 aristas y cada vértice interior tiene cuatro o más vecinos. ^[10]
• El gráfico bipartito completo en m y n vértices, denotado por K _{n, m} es el gráfico bipartito , donde U y V son conjuntos disjuntos de tamaño m y n , respectivamente , y E conecta cada vértice en U con todos los vértices en V. Se deduce que K _m,n tiene mn aristas. ^[11] Estrechamente relacionados con los gráficos bipartitos completos están los gráficos de corona , formados a partir de gráficos bipartitos completos eliminando los bordes de una coincidencia perfecta . ^[12] ${\displaystyle G=(U,V,E)}$
• Las gráficas de hipercubo , los cubos parciales y las gráficas de mediana son bipartitas. En estos gráficos, los vértices pueden estar etiquetados mediante vectores de bits , de tal manera que dos vértices sean adyacentes si y sólo si los vectores de bits correspondientes difieren en una sola posición. Se puede formar una bipartición separando los vértices cuyos vectores de bits tienen un número par de unos de los vértices con un número impar de unos. Los árboles y los gráficos cuadrados forman ejemplos de gráficos de mediana, y cada gráfico de mediana es un cubo parcial. ^[13]

Propiedades

Caracterización

Los gráficos bipartitos se pueden caracterizar de varias maneras diferentes:

• Un grafo no dirigido es bipartito si y sólo si no contiene un ciclo impar . ^{[14] [15]}
• Un gráfico es bipartito si y sólo si tiene dos colores (es decir, su número cromático es menor o igual a 2). ^[3]
• Un gráfico es bipartito si y sólo si cada arista pertenece a un número impar de enlaces , subconjuntos mínimos de aristas cuya eliminación aumenta el número de componentes del gráfico. ^[dieciséis]
• Un gráfico es bipartito si y sólo si el espectro del gráfico es simétrico. ^[17]

Teorema de Kőnig y gráficas perfectas

En gráficos bipartitos, el tamaño de la cobertura mínima de vértices es igual al tamaño de la coincidencia máxima ; este es el teorema de Kőnig . ^{[18] [19]} Una forma alternativa y equivalente de este teorema es que el tamaño del conjunto independiente máximo más el tamaño de la coincidencia máxima es igual al número de vértices. En cualquier gráfico sin vértices aislados, el tamaño de la cobertura mínima del borde más el tamaño de una coincidencia máxima es igual al número de vértices. ^[20] La combinación de esta igualdad con el teorema de Kőnig conduce al hecho de que, en gráficos bipartitos, el tamaño de la cobertura de borde mínima es igual al tamaño del conjunto independiente máximo, y el tamaño de la cobertura de borde mínima más el tamaño del La cobertura mínima de vértices es igual al número de vértices.

Otra clase de resultados relacionados se refiere a los gráficos perfectos : cada gráfico bipartito, el complemento de cada gráfico bipartito, el gráfico lineal de cada gráfico bipartito y el complemento del gráfico lineal de cada gráfico bipartito, son todos perfectos. La perfección de los gráficos bipartitos es fácil de ver (su número cromático es dos y su tamaño máximo de camarilla también es dos), pero la perfección de los complementos de los gráficos bipartitos es menos trivial y es otra reformulación del teorema de Kőnig. Este fue uno de los resultados que motivó la definición inicial de gráficas perfectas. ^[21] La perfección de los complementos de las gráficas lineales de gráficas perfectas es otra reformulación del teorema de Kőnig, y la perfección de las gráficas lineales mismas es una reformulación de un teorema anterior de Kőnig, que cada gráfica bipartita tiene una coloración de bordes usando un número de colores iguales a su grado máximo.

Según el teorema fuerte del grafo perfecto , los grafos perfectos tienen una caracterización de grafo prohibido que se asemeja a la de los grafos bipartitos: un grafo es bipartito si y solo si no tiene un ciclo impar como subgrafo, y un grafo es perfecto si y solo si tiene sin ciclo impar o su complemento como subgrafo inducido . Las gráficas bipartitas, las gráficas lineales de las gráficas bipartitas y sus complementos forman cuatro de las cinco clases básicas de gráficas perfectas utilizadas en la prueba del teorema de las gráficas perfectas fuertes. ^[22]

Grado

Para un vértice, el número de vértices adyacentes se llama grado del vértice y se denota . La fórmula de suma de grados para un gráfico bipartito establece que ^[23] ${\displaystyle \deg(v)}$

${\displaystyle \sum _{v\in V}\deg(v)=\sum _{u\in U}\deg(u)=|E|\,.}$

La secuencia de grados de un gráfico bipartito es el par de listas, cada una de las cuales contiene los grados de las dos partes y . Por ejemplo, el gráfico bipartito completo K _3,5 tiene secuencia de grados . Los gráficos bipartitos isomórficos tienen la misma secuencia de grados. Sin embargo, la secuencia de grados no identifica, en general, de forma única un gráfico bipartito; en algunos casos, los gráficos bipartitos no isomorfos pueden tener la misma secuencia de grados. ${\displaystyle U}$ ${\displaystyle V}$ ${\displaystyle (5,5,5),(3,3,3,3,3)}$

El problema de realización bipartita es el problema de encontrar un gráfico bipartito simple cuya secuencia de grados sea dos listas dadas de números naturales. (Los ceros finales pueden ignorarse ya que se obtienen trivialmente agregando un número apropiado de vértices aislados al dígrafo).

Relación con hipergrafías y gráficas dirigidas.

La matriz de biaadyacencia de un gráfico bipartito es una matriz de tamaño (0,1) que tiene un uno para cada par de vértices adyacentes y un cero para los vértices no adyacentes. ^[24] Las matrices de biaadyacencia se pueden utilizar para describir equivalencias entre gráficos bipartitos, hipergráficos y gráficos dirigidos. ${\displaystyle (U,V,E)}$ ${\displaystyle |U|\times |V|}$

Un hipergrafo es una estructura combinatoria que, como un grafo no dirigido, tiene vértices y aristas, pero en la que las aristas pueden ser conjuntos arbitrarios de vértices en lugar de tener que tener exactamente dos puntos finales. Se puede usar un gráfico bipartito para modelar un hipergrafo en el que U es el conjunto de vértices del hipergrafo, V es el conjunto de hiperaristas y E contiene un borde desde un vértice del hipergrafo v hasta un borde del hipergrafo e exactamente cuando v es uno de los puntos finales de e . Bajo esta correspondencia, las matrices de biadyacencia de gráficos bipartitos son exactamente las matrices de incidencia de los hipergráficos correspondientes. Como caso especial de esta correspondencia entre grafos bipartitos e hipergrafos, cualquier multigrafo (un grafo en el que puede haber dos o más aristas entre los mismos dos vértices) puede interpretarse como un hipergrafo en el que algunos hipergrafos tienen conjuntos iguales de puntos finales, y representado por un gráfico bipartito que no tiene múltiples adyacencias y en el que todos los vértices de un lado de la bipartición tienen grado dos. ^[25] ${\displaystyle (U,V,E)}$

Se puede utilizar una reinterpretación similar de las matrices de adyacencia para mostrar una correspondencia uno a uno entre gráficos dirigidos (en un número dado de vértices etiquetados, lo que permite bucles automáticos) y gráficos bipartitos equilibrados, con el mismo número de vértices en ambos lados de la bipartición. Porque, la matriz de adyacencia de un gráfico dirigido con n vértices puede ser cualquier matriz (0,1) de tamaño , que luego puede reinterpretarse como la matriz de adyacencia de un gráfico bipartito con n vértices a cada lado de su bipartición. ^[26] En esta construcción, el grafo bipartito es la doble cobertura bipartita del grafo dirigido. ${\displaystyle n\times n}$

Algoritmos

Probando el bipartidismo

Es posible probar si un gráfico es bipartito y devolver un ciclo de dos colores (si es bipartito) o un ciclo impar (si no lo es) en tiempo lineal , utilizando la búsqueda en profundidad . La idea principal es asignar a cada vértice el color que difiere del color de su padre en el bosque de búsqueda en profundidad, asignando colores en un recorrido de preorden del bosque de búsqueda en profundidad. Esto necesariamente proporcionará una doble coloración del bosque que se extiende y que consta de los bordes que conectan los vértices con sus padres, pero es posible que no coloree adecuadamente algunos de los bordes que no son bosques. En un bosque de búsqueda en profundidad, uno de los dos puntos finales de cada borde que no es bosque es un ancestro del otro punto final, y cuando la búsqueda en profundidad descubre un borde de este tipo, debe verificar que estos dos vértices tengan colores diferentes. Si no es así, entonces el camino en el bosque desde el ancestro al descendiente, junto con el borde mal coloreado, forman un ciclo impar, que el algoritmo devuelve junto con el resultado de que el gráfico no es bipartito. Sin embargo, si el algoritmo termina sin detectar un ciclo impar de este tipo, entonces cada borde debe colorearse adecuadamente y el algoritmo devuelve el color junto con el resultado de que el gráfico es bipartito. ^[27]

Alternativamente, se puede utilizar un procedimiento similar con búsqueda primero en amplitud en lugar de búsqueda primero en profundidad. Nuevamente, a cada nodo se le asigna el color opuesto a su padre en el bosque de búsqueda, en orden de amplitud. Si, cuando se colorea un vértice, existe un borde que lo conecta a un vértice previamente coloreado con el mismo color, entonces este borde junto con los caminos en el bosque de búsqueda en anchura que conectan sus dos puntos finales con su ancestro común más bajo forma un ciclo extraño. Si el algoritmo termina sin encontrar un ciclo impar de esta manera, entonces debe haber encontrado una coloración adecuada y puede concluir con seguridad que el gráfico es bipartito. ^[28]

Para los gráficos de intersección de segmentos de línea u otras formas simples en el plano euclidiano , es posible probar si el gráfico es bipartito y devolver un ciclo de dos colores o un ciclo impar en el tiempo , aunque el gráfico en sí pueda tener hasta aristas . . ^[29] ${\displaystyle n}$ ${\displaystyle O(n\log n)}$ ${\displaystyle O\left(n^{2}\right)}$

Ciclo impar transversal

Un gráfico con una transversal de ciclo impar de tamaño 2: al eliminar los dos vértices inferiores azules se obtiene un gráfico bipartito.

La transversal de ciclo impar es un problema algorítmico NP-completo que pregunta, dado un gráfico G = ( V , E ) y un número k , si existe un conjunto de  k vértices cuya eliminación de G causaría que el gráfico resultante sea bipartito. ^[30] El problema es manejable con parámetros fijos , lo que significa que existe un algoritmo cuyo tiempo de ejecución puede estar limitado por una función polinómica del tamaño del gráfico multiplicado por una función mayor de k . ^[31] El nombre transversal de ciclo impar proviene del hecho de que un grafo es bipartito si y sólo si no tiene ciclos impares . Por lo tanto, para eliminar vértices de un gráfico a fin de obtener un gráfico bipartito, es necesario "acertar con todos los ciclos impares", o encontrar el llamado conjunto transversal de ciclo impar . En la ilustración, cada ciclo impar en el gráfico contiene los vértices azules (los más bajos), por lo que eliminar esos vértices elimina todos los ciclos impares y deja un gráfico bipartito.

El problema de bipartición de aristas es el problema algorítmico de eliminar la menor cantidad de aristas posible para hacer que un gráfico sea bipartito y también es un problema importante en la algorítmica de modificación de gráficos. Este problema también es manejable con parámetros fijos y se puede resolver en el tiempo , ^[32] donde k es el número de aristas a eliminar y m es el número de aristas en el gráfico de entrada. ${\textstyle O\left(2^{k}m^{2}\right)}$

Pareo

Una coincidencia en un gráfico es un subconjunto de sus aristas, de las cuales no hay dos que compartan un punto final. Los algoritmos de tiempo polinomial son conocidos por muchos problemas algorítmicos de coincidencias, incluida la coincidencia máxima (encontrar una coincidencia que utilice tantas aristas como sea posible), la coincidencia de peso máximo y el matrimonio estable . ^[33] En muchos casos, los problemas de coincidencia son más sencillos de resolver en gráficos bipartitos que en gráficos no bipartitos, ^[34] y muchos algoritmos de coincidencia, como el algoritmo Hopcroft-Karp para una coincidencia de cardinalidad máxima ^[35], funcionan correctamente solo en entradas bipartitas. .

Como ejemplo simple, supongamos que un conjunto de personas buscan trabajo entre un conjunto de trabajos, y no todas las personas son adecuadas para todos los trabajos. Esta situación se puede modelar como un gráfico bipartito donde una ventaja conecta a cada solicitante de empleo con cada trabajo adecuado. ^[36] Una combinación perfecta describe una forma de satisfacer simultáneamente a todos los solicitantes de empleo y cubrir todos los puestos de trabajo; El teorema del matrimonio de Hall proporciona una caracterización de las gráficas bipartitas que permiten coincidencias perfectas. El Programa Nacional de Coincidencia de Residentes aplica métodos de comparación de gráficos para resolver este problema para estudiantes de medicina de EE. UU. que buscan empleo y trabajos de residencia hospitalaria . ^[37] ${\displaystyle P}$ ${\displaystyle J}$ ${\displaystyle (P,J,E)}$

La descomposición de Dulmage-Mendelsohn es una descomposición estructural de gráficos bipartitos que es útil para encontrar coincidencias máximas. ^[38]

Aplicaciones adicionales

Los gráficos bipartitos se utilizan ampliamente en la teoría de codificación moderna , especialmente para decodificar palabras clave recibidas del canal. Los gráficos de factores y los gráficos de Tanner son ejemplos de esto. Un gráfico de Tanner es un gráfico bipartito en el que los vértices de un lado de la bipartición representan dígitos de una palabra de código y los vértices del otro lado representan combinaciones de dígitos que se espera que sumen cero en una palabra de código sin errores. ^[39] Un gráfico de factores es una red de creencias estrechamente relacionada que se utiliza para la decodificación probabilística de códigos LDPC y turbo . ^[40]

En informática, una red de Petri es una herramienta de modelado matemático utilizada en análisis y simulaciones de sistemas concurrentes. Un sistema se modela como un gráfico dirigido bipartito con dos conjuntos de nodos: un conjunto de nodos de "lugar" que contienen recursos y un conjunto de nodos de "evento" que generan y/o consumen recursos. Existen restricciones adicionales en los nodos y bordes que limitan el comportamiento del sistema. Las redes de Petri utilizan las propiedades de los gráficos dirigidos bipartitos y otras propiedades para permitir pruebas matemáticas del comportamiento de los sistemas y al mismo tiempo permiten una fácil implementación de simulaciones del sistema. ^[41]

En geometría proyectiva , los gráficos de Levi son una forma de gráfico bipartito utilizado para modelar las incidencias entre puntos y líneas en una configuración . Correspondiente a la propiedad geométrica de los puntos y rectas de que cada dos rectas se encuentran como máximo en un punto y cada dos puntos están conectados con una sola recta, las gráficas de Levi no necesariamente contienen ciclos de longitud cuatro, por lo que su circunferencia debe ser seis o más. . ^[42]

Ver también

• Dimensión bipartita , el número mínimo de gráficos bipartitos completos cuya unión es el gráfico dado
• Doble cobertura bipartita , una forma de transformar cualquier grafo en un grafo bipartito duplicando sus vértices
• Hipergrafo bipartito , una generalización del bipartitismo a los hipergrafos .
• Matroide bipartita , una clase de matroides que incluye las matroides gráficas de gráficos bipartitos
• Proyección de red bipartita , una técnica de ponderación para comprimir información sobre redes bipartitas
• Gráfico bipartito convexo , un gráfico bipartito cuyos vértices se pueden ordenar de modo que las vecindades de los vértices sean contiguas
• Gráfico multipartito , una generalización de gráficos bipartitos a más de dos subconjuntos de vértices
• Gráfico de paridad , una generalización de los gráficos bipartitos en los que cada dos caminos inducidos entre los mismos dos puntos tienen la misma paridad
• Gráfico cuasi-bipartito , un tipo de instancia de problema de árbol de Steiner en el que los terminales forman un conjunto independiente, lo que permite algoritmos de aproximación que generalizan los de gráficos bipartitos.
• Gráfico dividido , un gráfico en el que los vértices se pueden dividir en dos subconjuntos, uno de los cuales es independiente y el otro es una camarilla.
• Problema de Zarankiewicz sobre el número máximo de aristas en un gráfico bipartito con subgrafos prohibidos

Referencias

1. Diestel, Reinard (2005), Teoría de grafos, Textos de posgrado en matemáticas , Springer, ISBN 978-3-642-14278-9, archivado desde el original el 9 de abril de 2011 , consultado el 27 de febrero de 2012
2. Asratian, Armen S.; Denley, Tristán MJ; Häggkvist, Roland (1998), Gráficos bipartitos y sus aplicaciones , Cambridge Tracts in Mathematics, vol. 131, Prensa de la Universidad de Cambridge, ISBN 9780521593458.
3. Asratian, Denley y Häggkvist (1998), pág. 7.
4. Scheinerman, Edward R. (2012), Matemáticas: una introducción discreta (3.ª ed.), Cengage Learning, p. 363, ISBN 9780840049421.
5. Chartrand, Gary ; Zhang, Ping (2008), Teoría de grafos cromáticos, matemáticas discretas y sus aplicaciones, vol. 53, Prensa CRC, pág. 223, ISBN 9781584888000.
6. Wasserman, Stanley ; Faust, Katherine (1994), Análisis de redes sociales: métodos y aplicaciones, Análisis estructural en las ciencias sociales, vol. 8, Cambridge University Press, págs. 299–302, ISBN 9780521387071.
7. Niedermeier, Rolf (2006), Invitación a algoritmos de parámetros fijos , Serie de conferencias de Oxford sobre matemáticas y sus aplicaciones, Oxford University Press, págs. 20-21, ISBN 978-0-19-856607-6
8. Bracey, Robert (2012), "Sobre la interpretación gráfica de las monedas del año 3 de Herodes", en Jacobson, David M.; Kokkinos, Nikos (eds.), Judea y Roma en monedas 65 a. C. - 135 d. C.: artículos presentados en la conferencia internacional organizada por Spink, 13 y 14 de septiembre de 2010 , Spink & Son , págs.
9. Soifer, Alexander (2008), El libro de colorear matemático , Springer-Verlag, págs. 136-137, ISBN 978-0-387-74640-1. A este resultado se le ha llamado a veces el "teorema de los dos colores"; Soifer lo atribuye a un famoso artículo de 1879 de Alfred Kempe que contiene una prueba falsa del teorema de los cuatro colores .
10. Bandelt, H.-J.; Chepoi, V.; Eppstein, D. (2010), "Combinatoria y geometría de gráficos cuadrados finitos e infinitos", Revista SIAM de Matemáticas Discretas , 24 (4): 1399–1440, arXiv : 0905.4537 , doi : 10.1137/090760301, S2CID  10788524.
11. Asratian, Denley y Häggkvist (1998), pág. 11.
12. Archidiácono, D .; Debowsky, M.; Dinitz, J .; Gavlas, H. (2004), "Sistemas cíclicos en el gráfico bipartito completo menos un factor", Matemáticas discretas , 284 (1–3): 37–43, doi :10.1016/j.disc.2003.11.021.
13. Ovchinnikov, Sergei (2011), Gráficos y cubos , Universitext, Springer. Véase especialmente el Capítulo 5, "Cubos parciales", págs. 127-181.
14. Asratian, Denley y Häggkvist (1998), Teorema 2.1.3, p. 8. Asratian et al. Atribuya esta caracterización a un artículo de 1916 de Dénes Kőnig . Para gráficas infinitas, este resultado requiere el axioma de elección .
15. Bang-Jensen, Jørgen; Gutin, Gregory (2001), Digraphs: teoría, algoritmos y aplicaciones (PDF) (1ª ed.), p. 25, ISBN 9781852332686, archivado (PDF) desde el original el 2023-01-02 , recuperado el 2023-01-02
16. Woodall, DR (1990), "Una prueba de la caracterización bipartita euleriana de McKee", Matemáticas discretas , 84 (2): 217–220, doi :10.1016/0012-365X(90)90380-Z, MR  1071664
17. Biggs, Norman (1994), Teoría de grafos algebraicos, Biblioteca Matemática de Cambridge (2ª ed.), Cambridge University Press, p. 53, ISBN 9780521458979.
18. Kőnig, Dénes (1931), "Gráfok és mátrixok", Matematikai és Fizikai Lapok , 38 : 116-119.
19. Bruto, Jonathan L.; Yellen, Jay (2005), Teoría de grafos y sus aplicaciones, Matemáticas discretas y sus aplicaciones (2ª ed.), CRC Press, p. 568, ISBN 9781584885054.
20. Chartrand, Gary ; Zhang, Ping (2012), Un primer curso de teoría de grafos, Publicaciones Courier Dover, págs. 189-190, ISBN 9780486483689.
21. Béla Bollobás (1998), Teoría de grafos moderna, Textos de posgrado en matemáticas, vol. 184, Springer, pág. 165, ISBN 9780387984889.
22. Chudnovsky, María ; Robertson, Neil ; Seymour, Pablo ; Thomas, Robin (2006), "El teorema del grafo perfecto fuerte", Annals of Mathematics , 164 (1): 51–229, arXiv : math/0212070 , CiteSeerX 10.1.1.111.7265 , doi :10.4007/annals.2006.164.51 , S2CID  119151552 .
23. Lovász, László (2014), Problemas y ejercicios combinatorios (2ª ed.), Elsevier, p. 281, ISBN 9780080933092
24. Asratian, Denley y Häggkvist (1998), pág. 17.
25. AA Sapozhenko (2001) [1994], "Hypergraph", Enciclopedia de Matemáticas , EMS Press
26. Brualdi, Richard A.; Harary, Frank ; Miller, Zevi (1980), "Bigrafos versus dígrafos mediante matrices", Journal of Graph Theory , 4 (1): 51–73, doi :10.1002/jgt.3190040107, MR  0558453. Brualdi et al. atribuya la idea de esta equivalencia a Dulmage, AL; Mendelsohn, NS (1958), "Coberturas de gráficos bipartitos", Canadian Journal of Mathematics , 10 : 517–534, doi : 10.4153/CJM-1958-052-0 , MR  0097069, S2CID  123363425.
27. Sedgewick, Robert (2004), Algoritmos en Java, Parte 5: Algoritmos gráficos (3.ª ed.), Addison Wesley, págs..
28. Kleinberg, Jon ; Tardos, Éva (2006), Diseño de algoritmos , Addison Wesley, págs. 94–97.
29. Eppstein, David (2009), "Prueba de bipartición de gráficos de intersección geométrica", Transacciones ACM sobre algoritmos , 5 (2): art. 15, arXiv : cs.CG/0307023 , doi : 10.1145/1497290.1497291, SEÑOR  2561751, S2CID  60496.
30. Yannakakis, Mihalis (1978), "Problemas NP completos de eliminación de nodos y bordes", Actas del décimo simposio ACM sobre teoría de la computación (STOC '78) , págs. 253-264, doi : 10.1145/800133.804355 , S2CID  363248
31. Caña, Bruce ; Smith, Kaleigh; Vetta, Adrian (2004), "Encontrar ciclos transversales impares", Operations Research Letters , 32 (4): 299–301, CiteSeerX 10.1.1.112.6357 , doi :10.1016/j.orl.2003.10.009, MR  2057781 .
32. Guo, Jiong; abuela, Jens; Huffner, Falk; Niedermeier, Rolf; Wernicke, Sebastian (2006), "Algoritmos de parámetros fijos basados ​​en compresión para conjunto de vértices de retroalimentación y bipartición de bordes", Journal of Computer and System Sciences , 72 (8): 1386–1396, doi : 10.1016/j.jcss.2006.02. 001
33. Ahuja, Ravindra K.; Magnanti, Thomas L.; Orlin, James B. (1993), "12. Asignaciones y coincidencias", Flujos de red: teoría, algoritmos y aplicaciones , Prentice Hall, págs..
34. Ahuja, Magnanti y Orlin (1993), pág. 463: "Los problemas de coincidencia no bipartitos son más difíciles de resolver porque no se reducen a problemas de flujo de red estándar".
35. Hopcroft, John E .; Karp, Richard M. (1973), "Un algoritmo n ^5/2 para coincidencias máximas en gráficos bipartitos", SIAM Journal on Computing , 2 (4): 225–231, doi :10.1137/0202019.
36. Ahuja, Magnanti y Orlin (1993), Solicitud 12.1 Asignación bipartita de personal, págs.
37. Robinson, Sara (abril de 2003), "¿Están los estudiantes de medicina encontrando su (mejor opción)?" (PDF) , SIAM News (3): 36, archivado desde el original (PDF) el 18 de noviembre de 2016 , consultado el 27 de agosto de 2012.
38. Dulmage y Mendelsohn (1958).
39. Moon, Todd K. (2005), Codificación de corrección de errores: métodos y algoritmos matemáticos, John Wiley & Sons, p. 638, ISBN 9780471648000.
40. Luna (2005), pág. 686.
41. Casandras, Christos G.; Lafortune, Stéphane (2007), Introducción a los sistemas de eventos discretos (2ª ed.), Springer, p. 224, ISBN 9780387333328.
42. Grünbaum, Branko (2009), Configuraciones de puntos y rectas, Estudios de Posgrado en Matemáticas , vol. 103, Sociedad Matemática Estadounidense , pág. 28, ISBN 9780821843086.

enlaces externos

• "Gráfico bipartito", Enciclopedia de Matemáticas , EMS Press , 2001 [1994]
• Sistema de Información sobre Clases de Grafos y sus Inclusiones: grafo bipartito
• Weisstein, Eric W. , "Gráfico bipartito", MathWorld
• Gráficos bipartitos en biología y medicina de sistemas.