Grafo bipartito

Los grafos bipartitos pueden caracterizarse de varias maneras diferentes:

• Un grafo no dirigido es bipartito si y solo si no contiene un ciclo impar . ^{[ 13 ] [ 14 ]}
• Un grafo es bipartito si y solo si es 2-coloreable (es decir, su número cromático es menor o igual a 2). ^{[ 3 ]}
• Un grafo es bipartito si y solo 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 grafo. ^{[ 15 ]}
• Un grafo es bipartito si y solo si el espectro del grafo es simétrico. ^{[ 16 ]}

En los grafos bipartitos, el tamaño de la cobertura mínima de vértices es igual al tamaño del emparejamiento máximo ; este es el teorema de Kőnig . ^{[ 17 ] [ 18 ]} Una forma alternativa y equivalente de este teorema es que el tamaño del conjunto independiente máximo más el tamaño del emparejamiento máximo 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 un emparejamiento máximo es igual al número de vértices. ^{[ 19 ]} Combinando esta igualdad con el teorema de Kőnig se llega a los hechos de que, en los 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 se refiere a los grafos perfectos : todo grafo bipartito, el complemento de todo grafo bipartito, el grafo de líneas de todo grafo bipartito y el complemento del grafo de líneas de todo 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 clique 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. ^{[ 20 ]} La perfección de los complementos de los grafos de líneas de los grafos perfectos es otra reformulación del teorema de Kőnig, y la perfección de los grafos de líneas mismos es una reformulación de un teorema anterior de Kőnig, que todo grafo bipartito tiene una coloración de aristas usando un número de colores igual a su grado máximo.

Según el teorema del grafo perfecto fuerte , los grafos perfectos tienen una caracterización de grafos prohibidos similar a la de los grafos bipartitos: un grafo es bipartito si y solo si no tiene ningún ciclo impar como subgrafo, y un grafo es perfecto si y solo si no tiene ningún ciclo impar ni su complemento como subgrafo inducido . Los grafos bipartitos, los grafos de líneas de grafos bipartitos y sus complementos forman cuatro de las cinco clases básicas de grafos perfectos utilizadas en la demostración del teorema del grafo perfecto fuerte. ^{[ 21 ]} De ello se deduce que cualquier subgrafo de un grafo bipartito también es bipartito porque no puede adquirir un ciclo impar. ^{[ 22 ]}

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

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

La secuencia de grados de un grafo bipartito es el par de listas, cada una de las cuales contiene los grados de las dos partes.${\displaystyle U}$y${\displaystyle V}$Por ejemplo, el grafo bipartito completo K _3,5 tiene una secuencia de grados${\displaystyle (5,5,5),(3,3,3,3,3)}$Los grafos bipartitos isomorfos tienen la misma secuencia de grados. Sin embargo , la secuencia de grados no identifica de forma unívoca un grafo bipartito; en algunos casos, grafos bipartitos no isomorfos pueden tener la misma secuencia de grados.

El problema de realización bipartita consiste en encontrar un grafo bipartito simple cuya secuencia de grados esté formada por dos listas dadas de números naturales. (Los ceros finales pueden ignorarse, ya que se obtienen fácilmente añadiendo un número adecuado de vértices aislados al digrafo).

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

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 extremos. Un grafo bipartito${\displaystyle (U,V,E)}$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 v del hipergrafo hasta una arista e del hipergrafo exactamente cuando v es uno de los extremos de e . Bajo esta correspondencia, las matrices de biadyacencia 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 extremos, y representado por un grafo bipartito que no tiene adyacencias múltiples y en el que los vértices de un lado de la bipartición tienen todos grado dos. ^{[ 25 ]}

Una reinterpretación similar de las matrices de adyacencia puede utilizarse para mostrar una correspondencia biunívoca entre grafos dirigidos (con un número dado de vértices etiquetados, permitiendo bucles) y grafos bipartitos equilibrados, 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 matriz (0,1) de tamaño${\displaystyle n\times n}$, que luego puede reinterpretarse como la matriz de adyacencia de un grafo bipartito con n vértices en cada lado de su bipartición. ^{[ 26 ]} En esta construcción, el grafo bipartito es la doble cubierta bipartita del grafo dirigido.

Es posible comprobar si un grafo es bipartito y obtener una coloración doble (si lo es) o un ciclo impar (si no lo es) en tiempo lineal , utilizando la búsqueda en profundidad (DFS). La idea principal es asignar a cada vértice un color distinto al de su padre en el bosque DFS, asignando colores mediante un recorrido en preorden del bosque de búsqueda en profundidad. Esto proporcionará necesariamente una coloración doble del bosque de expansión formado por las aristas que conectan los vértices con sus padres, pero puede que no coloree correctamente algunas de las aristas que no pertenecen al bosque. En un bosque DFS, uno de los dos extremos de cada arista que no pertenece al bosque es un ancestro del otro extremo, y cuando la búsqueda en profundidad descubre una arista de este tipo, debe comprobar 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 la arista mal coloreada, forman un ciclo impar, que el algoritmo devuelve junto con el resultado de que el grafo no es bipartito. Sin embargo, si el algoritmo termina sin detectar un ciclo impar de este tipo, entonces cada arista debe estar correctamente coloreada, y el algoritmo devuelve el coloreado junto con el resultado de que el grafo es bipartito. ^{[ 27 ]}

Alternativamente, se puede utilizar un procedimiento similar con búsqueda en anchura en lugar de DFS. Nuevamente, a cada nodo se le asigna el color opuesto al de su padre en el bosque de búsqueda, en orden de anchura. Si, al colorear un vértice, existe una arista que lo conecta con un vértice previamente coloreado con el mismo color, entonces esta arista, junto con los caminos en el bosque de búsqueda en anchura que conectan 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 una coloración adecuada y puede concluir con seguridad que el grafo es bipartito. ^{[ 28 ]}

Para los gráficos de intersección de${\displaystyle n}$segmentos de línea u otras formas simples en el plano euclidiano , es posible comprobar si el grafo es bipartito y devolver una coloración de dos colores o un ciclo impar en el tiempo.${\displaystyle O(n\log n)}$, utilizando la notación Big O , aunque el gráfico en sí mismo puede tener hasta${\displaystyle O(n^{2})}$bordes. ^{[ 29 ]}

El problema de la transversalidad de ciclos impares 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 haría que el grafo resultante fuera bipartito. ^{[ 30 ]} El problema es tratable con parámetros fijos , lo que significa que existe un algoritmo cuyo tiempo de ejecución puede ser acotado por una función polinómica del tamaño del grafo multiplicada por una función mayor de k . ^{[ 31 ]} El nombre transversalidad de ciclos impares 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 con el fin de obtener un grafo bipartito, es necesario "tocar todos los ciclos impares", o encontrar un llamado conjunto transversalidad de ciclos impares . En la ilustración, cada ciclo impar en el grafo contiene los vértices azules (los más bajos), por lo que eliminar esos vértices elimina 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 la algoritmia de modificación de grafos. Este problema también es tratable con parámetros fijos y puede resolverse en tiempo${\textstyle O\left(2^{k}m^{2}\right)}$, ^{[ 32 ]} donde k es el número de aristas a eliminar y m es el número de aristas en el grafo de entrada.

Un emparejamiento en un grafo es un subconjunto de sus aristas, donde no hay dos que compartan un extremo. Se conocen algoritmos de tiempo polinomial para muchos problemas algorítmicos de emparejamientos, incluyendo el emparejamiento máximo (encontrar un emparejamiento que utilice tantas aristas como sea posible), el emparejamiento de peso máximo y el matrimonio estable . ^{[ 33 ]} En muchos casos, los problemas de emparejamiento son más sencillos de resolver en grafos bipartitos que en grafos no bipartitos, ^{[ 34 ]} y muchos algoritmos de emparejamiento, como el algoritmo de Hopcroft-Karp para el emparejamiento de cardinalidad máxima ^{[ 35 ],} funcionan correctamente solo en entradas bipartitas.

Como ejemplo sencillo, supongamos que un conjunto${\displaystyle P}$de personas están buscando trabajo entre un conjunto${\displaystyle J}$de empleos, y no todas las personas son aptas para todos los empleos. Esta situación se puede modelar como un grafo bipartito.${\displaystyle (P,J,E)}$donde una arista conecta a cada solicitante de empleo con cada puesto adecuado. ^{[ 36 ]} Un emparejamiento perfecto describe una forma de satisfacer simultáneamente a todos los solicitantes de empleo y cubrir todos los puestos; el teorema del matrimonio de Hall proporciona una caracterización de los grafos bipartitos que permiten emparejamientos perfectos. El Programa Nacional de Asignación de Residentes aplica métodos de emparejamiento de grafos para resolver este problema para los solicitantes de empleo de estudiantes de medicina de EE. UU. y los puestos de residencia hospitalaria . ^{[ 37 ]}

La descomposición de Dulmage-Mendelsohn es una descomposición estructural de grafos bipartitos que resulta útil para encontrar emparejamientos máximos. ^{[ 38 ]}