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 y de números naturales, el problema pregunta si hay un gráfico bipartito simple etiquetado tal quees la secuencia de grados de este gráfico bipartito.
Soluciones
El problema pertenece a la clase de complejidad P . Esto se puede probar usando el teorema de Gale-Ryser , es decir, uno tiene que validar la exactitud de desigualdades.
Otras notaciones
El problema también se puede plantear en términos de matrices cero-uno . La conexión se puede ver si uno se da cuenta de que cada grafo bipartito tiene una matriz de biadjacencia donde las sumas de las columnas y las sumas de las filas corresponden a y . Entonces, el problema a menudo se denota mediante matrices 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 dados . Una tercera formulación es en términos de secuencias de grados de gráficos 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 gráfico dirigido. ¿Cuándo son los pares de números enteros no negativos (( a 1 , b 1 ), ..., ( a n , b n )) los pares de grado-grado de un gráfico dirigido etiquetado con como máximo un bucle por vértice?
Problemas relacionados
Problemas similares describen las secuencias de grados de gráficos simples y gráficos dirigidos simples . El primer problema es el llamado problema de realización de gráficos . El segundo se conoce como problema de realización de dígrafos . El problema de realización bipartita es equivalente a la pregunta, si existe un subgrafo bipartito etiquetado de un gráfico bipartito completo en una secuencia de grados dada. El problema de Hitchcock pide un subgrafo que minimice la suma de los costos en cada borde que se dan para el grafo bipartito completo. Otra generalización es el problema del factor f para gráficos bipartitos , es decir, para un gráfico bipartito dado, se busca un subgrafo que posea una cierta secuencia de grados. El problema del muestreo uniforme de un gráfico bipartito en una secuencia de grados fija es construir una solución para el problema de realización bipartita con la restricción adicional de que cada una de estas soluciones tiene la misma probabilidad. Este problema se mostró en FPTAS para secuencias regulares por Catherine Greenhill [1] (para gráficos bipartitos regulares con un factor 1 prohibido ) y para secuencias semi-regulares por Erdős et al. [2] El problema general sigue sin resolverse.
Referencias
- 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ática combinatoria . John Wiley e hijos .
- Greenhill, Catherine (2011). "Un polinomio enlazado en el tiempo de mezcla de una cadena de Markov para muestrear gráficos dirigidos regulares" . Revista electrónica de combinatoria . 18 (1): 234. arXiv : 1105.0457 . Código bibliográfico : 2011arXiv1105.0457G .
- Erdős, PL; Kiss, SZ; Miklós, I .; Soukup, Lajos (2015). "Recuento aproximado de realizaciones gráficas". PLOS ONE . 10 (7): e0131300. arXiv : 1301.7523 . Código bibliográfico : 2015PLoSO..1031300E . doi : 10.1371 / journal.pone.0131300 .
- ^ Greenhill (1997)
- ↑ Erdős (2013)