TEORÍA DE TÉRMINOS DE GRAFOS

En la teoría de grafos , se dice que un grafo conectado G está conectado a k -vértices (o k- conectado ) si tiene más de k vértices y permanece conectado cada vez que se eliminan menos de k vértices.

La conectividad de vértices , o simplemente conectividad , de un gráfico es la k más grande para la cual el gráfico está conectado a k -vértices.

Definiciones [ editar ]

Un gráfico con conectividad 4.

Un gráfico (que no sea un gráfico completo ) tiene conectividad k si k es del tamaño del subconjunto más pequeño de vértices, de modo que el gráfico se desconecta si los elimina. ^[1] Los gráficos completos no se incluyen en esta versión de la definición, ya que no se pueden desconectar eliminando vértices. El gráfico completo con n vértices tiene conectividad n  - 1, como lo implica la primera definición.

Una definición equivalente es que un gráfico con al menos dos vértices está conectado a k si, por cada par de vértices, es posible encontrar k caminos independientes de vértices que conectan estos vértices; ver el teorema de Menger ( Diestel 2005 , p. 55). Esta definición produce la misma respuesta, n  - 1, para la conectividad del gráfico completo K _n . ^[1]

Un gráfico 1-conectado se llama conectado ; un gráfico conectado a 2 se llama biconconectado . Un gráfico de 3 conectados se llama triconéctado.

Aplicaciones [ editar ]

Combinatoria poliédrica [ editar ]

El esqueleto 1- de cualquier politopo convexo k - dimensional forma un gráfico conectado k -vértice ( teorema de Balinski , Balinski 1961 ). Como un reverso parcial, el teorema de Steinitz establece que cualquier gráfico plano conectado a 3 vértices forma el esqueleto de un poliedro convexo .

En términos más generales, la conjetura de la celulación regular de 3 esferas afirma que cada gráfico conectado en 2 es el esqueleto unidimensional de un complejo CW regular en la esfera tridimensional ( http://twiki.di.uniroma1.it/pub/ Usuarios / SergioDeAgostino / DeAgostino.pdf ).

Complejidad computacional [ editar ]

La conectividad de vértices de un gráfico de entrada G se puede calcular en tiempo polinómico de la siguiente manera ^[2] considere todos los pares posibles$${\ displaystyle (s, t)}de nodos no adyacentes para desconectar, utilizando el teorema de Menger para justificar que el separador de tamaño mínimo para$${\ displaystyle (s, t)}es el número de rutas independientes de vértices por pares entre ellas, codifique la entrada duplicando cada vértice como un borde para reducir a un cálculo del número de rutas independientes de bordes por pares, y calcule el número máximo de tales rutas calculando el flujo máximo en el gráfico entre$${\ displaystyle s} y $${\ displaystyle t} con capacidad 1 para cada borde, observando que un flujo de $${\ displaystyle k}en este gráfico corresponde, por el teorema del flujo integral , a$${\ displaystyle k} caminos independientes de borde por pares desde $${\ displaystyle s} a $${\ displaystyle t}.

De Wikipedia, la enciclopedia libre

Saltar a navegaciónSaltar a búsqueda

Ejemplo de un gráfico bipartito sin ciclos.

Un gráfico bipartito completo con m = 5 yn = 3

En el campo matemático de la teoría de grafos , un gráfico bipartito (o bigraph ) es un gráfico cuyos vértices se pueden dividir en dos conjuntos separados e independientes. $${\ displaystyle U} y $${\ displaystyle V}de modo que cada borde conecta un vértice en$${\ displaystyle U} a uno en $${\ displaystyle V}. Conjuntos de vértices$${\ displaystyle U} y $${\ displaystyle V}generalmente se llaman las partes de la gráfica. De manera equivalente, un gráfico bipartito es un gráfico que no contiene ningún ciclo de longitud impar . ^[1] [2]

Los dos conjuntos $${\ displaystyle U} y $${\ displaystyle V}puede considerarse como una coloración del gráfico con dos colores: si uno colorea todos los nodos en$${\ displaystyle U} azul, y todos los nodos en $${\ displaystyle V}verde, cada borde tiene puntos finales de diferentes colores, como se requiere en el problema de coloración del gráfico. ^[3] [4] En contraste, tal coloración es imposible en el caso de un gráfico no bipartito, como un triángulo : después de que un nodo se colorea de azul y otro verde, el tercer vértice del triángulo se conecta a los vértices de ambos colores, evitando que se le asigne cualquier color.

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

Ejemplos [ editar ]

Cuando se modelan las relaciones entre dos clases diferentes de objetos, los gráficos bipartitos a menudo surgen naturalmente. 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 . ^[6]

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

Un tercer ejemplo es en el campo académico de la numismática. Las monedas antiguas se hacen usando dos impresiones positivas del diseño (el anverso y el reverso). Los gráficos que los numismáticos producen para representar la producción de monedas son gráficos bipartitos. ^[8]

Más ejemplos abstractos incluyen los siguientes:

• Cada árbol es bipartito. ^[4]
• Los gráficos de ciclo con un número par de vértices son bipartitos. ^[4]
• Cada gráfico plano cuyas caras tienen una longitud par es bipartito. ^[9] Casos especiales de esto son gráficos de cuadrícula y gráficos cuadrados , en los que cada cara interna consta de 4 bordes y cada vértice interno tiene cuatro o más vecinos. ^[10]
• El gráfico bipartito completa en m y n vértices, denotado por K _{n, m} es el gráfico bipartito$${\ displaystyle G = (U, V, E)}, Donde U y V son conjuntos disjuntos de tamaño m y n , respectivamente, y E se conecta cada vértice en U con todos los vértices en V . Se deduce que K _{m, n} tiene mn bordes. ^[11] Estrechamente relacionados con los gráficos bipartitos completos están los gráficos de corona , formados a partir de gráficos bipartitos completos al eliminar los bordes de una coincidencia perfecta . ^[12]
• Los gráficos de hipercubos , los cubos parciales y los gráficos medianos son bipartitos. En estos gráficos, los vértices pueden estar etiquetados por vectores de bits , de tal manera que dos vértices sean 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. ^[13]

Propiedades [ editar ]

Caracterización [ editar ]

Los gráficos bipartitos pueden caracterizarse de varias maneras diferentes:

• Un gráfico es bipartito si y solo si no contiene un ciclo impar . ^[14]
• Un gráfico es bipartito si y solo si tiene 2 colores (es decir, su número cromático es menor o igual que 2). ^[3]
• El espectro de un gráfico es simétrico si y solo si es un gráfico bipartito. ^[15]

Teorema de Kőnig y gráficos perfectos [ editar ]

En los gráficos bipartitos, el tamaño de la cubierta mínima del vértice es igual al tamaño de la coincidencia máxima ; Este es el teorema de Kőnig . ^[16] [17] Una forma alternativa y equivalente de este teorema es que el tamaño del conjunto independiente máximo más el tamaño de la coincidencia máxima es igual al número de vértices. En cualquier gráfico sin vértices aislados, el tamaño de la cubierta mínima del borde más el tamaño de una coincidencia máxima es igual al número de vértices. ^[18]La combinación de esta igualdad con el teorema de Kőnig lleva a los hechos de que, en gráficos bipartitos, el tamaño de la cubierta mínima del borde es igual al tamaño del conjunto independiente máximo, y el tamaño de la cubierta mínima del borde más el tamaño de la cubierta mínima del vértice es igual al número de vértices.

Otra clase de resultados relacionados se refiere a gráficos perfectos : cada gráfico bipartito, el complemento de cada gráfico bipartito, el gráfico lineal de cada gráfico bipartito y el complemento del gráfico lineal de cada 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 reformulación del teorema de Kőnig. Este fue uno de los resultados que motivó la definición inicial de gráficos perfectos. ^[19]La perfección de los complementos de los gráficos lineales de los gráficos perfectos es una nueva reformulación del teorema de Kőnig, y la perfección de los gráficos lineales en sí mismos es una reformulación de un teorema anterior de Kőnig, que cada gráfico bipartito tiene una coloración de borde usando una cantidad de colores igual a su grado máximo

De acuerdo con el fuerte teorema del gráfico perfecto , los gráficos perfectos tienen una caracterización de gráfico prohibida similar a la de los gráficos bipartitos: un gráfico es bipartito si y solo si no tiene un ciclo impar como subgrafo, y un gráfico es perfecto si y solo si tiene sin 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 prueba del teorema del gráfico perfecto fuerte. ^[20]

Grado [ editar ]

Para un vértice, el número de vértices adyacentes se denomina grado del vértice y se denota$${\ displaystyle \ deg (v)}. La fórmula de la suma de grados para un gráfico bipartito establece que

$${\ displaystyle \ 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 que contienen cada uno los grados de las dos partes. $${\ displaystyle U} y $${\ displaystyle V}. Por ejemplo, el gráfico bipartito completo K _3,5 tiene una secuencia de grados$${\ displaystyle (5,5,5), (3,3,3,3,3)}. Los gráficos bipartitos isomórficos tienen la misma secuencia de grados. Sin embargo, la secuencia de grados no identifica, en general, únicamente un gráfico bipartito; en algunos casos, los gráficos bipartitos no isomórficos pueden tener la misma secuencia de grados.

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

Relación con hipergrafías y gráficos dirigidos [ editar ]

La matriz de biadjacencia de un gráfico bipartito$${\ displaystyle (U, V, E)}es una matriz de tamaño (0,1)$${\ displaystyle | U | \ times | V |}que tiene uno para cada par de vértices adyacentes y un cero para vértices no adyacentes. ^[21] Las matrices de biadjacencia pueden usarse para describir equivalencias entre gráficos bipartitos, hipergrafías 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 cual las aristas pueden ser conjuntos arbitrarios de vértices en lugar de tener que tener exactamente dos puntos finales. Un gráfico bipartito$${\ displaystyle (U, V, E)}se puede usar para modelar una hipergrafía en la que U es el conjunto de vértices de la hipergrafía, V es el conjunto de hiperedificaciones y E contiene un borde desde un vértice de hipergrafía v hasta un borde de hipergrafía e exactamente cuando v es uno de los puntos finales de e . Bajo esta correspondencia, las matrices de biadjacencia de los gráficos bipartitos son exactamente las matrices de incidencia de las hipergrafías correspondientes. Como un caso especial de esta correspondencia entre gráficos bipartitos e hipergrafías, cualquier multigrafo(un gráfico en el que puede haber dos o más aristas entre los mismos dos vértices) puede interpretarse como una hipergrafía en la que algunas hiperedges tienen conjuntos iguales de puntos finales, y representarse por un gráfico bipartito que no tiene múltiples adyacencias y en el que vértices en un lado de la bipartición todos tienen grado dos. ^[22]

Se puede utilizar una reinterpretación similar de las matrices de adyacencia para mostrar una correspondencia biunívoca entre los gráficos dirigidos (en un número determinado de vértices etiquetados, permitiendo bucles automáticos) y los gráficos bipartitos equilibrados, con el mismo número de vértices en ambos lados de La bipartición. Para, la matriz de adyacencia de un gráfico dirigido con n vértices puede ser cualquier matriz (0,1) de tamaño$${\ displaystyle n \ times n}, que luego se puede reinterpretar como la matriz de adyacencia de un gráfico bipartito con n vértices en cada lado de su bipartición. ^[23] En esta construcción, el gráfico bipartito es la doble cubierta bipartita del gráfico dirigido.

Algoritmos [ editar ]

Prueba de bipartidismo [ editar ]

Es posible probar si un gráfico es bipartito y devolver un ciclo de dos colores (si es bipartito) o un ciclo impar (si no lo es) en tiempo lineal , utilizando la búsqueda de profundidad primero . La idea principal es asignar a cada vértice el color que difiere del color de su padre en el bosque de búsqueda de profundidad, asignando colores en un recorrido previo al pedido del bosque de búsqueda de profundidad. Esto necesariamente proporcionará una doble coloración del bosque que se extiendeque consiste en los bordes que conectan los vértices a sus padres, pero puede no colorear adecuadamente algunos de los bordes no forestales. En un bosque de búsqueda de profundidad primero, uno de los dos puntos finales de cada borde no forestal es un ancestro del otro punto final, y cuando la primera búsqueda de profundidad descubre un borde de este tipo, debe verificar 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 el borde descolorido, forman un ciclo extraño, 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 ser coloreado adecuadamente, y el algoritmo devuelve el color junto con el resultado de que el gráfico es bipartito. ^[24]

Alternativamente, se puede usar un procedimiento similar con la búsqueda de amplitud en lugar de la búsqueda de profundidad primero. Nuevamente, a cada nodo se le da el color opuesto a su padre en el bosque de búsqueda, en orden de amplitud. Si, cuando un vértice está coloreado, existe un borde que lo conecta a un vértice previamente coloreado con el mismo color, entonces este borde junto con los caminos en el bosque de búsqueda de amplitud que conecta sus dos puntos finales a su ancestro común más bajo forma un ciclo impar Si el algoritmo termina sin encontrar un ciclo extraño de esta manera, entonces debe haber encontrado un color adecuado y puede concluir con seguridad que el gráfico es bipartito. ^[25]

Para los gráficos de intersección de$${\ displaystyle n} 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 un ciclo impar en el tiempo$${\ displaystyle O (n \ log n)}, aunque el gráfico en sí mismo puede tener hasta $${\ displaystyle O (n ^ {2})}bordes ^[26]

Ciclo impar transversal [ editar ]

Artículo principal: ciclo impar transversal

Una gráfica con un ciclo impar transversal de tamaño 2: la eliminación de los dos vértices inferiores azules deja una gráfica bipartita.

El ciclo transversal impar es un problema algorítmico NP-completo que pregunta, dado un gráfico  G  = ( V , E ) y un número  k , si existe un conjunto de  k vértices cuya eliminación de  G causaría que el gráfico resultante sea bipartito. ^[27] El problema es el parámetro fijo manejable , lo que significa que hay un algoritmo cuyo tiempo de ejecución puede estar limitado por una función polinómica del tamaño del gráfico multiplicado por una función mayor de k . ^[28] El nombre ciclo impar transversalproviene del hecho de que un gráfico 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, uno necesita "acertar todos los ciclos impares", o encontrar un conjunto transversal llamado ciclo impar . En la ilustración, cada ciclo impar en el gráfico contiene los vértices azules (los más bajos), por lo que eliminar esos vértices mata todos los ciclos impares y deja un gráfico bipartito.

El problema de la bipartición de bordes es el problema algorítmico de eliminar la menor cantidad posible de bordes para hacer que un gráfico sea bipartito y también es un problema importante en los algoritmos de modificación de gráficos. Este problema también es manejable con parámetros fijos , y puede resolverse en el tiempo O (2 ^k  m ² ), ^[29] donde  k es el número de bordes a eliminar  ym es el número de bordes en el gráfico de entrada.

Coincidencia [ editar ]

Artículo principal: Emparejamiento (teoría de grafos)

Una coincidencia en un gráfico es un subconjunto de sus bordes, ninguno de los cuales comparte un punto final. Los algoritmos de tiempo polinómico son conocidos por muchos problemas algorítmicos en las 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 . ^[30] En muchos casos, los problemas de coincidencia son más fáciles de resolver en gráficos bipartitos que en gráficos no bipartitos, ^[31] y muchos algoritmos de coincidencia como el algoritmo Hopcroft-Karp para la coincidencia de cardinalidad máxima ^[32] funcionan correctamente solo en entradas bipartitas .

Como un simple ejemplo, supongamos que un conjunto $${\ displaystyle P} de las personas buscan trabajo entre un conjunto de $${\ displaystyle J}trabajos, con no todas las personas adecuadas para todos los trabajos. Esta situación se puede modelar como un gráfico bipartito$${\ displaystyle (P, J, E)}donde un borde conecta a cada buscador de trabajo con cada trabajo adecuado. ^[33] Una combinación perfecta describe una manera de satisfacer simultáneamente a todos los solicitantes de empleo y llenar todos los trabajos; El teorema de matrimonio de Hall proporciona una caracterización de los gráficos bipartitos que permiten combinaciones perfectas. El Programa nacional de comparación de residentes aplica métodos de comparación de gráficos para resolver este problema para los solicitantes de empleo de estudiantes de medicina de EE. UU . Y los trabajos de residencia en hospitales . ^[34]

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

Aplicaciones adicionales [ editar ]

Los gráficos bipartitos se usan ampliamente en la teoría de codificación moderna , especialmente para decodificar las palabras de código 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 de código, y los vértices del otro lado representan combinaciones de dígitos que se espera que sumen cero en una palabra de código sin errores. ^[36] Un gráfico de factores es una red de creencias estrechamente relacionada utilizada para la decodificación probabilística de LDPC y códigos turbo . ^[37]

En informática, una red de Petri es una herramienta de modelado matemático utilizada en el análisis y simulación 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 "evento" que generan y / o consumen recursos. Existen restricciones adicionales en los nodos y bordes que limitan 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 tiempo que permiten una fácil implementación de simulaciones del sistema. ^[38]

En geometría proyectiva , los gráficos de Levi son una forma de gráfico bipartito utilizado para modelar las incidencias entre puntos y líneas en una configuración . En correspondencia con la propiedad geométrica de los puntos y líneas que cada dos líneas se encuentran como máximo en un punto y cada dos puntos están conectados con una sola línea, los gráficos de Levi no contienen necesariamente ningún ciclo de longitud cuatro, por lo que su circunferencia debe ser seis o más . ^[39]

Ver también [ editar ]

• Dimensión bipartita , el número mínimo de gráficos bipartitos completos cuya unión es el gráfico dado
• Doble cubierta bipartita , una forma de transformar cualquier gráfico en un gráfico bipartito duplicando sus vértices
• Matroid bipartito , una clase de matroides que incluye los matroides gráficos de gráficos bipartitos
• Proyección de red bipartita , una técnica de ponderación para comprimir información sobre redes bipartitas
• Gráfico bipartito convexo , un gráfico bipartito cuyos vértices se pueden ordenar para que los vecindarios de vértices sean contiguos
• Gráfico multipartito , una generalización de gráficos bipartitos a más de dos subconjuntos de vértices
• Gráfico de paridad , una generalización de gráficos bipartitos en la que cada dos rutas inducidas entre los mismos dos puntos tienen la misma paridad
• Gráfico cuasi-bipartito , un tipo de instancia de problema del árbol Steiner en el que los terminales forman un conjunto independiente, lo que permite algoritmos de aproximación que generalizan los de los gráficos bipartitos
• Gráfico dividido , un gráfico en el que los vértices se pueden dividir en dos subconjuntos, uno de los cuales es independiente y el otro es una camarilla
• Problema de Zarankiewicz sobre el número máximo de aristas en un gráfico bipartito con subgrafías prohibidas