Gráfica bipartita

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

En el campo matemático de la teoría de grafos, un grafo bipartito (o bígrafo) es un grafo cuyos vértices se pueden dividir en dos conjuntos disjuntos e independientes $tu$ y $V$ , es decir, cada arista conecta un vértice en $tu$ uno en $V$ . Los conjuntos de vértices $tu$ y $V$ 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.

Los dos conjuntos pueden considerarse como una coloración del gráfico con dos colores: si uno colorea todos los nodos en $tu$ azul y todos los nodos en verde, cada borde tiene extremos de diferentes colores, como se requiere en el problema de coloración del gráfico. En cambio, tal coloración es imposible en el caso de un grafo 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 vértices de ambos colores, impidiendo que siendo asignado cualquiera de los dos colores. $V$ $tu$ $V$

A menudo se escribe $G=(U,V,E)$ para denotar un gráfico bipartito cuya partición tiene las partes $tu$ y $V$ , $mi$ denotando los bordes del gráfico. Si un gráfico bipartito no está conectado, puede tener más de una bipartición; en este caso, la $(U, V, E)$ notación es útil para especificar una bipartición particular que puede ser importante en una aplicación. Si $|U|=|V|$ , es decir, si los dos subconjuntos tienen la misma cardinalidad, entonces $GRAMO$ se llama un gráfico bipartito balanceado. Si todos los vértices del mismo lado de la bipartición tienen el mismo grado, entonces $GRAMO$ se llama biregular.

Ejemplos

Cuando se modelan las relaciones entre dos clases diferentes de objetos, los gráficos bipartitos suelen surgir 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.

Otro ejemplo en el que los gráficos bipartitos aparecen naturalmente 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 se puede modelar como un problema de conjunto dominante en un gráfico bipartito que tiene un vértice para cada tren y cada estación y una arista para cada par de una estación y un tren que se detiene en esa estación.

Un tercer ejemplo está en el campo académico de la numismática. Las monedas antiguas se fabrican utilizando 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.

Ejemplos más abstractos incluyen los siguientes:

Cada árbol es bipartito.
Los gráficos de ciclo con un número par de vértices son bipartitos.
Todo grafo plano cuyas caras tienen longitudes iguales es bipartito. 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.
El gráfico bipartito completo en m y n vértices, denotado por K _n,m es el gráfico bipartito $G=(U,V,E)$ , donde U y V son conjuntos disjuntos de tamaño m y n, respectivamente, y E conecta cada vértice en U con todos los vértices en V. Se sigue que K _m,n tiene mn aristas. Estrechamente relacionados con los gráficos bipartitos completos están los gráficos de corona, formados a partir de gráficos bipartitos completos eliminando los bordes de una combinación perfecta.
Los gráficos de hipercubo, los cubos parciales y los gráficos de mediana son bipartitos. En estos gráficos, los vértices pueden estar 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 los gráficos cuadrados forman ejemplos de gráficos medianos, y cada gráfico mediano es un cubo parcial.

Propiedades

Caracterización

Los gráficos bipartitos se pueden caracterizar de varias maneras diferentes:

Un grafo es bipartito si y solo si no contiene un ciclo impar.
Un grafo es bipartito si y sólo si es bicoloreable (es decir, su número cromático es menor o igual a 2).
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.
Un grafo es bipartito si y solo si el espectro del grafo es simétrico.

Teorema de Kőnig y gráficas perfectas

En gráficos bipartitos, el tamaño de la cobertura mínima de vértices es igual al tamaño de la coincidencia máxima; este es el teorema de Kőnig. Una forma alternativa y equivalente de este teorema es que el tamaño del máximo conjunto independiente más el tamaño del máximo emparejamiento es igual al número de vértices. En cualquier gráfico sin vértices aislados, el tamaño de la cobertura de borde mínima más el tamaño de una coincidencia máxima es igual al número de vértices. La combinación de esta igualdad con el teorema de Kőnig conduce al hecho de que, en grafos bipartitos, el tamaño de la cobertura mínima de aristas es igual al tamaño del conjunto máximo independiente, 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 gráficos perfectos: todo gráfico bipartito, el complemento de todo gráfico bipartito, el gráfico lineal de todo gráfico bipartito y el complemento del gráfico lineal de todo 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 grafos perfectos.La perfección de los complementos de los gráficos lineales de gráficos perfectos es otra reafirmación del teorema de Kőnig, y la perfección de los gráficos lineales en sí mismos es una reafirmación de un teorema anterior de Kőnig, que cada gráfico bipartito tiene una coloración de borde usando un número de colores igual a su grado máximo.

De acuerdo con el teorema del gráfico perfecto fuerte, los gráficos perfectos tienen una caracterización gráfica prohibida similar a la de los gráficos bipartitos: un gráfico es bipartito si y solo si no tiene un ciclo impar como subgráfico, y un gráfico es perfecto si y solo si tiene ningún ciclo impar o su complemento como un subgrafo inducido. Los gráficos bipartitos, los gráficos lineales de los gráficos bipartitos y sus complementos forman cuatro de las cinco clases básicas de gráficos perfectos utilizados en la demostración del teorema del gráfico perfecto fuerte.

La licenciatura

Para un vértice, el número de vértices adyacentes se llama grado del vértice y se denota $grado(v)$ . La fórmula de suma de grados para un gráfico bipartito establece que $sum_{v in V} deg(v) = sum_{u in U} deg(u) = |E|,.$

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 $tu$ y $V$ . Por ejemplo, el grafo bipartito completo K _3,5 tiene una secuencia de grados $(5,5,5),(3,3,3,3,3)$ . Los gráficos bipartitos isomorfos tienen la misma secuencia de grados. Sin embargo, la secuencia de grados, en general, no identifica de forma única un gráfico bipartito; en algunos casos, los gráficos bipartitos no isomorfos pueden tener la misma secuencia de grados.

El problema de realización bipartita es el problema de encontrar un gráfico bipartito simple con la secuencia de grados siendo dos listas dadas de números naturales. (Los ceros finales pueden ignorarse ya que se realizan de manera trivial agregando un número apropiado de vértices aislados al dígrafo).

Relación con hipergrafías y grafos dirigidos

La matriz de biadyacencia de un grafo bipartito $(U, V, E)$ es una matriz de tamaño (0,1) $|U|veces|V|$ que tiene un uno para cada par de vértices adyacentes y un cero para los vértices no adyacentes. Las matrices de biadyacencia se pueden usar para describir equivalencias entre gráficos bipartitos, hipergráficos y gráficos dirigidos.

Una hipergrafía es una estructura combinatoria que, como un gráfico 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. $(U, V, E)$ Se puede usar un gráfico bipartito para modelar una hipergrafía en la que U es el conjunto de vértices de la hipergrafía, V es el conjunto de hiperaristas y E contiene una arista desde un vértice de hipergrafía v hasta una arista de hipergrafía e exactamente cuando v es uno de los extremos de e. Bajo esta correspondencia, las matrices de biadyacencia de grafos bipartitos son exactamente las matrices de incidencia de las correspondientes hipergrafías. Como un 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.

Se puede usar una reinterpretación similar de matrices de adyacencia para mostrar una correspondencia uno a uno entre grafos dirigidos (en un número dado de vértices etiquetados, lo que permite bucles automáticos) 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 matriz (0,1) de tamaño $nveces n$ , que luego puede reinterpretarse como la matriz de adyacencia de un grafo bipartito con n vértices a cada lado de su bipartición. En esta construcción, el grafo bipartito es la doble cubierta bipartita del grafo dirigido.

Algoritmos

Probando el bipartidismo

Es posible probar si un gráfico es bipartito y devolver un ciclo bicolor (si es bipartito) o un ciclo impar (si no lo es) en tiempo lineal, utilizando la búsqueda en profundidad. La idea principal es asignar a cada vértice el color que difiere del color de su padre en el bosque de búsqueda primero en profundidad, asignando colores en un recorrido de preorden del bosque de búsqueda primero en profundidad. Esto necesariamente proporcionará una coloración bicolor del bosque expansivo 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 primero en profundidad, uno de los dos puntos finales de cada borde que no es de bosque es un ancestro del otro punto final, y cuando la búsqueda primero en profundidad descubre un borde de este tipo, debe verificar que estos dos vértices tengan colores diferentes. Si no lo hacen, luego, el camino en el bosque desde el antepasado hasta el descendiente, junto con el borde descolorido, forman un ciclo impar, que se devuelve desde el 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 colorearse correctamente y el algoritmo devuelve el coloreado junto con el resultado de que el gráfico es bipartito.

Alternativamente, se puede usar un procedimiento similar con la búsqueda primero en amplitud en lugar de la búsqueda primero en profundidad. Nuevamente, a cada nodo se le asigna el color opuesto a su padre en el bosque de búsqueda, en orden de anchura. 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 en anchura que conecta sus dos puntos finales con su ancestro común más bajo forman 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 gráfico es bipartito.

Para los gráficos de intersección de $norte$ 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 $O(nlog n)$ , aunque el gráfico en sí puede tener hasta ${ estilo de visualización O izquierda (n ^ {2} derecha)}$ bordes..

Ciclo impar transversal

La transversal de ciclo impar 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. El problema es manejable 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. El nombre ciclo impar transversalproviene 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 gráfico con el fin de obtener un gráfico bipartito, es necesario "golpear todos los ciclos impares", o encontrar un conjunto transversal de ciclo impar. En la ilustración, cada ciclo impar del gráfico contiene los vértices azules (los más inferiores), por lo que eliminar esos vértices elimina todos los ciclos impares y deja un gráfico bipartito.

El problema de bipartición de bordes es el problema algorítmico de eliminar la menor cantidad posible de bordes para hacer un gráfico bipartito y también es un problema importante en la modificación algorítmica de gráficos. Este problema también es tratable con parámetros fijos y se puede resolver en el tiempo ${ estilo de texto O izquierda (2 ^ {k} m ^ {2} derecha)}$ , donde k es el número de aristas a eliminar y m es el número de aristas en el gráfico de entrada.

Pareo

Una coincidencia en un gráfico es un subconjunto de sus bordes, ninguno de los cuales comparte un punto final. Los algoritmos de tiempo polinomial son conocidos por muchos problemas algorítmicos sobre coincidencias, incluida la coincidencia máxima (encontrar una coincidencia que use tantos bordes como sea posible), la coincidencia de peso máximo y el matrimonio estable. En muchos casos, los problemas de coincidencia son más fáciles de resolver en gráficos bipartitos que en gráficos no bipartitos, y muchos algoritmos de coincidencia, como el algoritmo de Hopcroft-Karp para coincidencia de cardinalidad máxima, funcionan correctamente solo en entradas bipartitas.

Como un ejemplo simple, suponga que un conjunto $PAGS$ de personas buscan trabajo entre un conjunto de $j$ trabajos, y no todas las personas son adecuadas para todos los trabajos. Esta situación se puede modelar como un gráfico bipartito $(P, J, E)$ donde un borde conecta a cada buscador de trabajo con cada trabajo adecuado. Un emparejamiento perfecto describe una forma de satisfacer simultáneamente a todos los buscadores 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 coincidencias perfectas. El Programa Nacional de Coincidencia de Residentes aplica métodos de comparación de gráficos para resolver este problema para los estudiantes de medicina de EE. UU. que buscan trabajo y trabajos de residencia en hospitales.

La descomposición de Dulmage-Mendelsohn es una descomposición estructural de gráficos bipartitos que es útil para encontrar coincidencias máximas.

Aplicaciones adicionales

Los gráficos bipartitos se utilizan ampliamente en la teoría de la codificación moderna, especialmente para decodificar las palabras clave 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 clave y los vértices del otro lado representan combinaciones de dígitos que se espera que sumen cero en una palabra clave sin errores. 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.

En informática, una red de Petri es una herramienta de modelado matemático utilizada en análisis y simulaciones de sistemas concurrentes. Un sistema se modela como un gráfico 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 simulaciones del sistema.

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 encuentran como máximo en un punto y cada dos puntos se conectan con una sola línea, los gráficos de Levi necesariamente no contienen ciclos de longitud cuatro, por lo que su circunferencia debe ser seis o más.

Contenido relacionado

Más resultados...