Grafos bipartitos explicados

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

1. Qué hace que un grafo sea bipartito

Un grafo es bipartito cuando sus vértices pueden dividirse en dos grupos de modo que cada arista vaya de un grupo al otro. Ninguna arista puede quedarse dentro de un grupo. Los dos grupos se llaman los lados o partes del grafo, y la división en sí es una bipartición.

En símbolos, un grafo G = (V, E) es bipartito si existen conjuntos disjuntos U y W con U ∪ W = V tales que cada arista tiene un extremo en U y el otro en W. Muchos textos escriben el grafo como G = (U, W, E) para no perder de vista la división. Nada exige que estén presentes todas las aristas posibles entre los lados, y nada exige que los lados tengan el mismo tamaño. La única regla es una prohibición: no hay ninguna arista dentro de U ni ninguna arista dentro de W. En el vocabulario de la guía sobre vértices y aristas, ambos lados son conjuntos independientes.

La propiedad es fácil de enunciar y sorprendentemente fácil de pasar por alto. El grafo de la izquierda en la figura siguiente es el ejemplo que acompaña a todo este artículo: ocho vértices, nueve aristas. Dibujado como un anillo con una cuerda, no parece nada en particular. Ordena los mismos vértices en dos columnas y la estructura salta a la vista.

La lista de aristas es lo bastante corta como para tenerla en la cabeza:

V = {A, B, C, D, E, F, G, H}
E = {AB, AD, AF, BC, CF, DE, EH, FG, GH}          9 aristas

U = {A, C, E, G}      W = {B, D, F, H}             cada arista une U con W

Conviene aclarar dos casos límite desde el principio. Un lazo une un vértice consigo mismo, así que sus dos extremos quedan en el mismo lado, y un grafo con un lazo nunca es bipartito. Las aristas paralelas no cambian nada: una segunda arista entre u y v cruza entre los lados exactamente igual que la primera, y esa es una de las propiedades que la guía sobre grafos simples y multigrafos presenta como inmunes a la multiplicidad. En un grafo dirigido, la pregunta se plantea sobre el grafo no dirigido subyacente, porque la definición nunca mira hacia dónde apunta una arista.

2. Dos colores, una bipartición

Pinta de azul los vértices de U y de naranja los de W. La definición dice entonces que los dos extremos de cada arista tienen colores distintos, que es exactamente una coloración propia con dos colores. Las dos descripciones son intercambiables:

Un grafo es bipartito si y solo si puede colorearse de forma propia con dos colores. Su número cromático es entonces como mucho 2: exactamente 2 si tiene al menos una arista, y 1 si no tiene ninguna.

La vista de la coloración explica un hecho que la vista de conjuntos oculta. En un grafo bipartito conexo, la bipartición es única, salvo por intercambiar los nombres de los dos lados. Colorea de azul un vértice cualquiera y todos los demás quedan determinados: un vecino tiene que ser naranja, un vecino de un vecino azul, y en general un vértice es azul exactamente cuando su distancia al vértice inicial es par. No queda ninguna elección en ninguna parte. En el ejemplo, {A, C, E, G} frente a {B, D, F, H} es la única división posible.

Un grafo con varias componentes se comporta de otra manera, porque cada componente puede invertirse por separado. Con k componentes hay 2k 2-coloraciones propias y 2k−1 biparticiones distintas, contando cada vértice aislado como una componente. Así que la pregunta «¿en qué lado está el vértice v?» tiene sentido dentro de una componente y es arbitraria entre componentes. Un código que guarda un único lado global para cada vértice y luego compara lados entre piezas no conectadas está comparando etiquetas que se eligieron de forma independiente.

3. Grafos bipartitos que ya conoces

Los grafos bipartitos no son un tema especial escondido en un capítulo posterior. Varias de las familias más conocidas son bipartitas, algunas por razones que cuesta un momento ver.

• Árboles y bosques. Un árbol no tiene ningún ciclo, así que nada puede salir mal: enráizalo en cualquier parte y colorea cada vértice según su profundidad sea par o impar. Todo árbol es bipartito, una consecuencia más de la estructura que se desarrolla en árboles en teoría de grafos.
• Caminos y ciclos pares. Un camino alterna los colores a lo largo de su recorrido. Un ciclo con un número par de vértices también, y se cierra correctamente. Un ciclo con un número impar no lo hace, como demuestra la sección siguiente.
• Cuadrículas y tableros de ajedrez. Colorea la casilla de la fila r y la columna c según la paridad de r + c y obtienes el patrón del tablero de ajedrez. Un paso a una casilla vecina cambia la paridad, así que el grafo de cuadrícula es bipartito. Un movimiento de caballo cambia una coordenada en 1 y la otra en 2, un total impar, así que el caballo siempre cae en el color contrario y el grafo del caballo también es bipartito.
• Hipercubos. El grafo del cubo Qn tiene como vértices las cadenas de n bits, con una arista entre dos cadenas que difieren exactamente en un bit. Cambiar un bit modifica en uno el número de unos, así que funciona colorear según la paridad de esa cuenta.
• Todo lo que se construye con dos tipos de cosas. Candidatos y puestos, usuarios y productos, autores y artículos, estudiantes y cursos. Cuando cada arista une un tipo con el otro, el grafo es bipartito por construcción.

El ejemplo del tablero tiene una recompensa clásica. Quita dos esquinas diagonalmente opuestas de un tablero de 8 por 8. ¿Pueden cubrirse las 62 casillas restantes con 31 fichas de dominó? Cada ficha cubre dos casillas vecinas, una de cada color. Las dos esquinas quitadas tienen el mismo color, así que el tablero tiene ahora 30 casillas de un color y 32 del otro, y no puede existir ningún recubrimiento. En términos de grafos, un recubrimiento con dominós es un emparejamiento perfecto en el grafo de cuadrícula, un emparejamiento perfecto en un grafo bipartito necesita lados iguales, y estos lados son desiguales. El acertijo lo planteó el filósofo Max Black en 1946 y más tarde lo hizo famoso Martin Gardner; es el argumento más breve que existe de por qué merece la pena fijarse en la bipartición.

Igual de útiles son los grafos que no son bipartitos. Cualquier grafo con un triángulo falla, porque tres vértices adyacentes entre sí necesitan tres colores. Eso descarta todo grafo completo Kn con n ≥ 3, y también descarta los siete puentes de Königsberg: la orilla norte, la isla y la isla del este forman un triángulo. El grafo de Petersen falla sin contener ningún triángulo, porque está lleno de ciclos de longitud 5.

4. El teorema de Kőnig: ningún ciclo impar

Los triángulos son un obstáculo, pero no el verdadero. El verdadero obstáculo es cualquier ciclo de longitud impar, y es el único obstáculo que existe.

Teorema. Un grafo es bipartito si y solo si no contiene ningún ciclo de longitud impar.

El resultado se debe a Dénes Kőnig. Asratian, Denley y Häggkvist lo remontan a su artículo de 1916 en Mathematische Annalen, y aparece con demostración en su libro de 1936 Theorie der endlichen und unendlichen Graphen, el primer libro de texto de teoría de grafos (el mismo libro del que se habla en grafos finitos e infinitos). Las dos direcciones de la demostración son breves, y la segunda es un algoritmo disfrazado.

Bipartito implica ningún ciclo impar. Recorre un ciclo v0, v1, …, vk−1 y vuelve a v0. Cada paso cambia el color, así que vi tiene el mismo color que v0 exactamente cuando i es par. La arista que cierra el ciclo, de vk−1 a v0, une dos colores distintos solo si k − 1 es impar, es decir, solo si la longitud del ciclo k es par.

Ningún ciclo impar implica bipartito. Trabaja componente por componente y elige una raíz cualquiera r. Colorea cada vértice según la paridad de su distancia a r. Supón que alguna arista uv uniera dos vértices del mismo color, de modo que d(u) y d(v) tienen la misma paridad. Sigue un camino más corto de r a u, cruza la arista hasta v y sigue un camino más corto de v de vuelta a r. Ese recorrido cerrado tiene longitud d(u) + d(v) + 1, que es impar.

Un recorrido cerrado todavía no es un ciclo, porque puede repetir vértices, y este es el paso que las demostraciones descuidadas se saltan. Lo arregla un pequeño lema: todo recorrido cerrado de longitud impar contiene un ciclo de longitud impar. Si el recorrido repite un vértice, pártelo ahí en dos recorridos cerrados más cortos; sus longitudes suman un número impar, así que uno de ellos es impar, y la inducción sobre la longitud termina el trabajo. El ciclo impar contradice la hipótesis, así que no existe tal arista y la coloración por distancias es propia.

El panel central de la figura contiene la trampa que conviene recordar. El ciclo de 5 es libre de triángulos y aun así no es bipartito. «Sin triángulos» es una condición necesaria y ni de lejos suficiente. Cuenta cualquier longitud impar.

El ejemplo del artículo supera la prueba. Sus ciclos tienen longitudes 4 (A, B, C, F), 6 (A, D, E, H, G, F) y 8 (el anillo exterior), todas pares. Conviene tener a mano dos corolarios sencillos. Borrar aristas o vértices nunca puede crear un ciclo impar, así que todo subgrafo de un grafo bipartito es bipartito. Añadir una sola arista, en cambio, puede destruir la propiedad, como muestra la sección siguiente.

5. Comprobar un grafo en tiempo lineal

La segunda mitad de la demostración es un procedimiento. Lanza una búsqueda en anchura desde cualquier vértice, da a cada vértice recién descubierto el color contrario al de su padre y vigila cada arista que examines. Si alguna arista tiene el mismo color en ambos extremos, el grafo no es bipartito. Si la búsqueda termina sin que eso ocurra, los colores forman una bipartición válida. Repite desde un vértice sin colorear hasta haber recorrido todas las componentes.

Una buena prueba hace algo más que responder sí o no. Devuelve un certificado que puede comprobarse de forma independiente: la 2-coloración cuando la respuesta es sí, y un ciclo impar concreto cuando es no. La función siguiente hace ambas cosas.

from collections import deque

def bipartite_or_odd_cycle(graph):
    """Devuelve (True, colour) o (False, odd_cycle) para un grafo no dirigido."""
    colour, parent, depth = {}, {}, {}
    for start in graph:                      # todas las componentes, no solo una
        if start in colour:
            continue
        colour[start], parent[start], depth[start] = 0, None, 0
        queue = deque([start])
        while queue:
            u = queue.popleft()
            for v in graph[u]:
                if v not in colour:          # arista de árbol: v recibe el otro color
                    colour[v], parent[v], depth[v] = 1 - colour[u], u, depth[u] + 1
                    queue.append(v)
                elif colour[v] == colour[u]: # mismo color en ambos extremos: ciclo impar
                    return False, odd_cycle(u, v, parent, depth)
    return True, colour

def odd_cycle(u, v, parent, depth):
    # u y v están a la misma profundidad BFS; subir hasta que los caminos se encuentren.
    left, right = [u], [v]
    while u != v:
        u, v = parent[u], parent[v]
        left.append(u)
        right.append(v)
    return left + right[-2::-1]              # u ... encuentro ... v, cerrado por la arista v-u

graph = {
    'A': ['B', 'D', 'F'], 'B': ['A', 'C'], 'C': ['B', 'F'], 'D': ['A', 'E'],
    'E': ['D', 'H'], 'F': ['A', 'C', 'G'], 'G': ['F', 'H'], 'H': ['E', 'G'],
}
ok, colour = bipartite_or_odd_cycle(graph)
print(ok, sorted(v for v in colour if colour[v] == 0))
# True ['A', 'C', 'E', 'G']

graph['C'].append('E'); graph['E'].append('C')   # una arista extra
print(bipartite_or_odd_cycle(graph))
# (False, ['C', 'B', 'A', 'D', 'E'])

La extracción del ciclo se basa en una propiedad de la búsqueda en anchura: cada arista une dos vértices cuyas profundidades difieren como mucho en uno. Dos vértices del mismo color tienen profundidades de la misma paridad, así que una arista en conflicto siempre une dos vértices a la misma profundidad. Por eso, al subir por sus punteros a los padres a la vez, se llega al vértice de encuentro en el mismo momento desde ambos lados. Si cada una de las dos subidas da t pasos, el ciclo tiene 2t + 1 aristas, un número impar por construcción.

Esto es lo que ocurre en el ejemplo del artículo, y luego tras añadir una arista de C a E:

BFS desde A       capa 0: A    capa 1: B, D, F    capa 2: C, E, G    capa 3: H
                  cada arista une capas vecinas   → bipartito, color 0 = {A, C, E, G}

añadir arista C-E C y E están ambos en la capa 2, así que tienen el mismo color
                  subida desde C: C, B, A    subida desde E: E, D, A    encuentro en A
                  ciclo impar C, B, A, D, E    5 aristas

Cada vértice entra una vez en la cola y cada arista se examina dos veces, una desde cada extremo, así que la prueba se ejecuta en tiempo O(V + E). Es tan rápido como leer el grafo. Una búsqueda en profundidad funciona igual de bien en principio, pero un DFS recursivo en Python choca con el límite de recursión por defecto de 1.000 en un camino largo, y esa es una razón por la que la versión iterativa en anchura es la opción más segura por defecto.

Conviene conocer una variante. Si las aristas llegan de una en una y necesitas saber tras cada inserción si el grafo sigue siendo bipartito, volver a lanzar la búsqueda es un desperdicio. Una estructura union-find que además guarde la paridad de cada vértice respecto a su raíz responde la pregunta en tiempo amortizado casi constante por arista: unir dos vértices que ya comparten raíz solo está permitido si sus paridades difieren.

6. Grafos bipartitos completos y el techo de n²/4

El grafo bipartito completo Km,n tiene m vértices en un lado, n en el otro y todas las m × n aristas posibles entre los lados. Es para los grafos bipartitos lo que Kn es para los grafos en general: el miembro más denso de la familia para unos tamaños de lado dados.

Dos miembros tienen nombre propio. K1,n es la estrella, un centro unido a n hojas, y además es un árbol. K3,3 es el grafo de los servicios del viejo acertijo que pide conectar tres casas con tres servicios sin que se cruce ninguna línea. El acertijo no tiene solución: el teorema de Kuratowski de 1930 dice que un grafo es plano exactamente cuando no contiene ninguna subdivisión de K5 ni de K3,3, y K3,3 es una de las dos formas prohibidas.

La bipartición da una demostración de una línea de que K3,3 no es plano. En un dibujo sin cruces, cada cara está rodeada por un recorrido cerrado de aristas. Un grafo bipartito no tiene triángulos, así que en un grafo bipartito plano, simple y conexo con al menos tres vértices, el borde de cada cara tiene al menos 4 aristas. Cada arista se cuenta dos veces en total entre los bordes de las caras, lo que da 4f ≤ 2m. Sustituyendo en la fórmula de Euler v − m + f = 2 se obtiene

m ≤ 2v − 4        para un grafo bipartito plano, simple y conexo con v ≥ 3

K3,3:   v = 6,  m = 9,  pero 2v − 4 = 8        así que no existe ningún dibujo plano

Una segunda cota clásica tiene que ver con la densidad. Si un lado tiene k vértices y el otro n − k, hay como mucho k(n − k) aristas, y ese producto es máximo cuando los lados son lo más parecidos posible. Así que un grafo bipartito con n vértices tiene como mucho ⌊n²/4⌋ aristas, valor que alcanza K⌊n/2⌋,⌈n/2⌉. Mantel demostró en 1907 que el mismo techo vale para cualquier grafo libre de triángulos, y que el grafo bipartito completo equilibrado es el único que lo alcanza. Es un contraste llamativo con la trampa de la sección 4: los grafos libres de triángulos no tienen por qué ser bipartitos, pero el grafo libre de triángulos más denso siempre lo es. El ejemplo del artículo tiene 9 aristas frente a un techo de 16, el número de aristas de K4,4.

Los grados obedecen una versión más fina del lema del apretón de manos. Cada arista tiene exactamente un extremo en cada lado, así que

∑ deg(u) sobre u en U  =  |E|  =  ∑ deg(w) sobre w en W

ejemplo:   3 + 2 + 2 + 2  =  9  =  2 + 2 + 3 + 2

Una consecuencia rápida: si todos los vértices tienen el mismo grado k ≥ 1, entonces k|U| = k|W|, así que un grafo bipartito regular siempre tiene dos lados del mismo tamaño. Ese hecho es el primer paso hacia los resultados de emparejamiento de la sección siguiente.

7. Emparejamientos: por qué importan los grafos bipartitos

Un emparejamiento es un conjunto de aristas en el que no hay dos que compartan un vértice. En un grafo bipartito es una asignación: cada candidato recibe como mucho un puesto y cada puesto como mucho un candidato. Un emparejamiento es perfecto cuando cubre todos los vértices. Gran parte de la razón por la que los grafos bipartitos llenan libros de texto es que los problemas de emparejamiento sobre ellos son a la vez importantes y resolubles de forma eficiente, y la teoría viene con certificados exactos.

El primer certificado dice cuándo se puede atender a todos los de un lado.

Teorema de Hall (1935). Un grafo bipartito G = (U, W, E) tiene un emparejamiento que cubre todos los vértices de U si y solo si todo subconjunto S ⊆ U tiene al menos |S| vecinos en W.

Lee la hipótesis con atención, porque a menudo se cita mal. La condición de Hall trata de cubrir un lado, no de un emparejamiento perfecto. Ambas cosas coinciden solo cuando |U| = |W|. La necesidad es evidente: si dos candidatos están cualificados cada uno para un único puesto, y es el mismo puesto, no pueden colocarse los dos. La aportación de Hall es que este tipo de escasez local es lo único que puede fallar. Un corolario que Kőnig demostró en 1916: todo grafo bipartito k-regular con k ≥ 1 tiene un emparejamiento perfecto.

El segundo certificado demuestra que un emparejamiento no puede mejorarse. Un recubrimiento por vértices es un conjunto de vértices que toca todas las aristas. Cada arista de un emparejamiento necesita su propio vértice del recubrimiento, así que ningún emparejamiento es mayor que ningún recubrimiento. En los grafos bipartitos ambos se encuentran:

Teorema de Kőnig y Egerváry (1931). En un grafo bipartito, el tamaño de un emparejamiento máximo es igual al tamaño de un recubrimiento por vértices mínimo.

Fuera de los grafos bipartitos esto falla a la primera ocasión: un triángulo tiene un emparejamiento máximo de tamaño 1 y un recubrimiento por vértices mínimo de tamaño 2. En el ejemplo del artículo existe un emparejamiento de tamaño 4, y {A, C, E, G} es un recubrimiento por vértices de tamaño 4, así que cada uno certifica que el otro es óptimo sin ninguna búsqueda.

Para encontrar un emparejamiento máximo se usan caminos aumentantes: un camino que empieza en un vértice libre, alterna entre aristas fuera y dentro del emparejamiento y termina en otro vértice libre. Intercambiar los dos tipos de arista a lo largo de él aumenta el emparejamiento en uno. Berge demostró en 1957 que un emparejamiento es máximo exactamente cuando no existe ningún camino aumentante. En un grafo bipartito, buscar uno es una simple búsqueda en profundidad, lo que da el método breve que a menudo se llama algoritmo de Kuhn:

def max_matching(left, adj):
    """Algoritmo de caminos aumentantes de Kuhn. adj asigna a cada vértice izquierdo sus vecinos derechos."""
    match_of = {}                            # vértice derecho -> vértice izquierdo

    def augment(u, seen):
        for v in adj[u]:
            if v in seen:
                continue
            seen.add(v)
            # v está libre, o su pareja puede pasar a otro vértice derecho
            if v not in match_of or augment(match_of[v], seen):
                match_of[v] = u
                return True
        return False

    size = sum(augment(u, set()) for u in left)
    return size, {u: v for v, u in match_of.items()}

adj = {'A': ['B', 'D', 'F'], 'C': ['B', 'F'], 'E': ['D', 'H'], 'G': ['F', 'H']}
size, pairs = max_matching(['A', 'C', 'E', 'G'], adj)
print(size, dict(sorted(pairs.items())))
# 4 {'A': 'D', 'C': 'B', 'E': 'H', 'G': 'F'}

El resultado es un emparejamiento perfecto, A–D, C–B, E–H, G–F. No es el único: este grafo tiene exactamente tres emparejamientos perfectos. El método se ejecuta en tiempo O(V · E), y como cualquier búsqueda recursiva en Python necesita reescribirse de forma iterativa para grafos muy profundos. Para instancias grandes, la opción habitual es el algoritmo de Hopcroft-Karp de 1973, que encuentra muchos caminos aumentantes más cortos en cada fase y se ejecuta en O(E √V).

Conviene conocer por su nombre tres problemas relacionados:

• Asignación con pesos. Cuando cada arista tiene un coste y buscas el emparejamiento perfecto más barato, el método húngaro de Kuhn (1955) lo resuelve de forma eficiente. La guía de asignación de trabajo lo aplica a decisiones reales de personal.
• Emparejamiento como flujo. Añade una fuente unida a cada vértice de U, un sumidero al que llega cada vértice de W, da a cada arista capacidad 1, y un flujo máximo es un emparejamiento máximo. El teorema de Kőnig y Egerváry pasa a ser un caso particular de flujo máximo igual a corte mínimo.
• Emparejamiento estable. Cuando ambos lados se ordenan mutuamente por preferencia, Gale y Shapley (1962) demostraron que siempre existe un emparejamiento sin ninguna pareja que prefiera estar junta, y dieron el algoritmo que lo encuentra.

8. Coloración de aristas y horarios

Colorear las aristas de un grafo de modo que las aristas que comparten un extremo reciban colores distintos requiere al menos Δ colores, donde Δ es el grado máximo, porque las aristas de un vértice de grado máximo chocan todas entre sí. En grafos generales eso no siempre basta: un triángulo tiene Δ = 2 y necesita 3 colores, y Vizing demostró en 1964 que Δ + 1 siempre basta para grafos simples. Los grafos bipartitos nunca necesitan el color extra.

Teorema de coloración de aristas de Kőnig (1916). Las aristas de todo grafo bipartito, multigrafos incluidos, pueden colorearse con exactamente Δ colores.

Una forma de verlo usa el teorema de Hall: un grafo bipartito puede completarse con vértices y aristas extra hasta un multigrafo bipartito Δ-regular, que se divide entonces en Δ emparejamientos perfectos, uno por color. El ejemplo del artículo tiene Δ = 3, en los vértices A y F, y tres colores bastan.

Este es el teorema que hay detrás de los horarios escolares. Pon a los profesores en un lado y a los grupos en el otro, y dibuja una arista por cada clase que un profesor da a un grupo en una semana, con aristas paralelas cuando el mismo profesor ve al mismo grupo varias veces. Un color es una franja horaria, y una coloración de aristas propia es un horario en el que ningún profesor ni ningún grupo está en dos sitios a la vez. El teorema de Kőnig dice que el número de franjas necesarias es igual a la mayor carga semanal de un solo profesor o grupo, nunca más. Los horarios reales añaden aulas y preferencias que rompen la estructura bipartita limpia, y ahí es donde el problema se vuelve difícil, pero el núcleo de la asignación es una coloración de aristas bipartita.

9. La vista matricial

Pon primero los vértices de U y después los de W, y la matriz de adyacencia de un grafo bipartito se descompone en bloques. Los dos bloques diagonales son nulos, porque no hay aristas dentro de un lado:

A  =  [ 0    B ]            B es la matriz de biadyacencia de |U| × |W|
      [ Bᵀ   0 ]

B del ejemplo          B  D  F  H
                   A [ 1  1  1  0 ]
                   C [ 1  0  1  0 ]
                   E [ 0  1  0  1 ]
                   G [ 0  0  1  1 ]

El bloque fuera de la diagonal B, la matriz de biadyacencia, contiene toda la información, así que los programas guardan solo ese bloque. Una tabla de valoraciones de usuarios y artículos es exactamente una matriz de biadyacencia con pesos, y por eso los sistemas de recomendación son de forma natural problemas de grafos; los compromisos entre formatos de almacenamiento se tratan en representación de grafos.

La estructura en bloques deja una huella en los valores propios. Si un vector (x, y), dividido por lados, cumple A(x, y) = λ(x, y), entonces (x, −y) cumple la misma ecuación con −λ. Así que el espectro de un grafo bipartito es simétrico respecto a cero, y el recíproco también es cierto: un grafo cuyo espectro de adyacencia es simétrico respecto a cero es bipartito. Los valores propios del ejemplo son ±2,356, ±1,477, ±1,095 y ±0,262, en pares perfectos. Añade la arista de C a E y el emparejamiento de valores se rompe, con el mayor valor propio en 2,592 y el menor en −2,281. En un grafo conexo, un solo número lo decide: el grafo es bipartito exactamente cuando el opuesto de su mayor valor propio también es un valor propio. El ciclo de 5, por ejemplo, tiene el valor propio 2 pero no −2.

Los químicos lo descubrieron antes de que los teóricos de grafos le pusieran nombre. En 1940, Coulson y Rushbrooke demostraron que en los hidrocarburos alternantes, cuyos átomos de carbono se dividen en dos conjuntos con enlaces solo entre los conjuntos, los niveles de energía de los electrones π aparecen en pares situados simétricamente respecto al centro. Ese teorema de emparejamiento es la simetría espectral bipartita, enunciada para moléculas. La relación más amplia entre valores propios y estructura es el tema de la teoría espectral de grafos.

10. Dónde aparecen los grafos bipartitos

Los grafos bipartitos son el modelo honesto siempre que un sistema relaciona dos tipos distintos de objetos y nunca relaciona directamente dos objetos del mismo tipo.

Dos filas merecen una mirada más atenta. En teoría de códigos, Tanner introdujo en 1981 el grafo que hoy lleva su nombre, con los bits del código en un lado y las comprobaciones de paridad en el otro. Los códigos LDPC modernos (de comprobación de paridad de baja densidad), que se usan en Wi-Fi y 5G, se decodifican pasando mensajes de ida y vuelta por las aristas de exactamente este grafo bipartito. Y cualquier hipergrafo, donde una arista puede unir más de dos vértices, puede guardarse sin pérdida como un grafo de incidencia bipartito, lo que permite ejecutar sobre él los algoritmos de grafos habituales.

La fila de colaboración esconde un error de modelado frecuente. Los analistas suelen proyectar un grafo bipartito sobre uno de sus lados, uniendo a dos autores siempre que comparten un artículo. La proyección tira información. Tres autores que escribieron juntos un artículo y tres autores que escribieron por parejas tres artículos distintos producen el mismo triángulo en la proyección, aunque las colaboraciones subyacentes son completamente distintas. Mantén el grafo bipartito como fuente de verdad y proyecta solo para una pregunta concreta.

11. Fácil de comprobar, difícil de reparar

La bipartición está justo en la frontera entre problemas fáciles y difíciles, y vale la pena ver exactamente dónde cae la línea.

• Dos colores: tiempo lineal. La sección 5 lo resuelve en O(V + E).
• Tres colores: NP-completo. Decidir si un grafo puede colorearse de forma propia con tres colores es uno de los problemas NP-completos clásicos catalogados por Garey y Johnson. Un color más convierte una búsqueda en anchura en un problema sin ningún algoritmo polinómico conocido, como explica la guía de coloración de grafos.
• Reparar un grafo no bipartito: NP-difícil. Borrar el menor número de aristas para que un grafo sea bipartito equivale a conservar el mayor número de aristas que cruzan alguna división de los vértices, que es el problema del corte máximo, uno de los 21 problemas NP-completos de Karp de 1972. Borrar el menor número de vértices, el problema del transversal de ciclos impares, también es NP-difícil.

Así que el ciclo impar que devuelve la prueba es barato de encontrar, pero no dice nada sobre la forma más barata de eliminarlos todos. En el ejemplo con la arista extra, borrar C–E restablece la bipartición, pero en un grafo grande con muchos ciclos impares entrelazados, la reparación mínima es realmente difícil de calcular.

12. Errores comunes

13. Glosario

15. Referencias

Las definiciones, teoremas y atribuciones anteriores proceden de estas fuentes, ordenadas cronológicamente.

1. Mantel, W. (1907). "Problem 28." Wiskundige Opgaven 10, 60 a 61. La cota ⌊n²/4⌋ para grafos libres de triángulos.
2. Kőnig, D. (1916). "Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre." Mathematische Annalen 77(4), 453 a 465. El teorema de coloración de aristas para grafos bipartitos y los emparejamientos perfectos en grafos bipartitos regulares.
3. Kuratowski, K. (1930). "Sur le problème des courbes gauches en topologie." Fundamenta Mathematicae 15, 271 a 283. La planaridad y los grafos prohibidos K5 y K3,3.
4. Egerváry, J. (1931). "Matrixok kombinatorius tulajdonságairól." Matematikai és Fizikai Lapok 38, 16 a 28.
5. Kőnig, D. (1931). "Gráfok és mátrixok." Matematikai és Fizikai Lapok 38, 116 a 119. Junto con Egerváry, la igualdad entre emparejamientos máximos y recubrimientos por vértices mínimos.
6. Hall, P. (1935). "On Representatives of Subsets." Journal of the London Mathematical Society 10(1), 26 a 30.
7. Kőnig, D. (1936). Theorie der endlichen und unendlichen Graphen. Leipzig: Akademische Verlagsgesellschaft. El primer libro de texto de teoría de grafos, con la caracterización por ciclos impares.
8. Coulson, C. A. y Rushbrooke, G. S. (1940). "Note on the Method of Molecular Orbitals." Proceedings of the Cambridge Philosophical Society 36(2), 193 a 200. El teorema de emparejamiento para hidrocarburos alternantes.
9. Kuhn, H. W. (1955). "The Hungarian Method for the Assignment Problem." Naval Research Logistics Quarterly 2, 83 a 97.
10. Berge, C. (1957). "Two Theorems in Graph Theory." Proceedings of the National Academy of Sciences 43(9), 842 a 844. Los caminos aumentantes caracterizan los emparejamientos máximos.
11. Gale, D. y Shapley, L. S. (1962). "College Admissions and the Stability of Marriage." American Mathematical Monthly 69(1), 9 a 15.
12. Vizing, V. G. (1964). "On an Estimate of the Chromatic Class of a p-Graph." Diskretnyi Analiz 3, 25 a 30.
13. Karp, R. M. (1972). "Reducibility Among Combinatorial Problems." In Complexity of Computer Computations, 85 a 103. Nueva York: Plenum. El corte máximo entre los 21 problemas NP-completos.
14. Hopcroft, J. E. y Karp, R. M. (1973). "An n^5/2 Algorithm for Maximum Matchings in Bipartite Graphs." SIAM Journal on Computing 2(4), 225 a 231.
15. Garey, M. R. y Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. San Francisco: W. H. Freeman. La 3-colorabilidad de grafos como problema NP-completo.
16. Cvetković, D. M., Doob, M. y Sachs, H. (1980). Spectra of Graphs: Theory and Application. Nueva York: Academic Press. Los espectros simétricos caracterizan los grafos bipartitos.
17. Tanner, R. M. (1981). "A Recursive Approach to Low Complexity Codes." IEEE Transactions on Information Theory 27(5), 533 a 547.
18. Asratian, A. S., Denley, T. M. J. y Häggkvist, R. (1998). Bipartite Graphs and Their Applications. Cambridge Tracts in Mathematics 131. Cambridge: Cambridge University Press. Fuente de la atribución a 1916 del teorema de los ciclos impares.
19. Diestel, R. (2017). Graph Theory, 5.ª edición. Graduate Texts in Mathematics 173. Berlín: Springer.