Problema de realización bipartita

El problema de realización bipartita es un problema de decisión clásico en la teoría de grafos , una rama de la combinatoria . Dadas dos secuencias finitas${\displaystyle (a_{1},\dots ,a_{n})}$y${\displaystyle (b_{1},\dots ,b_{m})}$de números naturales con${\displaystyle m\leq n}$, el problema pregunta si existe un grafo bipartito simple etiquetado tal que${\displaystyle (a_{1},\dots ,a_{n}),(b_{1},\dots ,b_{m})}$es la secuencia de grados de este grafo bipartito.

El problema pertenece a la clase de complejidad P. Esto se puede demostrar utilizando el teorema de Gale-Ryser , es decir, hay que validar la corrección de${\displaystyle n}$desigualdades .

El problema también puede plantearse en términos de matrices binarias . La conexión puede verse si uno se da cuenta de que cada grafo bipartito tiene una matriz de biadyacencia donde las sumas de las columnas y las sumas de las filas corresponden a${\displaystyle (a_{1},\ldots ,a_{n})}$y${\displaystyle (b_{1},\ldots ,b_{m})}$El problema se suele denotar mediante matrices binarias (0-1) para sumas de filas y columnas dadas . En la literatura clásica, el problema se planteaba a veces en el contexto de tablas de contingencia mediante tablas de contingencia con marginales dadas . Una tercera formulación se basa en secuencias de grados de grafos dirigidos simples con como máximo un bucle por vértice . En este caso, la matriz se interpreta como la matriz de adyacencia de dicho grafo dirigido. ¿Cuándo son pares de enteros no negativos ((a₁, b₁ ), ..., (aₙ, bₙ ) ) los _pares de grado de entrada - _grado de _{salida de} un grafo dirigido etiquetado con como máximo un bucle por vértice?  

Problemas similares describen las secuencias de grados de grafos simples y grafos dirigidos simples. El primer problema es el llamado problema de realización de grafos , y el segundo se conoce como el problema de realización de digrafos . El problema de realización bipartita es equivalente a la pregunta de si existe un subgrafo bipartito etiquetado de un grafo bipartito completo con una secuencia de grados dada. El problema de Hitchcock pide encontrar un subgrafo que minimice la suma de los costos en cada arista dados para el grafo bipartito completo. Una generalización adicional es el problema del factor f para grafos bipartitos , es decir, para un grafo bipartito dado se busca un subgrafo que posea una cierta secuencia de grados. El problema del muestreo uniforme de un grafo bipartito con una secuencia de grados fija consiste en construir una solución para el problema de realización bipartita con la restricción adicional de que cada solución tenga la misma probabilidad. Se demostró que este problema está en FPTAS para secuencias regulares por Catherine Greenhill ^{[ 1 ]} (para grafos bipartitos regulares con un 1-factor prohibido ) y para secuencias semi-regulares por Erdős et al. ^{[ 2 ]} El problema general aún no está resuelto.

• Gale, D. (1957). "Un teorema sobre flujos en redes" . Pacific J. Math . 7 (2): 1073– 1082. doi : 10.2140/pjm.1957.7.1073 .
• Ryser, HJ (1963). Matemáticas combinatorias . John Wiley & Sons .
• Greenhill, Catherine (2011). "Una cota polinomial para el tiempo de mezcla de una cadena de Markov para el muestreo de grafos dirigidos regulares" . Electronic Journal of Combinatorics . 18 (1): 234. arXiv : 1105.0457 . Bibcode : 2011arXiv1105.0457G . doi : 10.37236/721 . S2CID 11309590 . 
• Erdős, PL; Kiss, SZ; Miklós, I.; Soukup, Lajos (2015). "Conteo aproximado de realizaciones gráficas" . PLOS ONE . 10 (7) e0131300. arXiv : 1301.7523 . Bibcode : 2015PLoSO..1031300E . doi : 10.1371/journal.pone.0131300 . PMC 4498913. PMID 26161994 .  
• Erdős, Péter L.; Király, Zoltán; Miklós, István (mayo de 2013). "Sobre las distancias de intercambio de diferentes realizaciones de una secuencia de grados gráfica" (PDF) . Combinatoria, Probabilidad y Computación . 22 (3): 366– 383. arXiv : 1205.2842 . doi : 10.1017/S0963548313000096 . S2CID 5643528 .