Gráfico bipartito

Ejemplo de un gráfico bipartito sin ciclos

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 uno en . Los conjuntos de vértices y se denominan generalmente partes del grafo. De manera equivalente, un grafo bipartito es un grafo que no contiene ningún ciclo de longitud impar . ^[1]^[2] ${\estilo de visualización U}$ ${\estilo de visualización V}$ ${\estilo de visualización U}$ ${\estilo de visualización V}$ ${\estilo de visualización U}$ ${\estilo de visualización V}$

Los dos conjuntos pueden considerarse como una coloración del gráfico con dos colores: si uno colorea 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, lo que evita que se le asigne cualquiera de los colores. ${\estilo de visualización U}$ ${\estilo de visualización V}$ ${\estilo de visualización U}$ ${\estilo de visualización V}$

A menudo se escribe para denotar un grafo bipartito cuya partición tiene las partes y , con denotando los bordes del grafo. Si un grafo bipartito no está conectado , 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 de importancia en una aplicación. Si , es decir, si los dos subconjuntos tienen la misma cardinalidad , entonces se llama grafo bipartito equilibrado . ^[3] Si todos los vértices en el mismo lado de la bipartición tienen el mismo grado , entonces se llama biregular . $G=(U,V,E)$ ${\estilo de visualización U}$ ${\estilo de visualización V}$ ${\estilo de visualización E}$ ${\estilo de visualización (U,V,E)}$ $|U|=|V|$ ${\estilo de visualización G}$ ${\estilo de visualización G}$

Ejemplos

Al modelar las relaciones entre dos clases diferentes de objetos, muy a menudo surgen de forma natural los grafos bipartitos. Por ejemplo, un grafo de jugadores de fútbol y clubes, con una arista entre un jugador y un club si el jugador ha jugado para ese club, es un ejemplo natural de una red de afiliación , un tipo de grafo bipartito utilizado en el análisis de redes sociales . ^[6]

Otro ejemplo en el que los grafos bipartitos aparecen de forma natural es en el problema de optimización ferroviaria ( NP-completo ), en el que la entrada es un cronograma 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 tren pase por al menos una de las estaciones elegidas. Este problema se puede modelar como un problema de conjunto dominante en un grafo bipartito que tiene un vértice para cada tren y cada estación y una arista para cada par de una estación y un tren que se detiene en esa estación. ^[7]

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

Ejemplos más abstractos incluyen los siguientes:

Todo árbol es bipartito. ^[4]
Los gráficos de ciclo con un número par de vértices son bipartitos. ^[4]
Todo grafo plano cuyas caras tienen todas una longitud par es bipartito. ^[9] Casos especiales de esto son los grafos de cuadrícula y los grafos cuadrados , en los que cada cara interna consta de 4 aristas y cada vértice interno tiene cuatro o más vecinos. ^[10]
El grafo bipartito completo en m y n vértices, denotado por K _n,m es el grafo 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 . De ello se deduce que K _m,n tiene mn aristas. ^[11] Estrechamente relacionados con los grafos bipartitos completos están los grafos corona , formados a partir de grafos bipartitos completos eliminando las aristas de un grafo de coincidencia perfecta . ^[12] $G=(U,V,E)$
Los grafos hipercubicos , los cubos parciales y los grafos medianos son bipartitos. En estos grafos, los vértices pueden etiquetarse mediante vectores de bits , de tal manera que dos vértices son adyacentes si y solo 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 grafos cuadrados forman ejemplos de grafos medianos, y cada grafo mediano es un cubo parcial. ^[13]

Propiedades

Caracterización

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

Un gráfico no dirigido es bipartito si y sólo si no contiene un ciclo impar . ^[14]^[15]
Un grafo es bipartito si y sólo si es 2-coloreable (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. ^[16]
Un gráfico es bipartito si y sólo si el espectro del gráfico es simétrico. ^[17]

Teorema de König y grafos perfectos

En grafos 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 grafo sin vértices aislados, el tamaño de la cobertura mínima de aristas 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 a los hechos de que, en grafos bipartitos, el tamaño de la cobertura mínima de aristas es igual al tamaño del conjunto independiente máximo, y el tamaño de la cobertura mínima de aristas más el tamaño de la cobertura mínima de vértices es igual al número de vértices.

Otra clase de resultados relacionados concierne a los grafos perfectos : cada grafo bipartito, el complemento de cada grafo bipartito, el grafo lineal de cada grafo bipartito y el complemento del grafo lineal de cada grafo bipartito son todos perfectos. La perfección de los grafos bipartitos es fácil de ver (su número cromático es dos y su tamaño máximo de grupo también es dos), pero la perfección de los complementos de los grafos 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 grafos perfectos. ^[21] La perfección de los complementos de los grafos lineales de los grafos perfectos es otra reformulación del teorema de Kőnig, y la perfección de los grafos lineales en sí mismos es una reformulación de un teorema anterior de Kőnig, que dice que cada grafo bipartito tiene una coloración de aristas que utiliza un número de colores igual a su grado máximo.

Según el teorema fuerte del grafo perfecto , los grafos perfectos tienen una caracterización de grafo prohibido similar 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 no tiene un ciclo impar o su complemento como subgrafo inducido . Los grafos bipartitos, los grafos lineales de grafos bipartitos y sus complementos forman cuatro de las cinco clases básicas de grafos perfectos utilizados en la prueba del teorema fuerte del grafo perfecto. ^[22] De ello se deduce que cualquier subgrafo de un grafo bipartito también es bipartito porque no puede ganar un ciclo impar. ^[23]

Grado

Para un vértice, la cantidad de vértices adyacentes se denomina grado del vértice y se denota por . La fórmula de suma de grados para un gráfico bipartito establece que ^[24] $\deg v$

\suma _{v\en V}\deg v=\suma _{u\en U}\deg u=|E|\,.

La secuencia de grados de un grafo bipartito es el par de listas que contienen cada una los grados de las dos partes y . Por ejemplo, el grafo bipartito completo K _3,5 tiene una secuencia de grados . Los grafos bipartitos isomorfos tienen la misma secuencia de grados. Sin embargo, la secuencia de grados, en general, no identifica de forma única a un grafo bipartito; en algunos casos, los grafos bipartitos no isomorfos pueden tener la misma secuencia de grados. ${\estilo de visualización U}$ ${\estilo de visualización V}$ $(5,5,5),(3,3,3,3,3)$

El problema de realización bipartita es el problema de encontrar un grafo bipartito simple cuya secuencia de grados sean dos listas dadas de números naturales. (Los ceros finales pueden ignorarse ya que se realizan de manera trivial agregando una cantidad apropiada de vértices aislados al dígrafo).

Relación con hipergrafos y grafos dirigidos

La matriz de biadyacencia 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. ^[25] Las matrices de biadyacencia se pueden utilizar para describir equivalencias entre gráficos bipartitos, hipergráficos y gráficos dirigidos. ${\estilo de visualización (U,V,E)}$ $|U|\times |V|$

Un hipergrafo es una estructura combinatoria que, al igual que 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. Un grafo bipartito se puede utilizar 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 una arista desde un vértice del hipergrafo $v$ hasta una arista del hipergrafo $e$ exactamente cuando $v$ es uno de los puntos finales de $e$ . Según esta correspondencia, las matrices de biyacencia de los grafos bipartitos son exactamente las matrices de incidencia de los hipergrafos 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 algunas hiperaristas tienen conjuntos iguales de puntos finales, y representarse mediante un grafo bipartito que no tiene múltiples adyacencias y en el que los vértices de un lado de la bipartición tienen todos grado dos. ^[26] ${\estilo de visualización (U,V,E)}$

Una reinterpretación similar de las matrices de adyacencia puede utilizarse para mostrar una correspondencia uno a uno entre grafos dirigidos (en un número dado de vértices etiquetados, permitiendo bucles propios) y grafos bipartitos balanceados, con el mismo número de vértices en ambos lados de la bipartición. Para ello, la matriz de adyacencia de un grafo 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 grafo bipartito con $n$ vértices en cada lado de su bipartición. ^[27] En esta construcción, el grafo bipartito es la doble cubierta bipartita del grafo dirigido. $n\veces n$

Algoritmos

Poniendo a prueba el bipartidismo

Es posible probar si un grafo es bipartito, y devolver un coloreado doble (si es bipartito) o un ciclo impar (si no lo es) en tiempo lineal , utilizando una 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 proporcionará necesariamente un coloreado doble del bosque de expansión que consiste en los bordes que conectan los vértices con sus padres, pero puede que no coloree correctamente algunos de los bordes que no son del bosque. En un bosque de búsqueda en profundidad, uno de los dos puntos finales de cada borde que no es del 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 lo hacen, entonces el camino en el bosque desde el ancestro hasta el descendiente, junto con el borde mal coloreado, forman un ciclo impar, que es devuelto por el algoritmo 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 estar coloreado correctamente y el algoritmo devuelve la coloración junto con el resultado de que el gráfico es bipartito. ^[28]

Como alternativa, se puede utilizar un procedimiento similar con una búsqueda en amplitud en lugar de una búsqueda 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 una arista que lo conecta con un vértice previamente coloreado con el mismo color, entonces esta arista junto con las rutas en el bosque de búsqueda en amplitud que conectan sus dos puntos finales con su ancestro común más bajo forman un ciclo impar. 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 grafo es bipartito. ^[29]

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 impar en el tiempo , incluso aunque el gráfico en sí pueda tener hasta aristas. ^[30] ${\estilo de visualización n}$ $O(n\log n)$ $O\left(n^{2}\right)$

Ciclo impar transversal

El ciclo impar transversal es un problema algorítmico NP-completo que pregunta, dado un grafo 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 grafo resultante fuera bipartito. ^[31] El problema es manejable con parámetros fijos , lo que significa que hay un algoritmo cuyo tiempo de ejecución puede estar acotado por una función polinómica del tamaño del grafo multiplicado por una función mayor de k . ^[32] El nombre transversal de ciclo impar proviene del hecho de que un grafo es bipartito si y solo si no tiene ciclos impares. Por lo tanto, para eliminar vértices de un grafo para obtener un grafo bipartito, uno necesita "llegar a todos los ciclos impares", o encontrar un llamado conjunto transversal de ciclo impar . En la ilustración, cada ciclo impar en el grafo contiene los vértices azules (los de más abajo), por lo que eliminar esos vértices mata todos los ciclos impares y deja un grafo bipartito.

El problema de bipartición de aristas es el problema algorítmico de eliminar la menor cantidad posible de aristas para hacer que un grafo sea bipartito y también es un problema importante en los algoritmos de modificación de grafos. Este problema también es manejable con parámetros fijos y se puede resolver en el tiempo ^[33] , donde k es la cantidad de aristas a eliminar y m es la cantidad de aristas en el grafo de entrada. ${\textstyle O\izquierda(2^{k}m^{2}\derecha)}$

Pareo

Un emparejamiento en un grafo es un subconjunto de sus aristas, de las cuales ninguna comparte un punto final. Los algoritmos de tiempo polinomial son conocidos para muchos problemas algorítmicos sobre emparejamientos, incluyendo el emparejamiento máximo (encontrar un emparejamiento que use tantas aristas como sea posible), el emparejamiento de peso máximo y el matrimonio estable . ^[34] En muchos casos, los problemas de emparejamiento son más simples de resolver en grafos bipartitos que en grafos no bipartitos, ^[35] y muchos algoritmos de emparejamiento como el algoritmo Hopcroft–Karp para el emparejamiento de cardinalidad máxima ^[36] funcionan correctamente solo en entradas bipartitas.

Como ejemplo simple, supongamos que un conjunto de personas están buscando empleos entre un conjunto de empleos, y que no todas las personas son aptas para todos los empleos. Esta situación se puede modelar como un gráfico bipartito donde una arista conecta a cada solicitante de empleo con cada empleo adecuado. ^[37] Una correspondencia perfecta describe una forma de satisfacer simultáneamente a todos los solicitantes de empleo y cubrir todos los empleos; el teorema del matrimonio de Hall proporciona una caracterización de los gráficos bipartitos que permiten correspondencias perfectas. El Programa Nacional de Correspondencia de Residentes aplica métodos de correspondencia de grafos para resolver este problema para los solicitantes de empleo de estudiantes de medicina de Estados Unidos y los empleos de residencia hospitalaria . ^[38] ${\estilo de visualización P}$ ${\estilo de visualización J}$ ${\estilo de visualización (P,J,E)}$

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

Aplicaciones adicionales

Los gráficos bipartitos se utilizan ampliamente en la teoría de codificación moderna , especialmente para decodificar palabras de código recibidas del canal. Los gráficos factoriales 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. ^[40] Un gráfico factorial es una red de creencias estrechamente relacionada que se utiliza para la decodificación probabilística de códigos LDPC y turbo . ^[41]

En informática, una red de Petri es una herramienta de modelado matemático que se utiliza en el análisis y la simulación 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 o consumen recursos. Existen restricciones adicionales en los nodos y los 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. ^[42]

En geometría proyectiva , los grafos de Levi son una forma de grafo bipartito que se utiliza para modelar las incidencias entre puntos y líneas en una configuración . En correspondencia con la propiedad geométrica de los puntos y las líneas de que cada dos líneas se encuentran en como máximo un punto y cada dos puntos pueden estar conectados con una sola línea, los grafos de Levi no contienen necesariamente ningún ciclo de longitud cuatro, por lo que su circunferencia debe ser seis o más. ^[43]

Véase también

Dimensión bipartita , el número mínimo de gráficos bipartitos completos cuya unión es el gráfico dado
Cobertura doble bipartita , una forma de transformar cualquier gráfico en un gráfico bipartito duplicando sus vértices
Hipergrafo bipartito , una generalización de la bipartididad a los hipergrafos .
Matroide bipartito , una clase de matroides que incluye los matroides gráficos de grafos bipartitos
Proyección de red bipartita , una técnica de ponderación para comprimir información sobre redes bipartitas
Grafo bipartito convexo , un grafico bipartito cuyos vértices se pueden ordenar de manera que los vecindarios de los vértices sean contiguos.
Gráfico multipartito , una generalización de los 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 aquellos para 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 grafo bipartito con subgrafos prohibidos

Referencias

^ 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
^ Asratian, Armen S.; Denley, Tristan MJ; Häggkvist, Roland (1998), Gráficos bipartitos y sus aplicaciones , Cambridge Tracts in Mathematics, vol. 131, Cambridge University Press, ISBN 9780521593458.
^ abc Asratian, Denley y Häggkvist (1998), pág. 7.
^ abc Scheinerman, Edward R. (2012), Matemáticas: una introducción discreta (3.ª ed.), Cengage Learning, pág. 363, ISBN 9780840049421.
^ Chartrand, Gary ; Zhang, Ping (2008), Teoría de grafos cromáticos, Matemáticas discretas y sus aplicaciones, vol. 53, CRC Press, pág. 223, ISBN 9781584888000.
^ 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.
^ Niedermeier, Rolf (2006), Invitación a los algoritmos de parámetros fijos , Oxford Lecture Series in Mathematics and Its Applications, Oxford University Press, págs. 20-21, ISBN 978-0-19-856607-6
^ 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 del 65 a. C. al 135 d. C.: trabajos presentados en la Conferencia Internacional organizada por Spink, 13 y 14 de septiembre de 2010 , Spink & Son , págs. 65-84
^ Soifer, Alexander (2008), El libro para colorear matemático , Springer-Verlag, págs. 136-137, ISBN 978-0-387-74640-1Este resultado se ha denominado a veces "teorema de los dos colores"; Soifer lo atribuye a un famoso artículo de 1879 de Alfred Kempe que contenía una prueba falsa del teorema de los cuatro colores .
^ Bandelt, H.-J.; Chepoi, V.; Eppstein, D. (2010), "Combinatoria y geometría de grafos cuadrados finitos e infinitos", SIAM Journal on Discrete Mathematics , 24 (4): 1399–1440, arXiv : 0905.4537 , doi :10.1137/090760301, S2CID 10788524.
^ Asratian, Denley y Häggkvist (1998), pág. 11.
^ Archdeacon, D .; Debowsky, M.; Dinitz, J .; Gavlas, H. (2004), "Sistemas de ciclos en el gráfico bipartito completo menos un factor", Discrete Mathematics , 284 (1–3): 37–43, doi :10.1016/j.disc.2003.11.021.
^ Ovchinnikov, Sergei (2011), Gráficos y cubos , Universitext, Springer. Véase especialmente el Capítulo 5, "Cubos parciales", págs. 127-181.
^ Asratian, Denley y Häggkvist (1998), Teorema 2.1.3, pág. 8. Asratian et al. atribuyen esta caracterización a un artículo de Dénes Kőnig de 1916. Para grafos infinitos, este resultado requiere el axioma de elección .
^ Bang-Jensen, Jørgen; Gutin, Gregory (2001), Dígrafos: teoría, algoritmos y aplicaciones (PDF) (1.ª ed.), Springer, pág. 25, ISBN 9781852332686, archivado (PDF) del original el 2 de enero de 2023 , consultado el 2 de enero de 2023
^ Woodall, DR (1990), "Una prueba de la caracterización euleriana-bipartita de McKee", Discrete Mathematics , 84 (2): 217–220, doi :10.1016/0012-365X(90)90380-Z, MR 1071664
^ Biggs, Norman (1994), Teoría de grafos algebraicos, Cambridge Mathematical Library (2.ª ed.), Cambridge University Press, pág. 53, ISBN 9780521458979.
^ Kőnig, Dénes (1931), "Gráfok és mátrixok", Matematikai és Fizikai Lapok , 38 : 116-119.
^ Gross, Jonathan L.; Yellen, Jay (2005), Teoría de grafos y sus aplicaciones, Matemáticas discretas y sus aplicaciones (2.ª ed.), CRC Press, pág. 568, ISBN 9781584885054.
^ Chartrand, Gary ; Zhang, Ping (2012), Un primer curso de teoría de grafos, Courier Dover Publications, págs. 189-190, ISBN 9780486483689.
^ Béla Bollobás (1998), Teoría de grafos moderna, Textos de posgrado en matemáticas, vol. 184, Springer, pág. 165, ISBN 9780387984889.
^ Chudnovsky, Maria ; Robertson, Neil ; Seymour, Paul ; Thomas, Robin (2006), "El teorema del grafo perfecto fuerte", Anales de Matemáticas , 164 (1): 51–229, arXiv : math/0212070 , CiteSeerX 10.1.1.111.7265 , doi :10.4007/annals.2006.164.51, S2CID 119151552 .
^ DeVos, Matt, "Matchings" (PDF) , Notas de clase: Introducción a la teoría de grafos, Matemáticas 345 , Universidad Simon Fraser
^ Lovász, László (2014), Problemas y ejercicios combinatorios (2ª ed.), Elsevier, p. 281, ISBN 9780080933092
^ Asratian, Denley y Häggkvist (1998), pág. 17.
^ AA Sapozhenko (2001) [1994], "Hipergrafo", Enciclopedia de Matemáticas , EMS Press
^ Brualdi, Richard A.; Harary, Frank ; Miller, Zevi (1980), "Bígrafos versus dígrafos a través de matrices", Journal of Graph Theory , 4 (1): 51–73, doi :10.1002/jgt.3190040107, MR 0558453Brualdi et al. atribuyen la idea de esta equivalencia a Dulmage, AL; Mendelsohn, NS (1958), "Coberturas de grafos bipartitos", Canadian Journal of Mathematics , 10 : 517–534, doi : 10.4153/CJM-1958-052-0 , MR 0097069, S2CID 123363425.
^ Sedgewick, Robert (2004), Algoritmos en Java, Parte 5: Algoritmos de gráficos (3.ª ed.), Addison Wesley, págs. 109-111.
^ Kleinberg, Jon ; Tardos, Éva (2006), Diseño de algoritmos , Addison Wesley, págs. 94–97.
^ Eppstein, David (2009), "Prueba de bipartidismo de gráficos de intersección geométrica", ACM Transactions on Algorithms , 5 (2): Art. 15, arXiv : cs.CG/0307023 , doi :10.1145/1497290.1497291, MR 2561751, S2CID 60496.
^ Yannakakis, Mihalis (1978), "Problemas NP-completos con eliminación de nodos y aristas", Actas del 10º Simposio ACM sobre teoría de la computación (STOC '78) , págs. 253-264, doi : 10.1145/800133.804355 , S2CID 363248
^ Reed, Bruce ; Smith, Kaleigh; Vetta, Adrian (2004), "Encontrar transversales de ciclos impares", Operations Research Letters , 32 (4): 299–301, CiteSeerX 10.1.1.112.6357 , doi :10.1016/j.orl.2003.10.009, MR 2057781 .
^ Guo, Jiong; Gramm, Jens; Hüffner, Falk; Niedermeier, Rolf; Wernicke, Sebastian (2006), "Algoritmos de parámetros fijos basados en compresión para la bipartición de aristas y conjuntos de vértices con retroalimentación", Journal of Computer and System Sciences , 72 (8): 1386–1396, doi : 10.1016/j.jcss.2006.02.001
^ Ahuja, Ravindra K.; Magnanti, Thomas L.; Orlin, James B. (1993), "12. Asignaciones y emparejamientos", Flujos de red: teoría, algoritmos y aplicaciones , Prentice Hall, págs. 461–509.
^ Ahuja, Magnanti y Orlin (1993), pág. 463: "Los problemas de coincidencia no bipartita son más difíciles de resolver porque no se reducen a problemas de flujo de red estándar".
^ Hopcroft, John E. ; Karp, Richard M. (1973), "Un algoritmo n ^5/2 para emparejamientos máximos en gráficos bipartitos", SIAM Journal on Computing , 2 (4): 225–231, doi :10.1137/0202019.
^ Ahuja, Magnanti y Orlin (1993), Aplicación 12.1 Asignación de personal bipartita, págs. 463–464.
^ 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 2016-11-18 , consultado el 2012-08-27.
^ Dulmage y Mendelsohn (1958).
^ Moon, Todd K. (2005), Codificación de corrección de errores: métodos y algoritmos matemáticos, John Wiley & Sons, pág. 638, ISBN 9780471648000.
^ Luna (2005), pág. 686.
^ Cassandras, Christos G.; Lafortune, Stephane (2007), Introducción a los sistemas de eventos discretos (2.ª ed.), Springer, pág. 224, ISBN 9780387333328.
^ Grünbaum, Branko (2009), Configuraciones de puntos y líneas, Estudios de posgrado en matemáticas , vol. 103, American Mathematical Society , pág. 28, ISBN 9780821843086.

Enlaces externos

"Grafo 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
Grafos bipartitos en biología de sistemas y medicina