En el campo matemático de la teoría de grafos , un grafo bipartito (o bigraph ) es un grafo cuyos vértices se pueden dividir en dos conjuntos independientes y disjuntos. y tal que cada borde conecta un vértice en a uno 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]
Los dos conjuntos y puede pensarse como una coloración del gráfico con dos colores: si uno colorea todos los nodos en azul, y todos los nodos en verde, 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 verde, el tercer vértice del triángulo se conecta a los vértices de ambos colores, evitando que se le asigne ninguno de los dos colores.
Uno escribe a menudo para denotar un grafo bipartito cuya partición tiene las partes y , con que denota los bordes del gráfico. Si un gráfico bipartito no está conectado , puede tener más de una bipartición; [5] en este caso, elLa 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 la misma cardinalidad , entoncesse llama gráfico bipartito equilibrado . [3] Si todos los vértices del mismo lado de la bipartición tienen el mismo grado , entoncesse llama birregular .
Ejemplos de
Al modelar relaciones entre dos clases diferentes de objetos, los gráficos bipartitos surgen con mucha frecuencia 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 una red de afiliación , un tipo de gráfico bipartito utilizado en el análisis de redes sociales . [6]
Otro ejemplo en el que aparecen gráficos bipartitos de forma natural 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 puede modelarse como un problema de conjunto dominante en un gráfico bipartito que tiene un vértice para cada tren y cada estación y un borde para cada par de una estación y un tren que se detiene en esa estación. [7]
Un tercer ejemplo está en el campo académico de la numismática. Las monedas antiguas se hacen usando 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]
Entre los ejemplos más abstractos se incluyen los siguientes:
- Cada árbol es bipartito. [4]
- Los gráficos cíclicos con un número par de vértices son bipartitos. [4]
- Cada gráfico plano cuyas caras tienen todas una longitud uniforme 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 se 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 gráficos bipartitos completos están los gráficos de corona , formados a partir de gráficos bipartitos completos al eliminar los bordes de una coincidencia perfecta . [12]
- Los gráficos de hipercubo , los cubos parciales y los gráficos de mediana son bipartitos. En estos gráficos, los vértices pueden ser etiquetados por 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 las gráficas cuadradas forman ejemplos de gráficas medianas, y cada gráfica mediana es un cubo parcial. [13]
Propiedades
Caracterización
Los gráficos bipartitos se pueden caracterizar de varias formas diferentes:
- Un gráfico es bipartito si y solo si no contiene un ciclo impar . [14]
- Un gráfico es bipartito si y solo si es 2-colorante (es decir, su número cromático es menor o igual a 2). [3]
- El espectro de un gráfico es simétrico si y solo si es un gráfico bipartito. [15]
Teorema de Kőnig y gráficas perfectas
En gráficos bipartitos, el tamaño de la cobertura mínima del vértice es igual al tamaño de la coincidencia máxima ; este es el teorema de Kőnig . [16] [17] Una forma alternativa y equivalente de este teorema es que el tamaño del conjunto máximo independiente 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 del borde mínimo más el tamaño de una coincidencia máxima es igual al número de vértices. [18] La combinación de esta igualdad con el teorema de Kőnig conduce al hecho de que, en los gráficos bipartitos, el tamaño de la cobertura del borde mínimo es igual al tamaño del conjunto independiente máximo, y el tamaño de la cobertura del borde mínimo 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 concierne 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 reafirmación del teorema de Kőnig. Este fue uno de los resultados que motivó la definición inicial de gráficos perfectos. [19] La perfección de los complementos de las gráficas lineales de las gráficas perfectas es otra nueva afirmación del teorema de Kőnig, y la perfección de las gráficas lineales en sí es una reformulación de un teorema anterior de Kőnig, según el cual cada grafo bipartito tiene una coloración de bordes usando colores iguales a su grado máximo.
De acuerdo con el teorema del grafo perfecto fuerte , los grafos perfectos tienen una caracterizacion grafica prohibida 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 demostración del teorema de la gráfica perfecta fuerte. [20]
La licenciatura
Para un vértice, el número de vértices adyacentes se denomina grado del vértice y se denota. La fórmula de la suma de grados para un gráfico bipartito establece que
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 una secuencia de grados. Los gráficos bipartitos isomorfos 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 isomórficos pueden tener la misma secuencia de grados.
El problema de la realización bipartita es el problema de encontrar una gráfica bipartita simple con la secuencia de grados siendo dos listas dadas de números naturales. (Los ceros finales se pueden ignorar, ya que se realizan trivialmente agregando un número apropiado de vértices aislados al dígrafo).
Relación con hipergráficos y gráficos dirigidos
La matriz de biadjacencia de un gráfico bipartitoes una (0,1) matriz de tamañoque tiene uno para cada par de vértices adyacentes y un cero para los vértices no adyacentes. [21] Las matrices de biadyacencia se pueden utilizar para describir equivalencias entre gráficos bipartitos, hipergráficos y gráficos dirigidos.
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 extremos. Un gráfico bipartitose puede utilizar para modelar un hipergráfico en el que U es el conjunto de vértices del hipergráfico, V es el conjunto de hipergrafos y E contiene una arista desde un vértice de hipergrafia v hasta una arista de hipergrafia e exactamente cuando v es uno de los puntos finales de e . Bajo esta correspondencia, las matrices de biadjacencia de los 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 mas 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 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. [22]
Se puede utilizar una reinterpretación similar de 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 propios) y gráficos bipartitos balanceados, con el mismo número de vértices en ambos lados de la bipartición. Porque, la matriz de adyacencia de un grafo dirigido con n vértices puede ser cualquier (0,1) matriz de tamaño, que luego se puede reinterpretar como la matriz de adyacencia de un grafo bipartito con n vértices en cada lado de su bipartición. [23] En esta construcción, el gráfico bipartito es la doble cobertura bipartita del gráfico dirigido.
Algoritmos
Prueba de la bipartita
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 primero . La idea principal es asignar a cada vértice el color que difiere del color de su padre en el bosque de búsqueda de profundidad primero, asignando colores en un recorrido de preorden del bosque de búsqueda de profundidad primero. Esto proporcionará necesariamente un color doble del bosque en expansión que consiste en los bordes que conectan los vértices con sus padres, pero es posible que no coloree correctamente algunos de los bordes que no son del bosque. En un bosque de búsqueda en profundidad primero, uno de los dos puntos finales de cada borde que no es del bosque es un ancestro del otro punto final, y cuando la primera 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 de antepasado a descendiente, junto con el borde mal coloreado, forman un ciclo impar, que se devuelve del 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 tener el color adecuado y el algoritmo devuelve el color junto con el resultado de que el gráfico es bipartito. [24]
Alternativamente, se puede utilizar un procedimiento similar con la búsqueda primero en amplitud en lugar de la 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 un borde que lo conecta con un vértice previamente coloreado con el mismo color, entonces este borde junto con las rutas en el bosque de búsqueda de amplitud primero que conecta sus dos extremos con su ancestro común más bajo forma un ciclo impar. Si el algoritmo termina sin encontrar un ciclo impar de esta manera, entonces debe haber encontrado un color adecuado y puede concluir con seguridad que el gráfico es bipartito. [25]
Para las gráficas 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, aunque el gráfico en sí puede tener hasta bordes. [26]
Ciclo impar transversal
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. [27] El problema es tratable con parámetros fijos , lo que significa que hay un algoritmo cuyo tiempo de ejecución puede estar acotado por una función polinomial del tamaño del gráfico multiplicado por una función mayor de k . [28] El nombre transversal de ciclo impar proviene del hecho de que una gráfica es bipartita si y solo si no tiene ciclos impares . Por lo tanto, para eliminar vértices de un gráfico con el fin de obtener un gráfico bipartito, es necesario "acertar todos los ciclos impares", o encontrar un conjunto transversal llamado ciclo impar . En la ilustración, cada ciclo impar del gráfico contiene los vértices azules (los de la parte inferior), por lo que eliminar esos vértices mata todos los ciclos impares y deja un gráfico bipartito.
El problema de la bipartición de los bordes es el problema algorítmico de eliminar el menor número posible de bordes para hacer un gráfico bipartito y también es un problema importante en los algoritmos de modificación de gráficos. Este problema también se puede tratar con parámetros fijos y se puede resolver a tiempo, [29] donde k es el número de bordes a eliminar y m es el número de bordes en el gráfico de entrada.
Pareo
Una coincidencia en un gráfico es un subconjunto de sus bordes, de los cuales no hay dos que compartan un punto final. Los algoritmos de tiempo polinómico son conocidos por muchos problemas algorítmicos sobre emparejamientos, incluido el emparejamiento máximo (encontrar un emparejamiento que use tantos bordes como sea posible), el emparejamiento de peso máximo y el matrimonio estable . [30] En muchos casos, los problemas de coincidencia son más simples de resolver en gráficos bipartitos que en gráficos no bipartitos, [31] y muchos algoritmos de coincidencia como el algoritmo Hopcroft-Karp para la máxima coincidencia de cardinalidad [32] funcionan correctamente solo en entradas bipartitas .
Como ejemplo simple, suponga que un conjunto de las personas buscan trabajo entre un conjunto de puestos de trabajo, con no todas las personas adecuadas para todos los puestos de trabajo. Esta situación se puede modelar como un gráfico bipartito.donde una ventaja conecta a cada solicitante de empleo con cada trabajo adecuado. [33] 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 los gráficos bipartitos que permiten emparejamientos perfectos. El Programa Nacional de Emparejamiento de Residentes aplica métodos de emparejamiento de gráficos para resolver este problema para estudiantes de medicina estadounidenses que buscan empleo y trabajos de residencia en hospitales . [34]
La descomposición de Dulmage-Mendelsohn es una descomposición estructural de gráficos bipartitos que es útil para encontrar coincidencias máximas. [35]
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 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 sumen cero en una palabra de código sin errores. [36] 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 . [37]
En informática, una red de Petri es una herramienta de modelado matemático que se utiliza en el análisis y las simulaciones de sistemas concurrentes. Un sistema se modela como un grafo dirigido bipartito con dos conjuntos de nodos: un conjunto de nodos de "lugar" que contienen recursos y un conjunto de nodos de "eventos" que generan y / o consumen recursos. Hay restricciones adicionales en los nodos y bordes que restringen 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, al mismo tiempo que permiten una fácil implementación de las simulaciones del sistema. [38]
En geometría proyectiva , los gráficos de Levi son una forma de gráfico 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 unen en un punto como máximo y cada dos puntos se conectan con una sola línea, las gráficas de Levi no contienen necesariamente ciclos de longitud cuatro, por lo que su circunferencia debe ser seis o más. . [39]
Ver también
- Dimensión bipartita , el número mínimo de gráficos bipartitos completos cuya unión es el gráfico dado
- Cubierta 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 bipartita a los hipergrafos .
- Matroide bipartito , 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
- Grafo bipartito convexo , un grafo bipartito cuyos vértices se pueden ordenar de modo que las vecindades de los vértices sean contiguas
- Grafo multipartito , una generalización de grafos bipartitos a más de dos subconjuntos de vértices
- Gráfico de paridad , una generalización de 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 las terminales forman un conjunto independiente, lo que permite algoritmos de aproximación que generalizan los de los 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
- ^ Diestel, Reinard (2005), Teoría de grafos , Textos de posgrado en matemáticas , Springer, ISBN 978-3-642-14278-9
- ^ Asratian, Armen S .; Denley, Tristan MJ; Häggkvist, Roland (1998), Gráficos bipartitos y sus aplicaciones , Cambridge Tracts in Mathematics, 131 , Cambridge University Press, ISBN 9780521593458.
- ↑ a b c Asratian, Denley y Häggkvist (1998) , p. 7.
- ^ a b c Scheinerman, Edward R. (2012), Matemáticas: una introducción discreta (3ª ed.), Cengage Learning, p. 363, ISBN 9780840049421.
- ^ Chartrand, Gary ; Zhang, Ping (2008), Teoría de gráficos cromáticos , Matemáticas discretas y sus aplicaciones, 53 , CRC Press, p. 223, ISBN 9781584888000.
- ^ Wasserman, Stanley ; Faust, Katherine (1994), Social Network Analysis: Methods and Applications , Structural Analysis in the Social Sciences, 8 , Cambridge University Press, págs. 299-302, ISBN 9780521387071.
- ^ Niedermeier, Rolf (2006), Invitación a 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.), Judaea and Rome in Coins 65 a. C. - 135 d. C.: ponencias presentadas en la conferencia internacional organizada por Spink, del 13 al 14 de septiembre de 2010 , Spink & Son , págs. 65–84
- ^ Soifer, Alexander (2008), The Mathematical Coloring Book , Springer-Verlag, págs. 136-137, ISBN 978-0-387-74640-1. Este resultado a veces se ha llamado el "teorema de los dos colores"; Soifer lo atribuye a un famoso artículo de Alfred Kempe de 1879 que contiene una prueba falsa del teorema de los cuatro colores .
- ^ Bandelt, H.-J .; Chepoi, V .; Eppstein, D. (2010), "Combinatoria y geometría de gráficos 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. 11.
- ^ Archidiácono, D .; Debowsky, M .; Dinitz, J .; Gavlas, H. (2004), "Sistemas de ciclos en el gráfico bipartito completo menos un factor único", Matemáticas discretas , 284 (1-3): 37-43, doi : 10.1016 / j.disc.2003.11.021.
- ^ Ovchinnikov, Sergei (2011), Gráficos y cubos , Universitext, Springer. Consulte especialmente el Capítulo 5, "Partial Cubes", págs. 127-181.
- ^ Asratian, Denley y Häggkvist (1998) , Teorema 2.1.3, p. 8. Asratian et al. atribuye esta caracterización a un artículo de 1916 de Dénes Kőnig . Para gráficos infinitos, este resultado requiere el axioma de elección .
- ^ Biggs, Norman (1994), Teoría de grafos algebraicos , Cambridge Mathematical Library (2ª ed.), Cambridge University Press, p. 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. 568, ISBN 9781584885054.
- ^ Chartrand, Gary; Zhang, Ping (2012), Un primer curso de teoría de grafos , Publicaciones de Courier Dover, págs. 189-190, ISBN 9780486483689.
- ^ Béla Bollobás (1998), Teoría Moderna de Grafos , Textos de Posgrado en Matemáticas, 184 , Springer, p. 165, ISBN 9780387984889.
- ^ Chudnovsky, Maria ; Robertson, Neil ; Seymour, Paul ; 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.
- ^ Asratian, Denley y Häggkvist (1998) , p. 17.
- ^ AA Sapozhenko (2001) [1994], "Hypergraph" , Encyclopedia of Mathematics , EMS Press
- ^ Brualdi, Richard A .; Harary, Frank ; Miller, Zevi (1980), "Bigraphs versus digraphs via matrices", Journal of Graph Theory , 4 (1): 51–73, doi : 10.1002 / jgt.3190040107 , MR 0558453. Brualdi y col. acreditar 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.
- ^ 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), Algorithm Design , Addison Wesley, págs. 94–97.
- ^ Eppstein, David (2009), "Prueba de la bipartidad de los gráficos de intersección geométrica", Transacciones ACM sobre algoritmos , 5 (2): Art. 15, arXiv : cs.CG/0307023 , doi : 10.1145 / 1497290.1497291 , MR 2561751 , S2CID 60496.
- ^ Yannakakis, Mihalis (1978), "Problemas NP-completos de eliminación de nodos y bordes", Actas del X 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), "Finding odd cycle transversals", 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 el 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
- ^ 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. 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 coincidencias máximas en gráficos bipartitos", SIAM Journal on Computing , 2 (4): 225-231, doi : 10.1137 / 0202019.
- ^ Ahuja, Magnanti & Orlin (1993) , Asignación de personal bipartita de solicitud 12.1, págs. 463–464.
- ^ Robinson, Sara (abril de 2003), "¿Están los estudiantes de medicina encontrando su (mejor) pareja posible?" (PDF) , SIAM News (3): 36, archivado desde el original (PDF) el 18 de noviembre de 2016 , consultado el 27 de agosto de 2012.
- ^ 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. 638, ISBN 9780471648000.
- ↑ Moon (2005) , p. 686.
- ^ Cassandras, Christos G .; Lafortune, Stephane (2007), Introducción a los sistemas de eventos discretos (2ª ed.), Springer, p. 224, ISBN 9780387333328.
- ^ Grünbaum, Branko (2009), Configuraciones de puntos y líneas , Estudios de posgrado en matemáticas , 103 , American Mathematical Society , p. 28, ISBN 9780821843086.
enlaces externos
- "Graph, bipartite" , Encyclopedia of Mathematics , EMS Press , 2001 [1994]
- Sistema de información sobre clases de gráficos y sus inclusiones : gráfico bipartito
- Weisstein, Eric W. , "Gráfico bipartito" , MathWorld
- Gráficos bipartitos en biología de sistemas y medicina