TEORÍA DE TÉRMINOS DE GRAFOS

De Wikipedia, la enciclopedia libre

Saltar a navegaciónSaltar a búsqueda

Un gráfico con 16 vértices y 6 puentes (resaltados en rojo)

Un gráfico conectado no dirigido sin bordes de puente

En la teoría de grafos , un puente , istmo , borde de corte o arco de corte es un borde de un gráfico cuya eliminación aumenta su número de componentes conectados . ^{[1] De manera} equivalente, un borde es un puente si y solo si no está contenido en ningún ciclo . Se dice que un gráfico no tiene puentes o está libre de istmo si no contiene puentes.

Otro significado de "puente" aparece en el término puente de un subgrafo . Si H es un subgrafo de G , un puente de H en G es un subgrafo máxima de G que no está contenido en H y no está separado por H .

Árboles y bosques [ editar ]

Un gráfico con $${\ displaystyle n} los nodos pueden contener como máximo $${\ displaystyle n-1}puentes, ya que agregar bordes adicionales debe crear un ciclo. Los gráficos con exactamente$${\ displaystyle n-1}los puentes son exactamente los árboles , y los gráficos en los que cada borde es un puente son exactamente los bosques .

En cada gráfico no dirigido, hay una relación de equivalencia en los vértices según la cual dos vértices se relacionan entre sí siempre que haya dos caminos de borde disyuntivo que los conectan. (Cada vértice está relacionado con sí mismo a través de dos caminos de longitud cero, que son idénticos pero no obstante disyunto de borde.) Las clases de equivalencia de esta relación se denominan componentes conectados a 2 bordes , y los puentes del gráfico son exactamente los bordes cuyos Los puntos finales pertenecen a diferentes componentes. El árbol de bloques de puente del gráfico tiene un vértice para cada componente no trivial y un borde para cada puente. ^[2]

Relación con la conectividad de vértices [ editar ]

Los puentes están estrechamente relacionados con el concepto de vértices de articulación , vértices que pertenecen a cada ruta entre algún par de otros vértices. Los dos puntos finales de un puente son vértices de articulación a menos que tengan un grado de 1, aunque también puede ser posible que un borde sin puente tenga dos vértices de articulación como puntos finales. Análogamente a los gráficos sin puente que están conectados a 2 bordes, los gráficos sin vértices de articulación están conectados a 2 vértices .

En un gráfico cúbico , cada vértice de corte es un punto final de al menos un puente.

Gráficos sin puente [ editar ]

Un gráfico sin puente es un gráfico que no tiene ningún puente. Las condiciones equivalentes son que cada componente conectado del gráfico tiene una descomposición del oído abierto , ^[3] que cada componente conectado está conectado a 2 bordes , o (según el teorema de Robbins ) que cada componente conectado tiene una fuerte orientación . ^[3]

Un problema abierto importante que involucra puentes es la conjetura del ciclo de doble cubierta , debido a Seymour y Szekeres (1978 y 1979, independientemente), que establece que cada gráfico sin puente admite un conjunto de ciclos simples que contienen cada borde exactamente dos veces. ^[4]

El algoritmo de búsqueda de puentes de Tarjan [ editar ]

Robert Tarjan describió el primer algoritmo de tiempo lineal para encontrar los puentes en un gráfico en 1974. ^[5] Realiza los siguientes pasos:

• Encuentra un bosque de$${\ displaystyle G}
• Crea un bosque enraizado $${\ displaystyle F} del árbol de expansión
• Atravesar el bosque $${\ displaystyle F}en preordenar y numerar los nodos. Los nodos principales en el bosque ahora tienen números más bajos que los nodos secundarios.
• Para cada nodo $${\ displaystyle v} en preordenar (denotando cada nodo usando su número de preorden), haga:
  • Calcule la cantidad de descendientes del bosque $${\ displaystyle ND (v)} para este nodo, agregando uno a la suma de los descendientes de sus hijos.
  • Calcular $${\ displaystyle L (v)}, la etiqueta de pedido más bajo accesible desde $${\ displaystyle v} por una ruta para la cual todos menos el último borde permanecen dentro del subárbol enraizado $${\ displaystyle v}. Este es el mínimo del conjunto que consiste en la etiqueta de pedido previo de$${\ displaystyle v}, de los valores de $${\ displaystyle L (w)} en los nodos hijos de $${\ displaystyle v} y de las etiquetas de preorden de nodos accesibles desde $${\ displaystyle v} por bordes que no pertenecen a $${\ displaystyle F}.
  • Del mismo modo, calcular $${\ displaystyle H (v)}, la etiqueta de preorden más alta alcanzable por una ruta para la cual todos menos el último borde permanecen dentro del subárbol enraizado en $${\ displaystyle v}. Este es el máximo del conjunto que consiste en la etiqueta de preorden de$${\ displaystyle v}, de los valores de $${\ displaystyle H (w)} en los nodos hijos de $${\ displaystyle v} y de las etiquetas de preorden de nodos accesibles desde $${\ displaystyle v} por bordes que no pertenecen a $${\ displaystyle F}.
  • Para cada nodo $${\ displaystyle w} con nodo padre $${\ displaystyle v}, Si $${\ displaystyle L (w) = w} y {\ displaystyle H (w)  entonces el borde de $${\ displaystyle v} a $${\ displaystyle w} Es un puente.

Búsqueda de puentes con descomposiciones en cadena [ editar ]

Un algoritmo de búsqueda de puente muy simple ^[6] utiliza descomposiciones en cadena . Las descomposiciones en cadena no solo permiten calcular todos los puentes de un gráfico, sino que también permiten leer cada vértice de corte de G (y el árbol de corte de bloque de G ), lo que proporciona un marco general para probar 2 vértices y 2 vértices -conectividad (que se extiende a las pruebas de conectividad de 3 bordes y 3 vértices en tiempo lineal).

Las descomposiciones en cadena son descomposiciones especiales del oído que dependen de un árbol DFS T de G y se pueden calcular de manera muy simple: deje que cada vértice se marque como no visitado. Para cada vértice v en números DFS ascendentes 1 ... n , atraviese cada respaldo (es decir, cada borde que no esté en el árbol DFS) que incide en v y siga el camino de los bordes de los árboles hasta la raíz de T , deteniéndose en El primer vértice marcado como visitado. Durante tal recorrido, cada vértice atravesado se marca como visitado. Por lo tanto, un recorrido se detiene a más tardar en v y forma una ruta o ciclo dirigido, comenzando con v; llamamos a este camino o ciclo una cadena. La i ésima cadena encontrada por este procedimiento se denomina C _i . C = C ₁ , C ₂ , ... es entonces una degradación de las cadenas de G .

Los siguientes caracterizaciones luego permitir a leer de varias propiedades de G de C de manera eficiente, incluyendo todos los puentes de G . ^[6] Sea C una descomposición en cadena de un gráfico simple conectado G = (V, E) .

1. G está conectado-2-borde si y sólo si las cadenas en C partición E .
2. Un borde e en G es un puente si y sólo si e no está contenida en cualquier cadena en C .
3. Si G está conectado a 2 bordes, C es una descomposición del oído .
4. G está conectada a 2-vértice si y sólo si G tiene grado mínimo 2 y C ₁ es el único ciclo en C .
5. Un vértice v en un gráfico G conectado a 2 bordes es un vértice cortado si y solo si v es el primer vértice de un ciclo en C - C ₁ .
6. Si G está conectado a 2 vértices, C es una descomposición del oído abierto .

En la teoría de grafos , el problema de prueba de planaridad es el problema algorítmico de probar si un gráfico dado es un gráfico plano (es decir, si se puede dibujar en el plano sin intersecciones de bordes). Este es un problema bien estudiado en informática para el cual han surgido muchos algoritmos prácticos, muchos de los cuales se aprovechan de nuevas estructuras de datos . La mayoría de estos métodos funcionan en tiempo O ( n ) (tiempo lineal), donde n es el número de aristas (o vértices) en el gráfico, que es asintóticamente óptimo. En lugar de ser un solo valor booleano, la salida de un algoritmo de prueba de planaridad puede ser una incrustación de gráfico plano , si el gráfico es plano, o un obstáculo para la planaridad como un subgrafo de Kuratowski si no lo es.

Criterios de planaridad [ editar ]

Los algoritmos de prueba de planaridad generalmente aprovechan los teoremas de la teoría de grafos que caracterizan el conjunto de grafos planos en términos que son independientes de los dibujos de grafos. Éstos incluyen

• El teorema de Kuratowski de que un gráfico es plano si y solo si no contiene un subgrafo que es una subdivisión de K ₅ (el gráfico completo en cinco vértices ) o K _3,3 (el gráfico de utilidad , un gráfico bipartito completo en seis vértices, tres de los cuales se conectan a cada uno de los otros tres).
• El teorema de Wagner de que un gráfico es plano si y solo si no contiene un menor (subgrafo de una contracción) que es isomorfo a K ₅ o K _3,3 .
• El criterio de planaridad Fraysseix – Rosenstiehl , que caracteriza los gráficos planos en términos de un ordenamiento izquierda-derecha de los bordes en un árbol de búsqueda de profundidad primero .

El criterio de planaridad de Fraysseix-Rosenstiehl se puede usar directamente como parte de algoritmos para pruebas de planaridad, mientras que los teoremas de Kuratowski y Wagner tienen aplicaciones indirectas: si un algoritmo puede encontrar una copia de K ₅ o K _3,3 dentro de un gráfico dado, puede ser asegúrese de que el gráfico de entrada no sea plano y regrese sin cálculo adicional.

Otros criterios de planaridad, que caracterizan los gráficos planos matemáticamente pero son menos centrales para los algoritmos de prueba de planaridad, incluyen el criterio de planaridad de Whitney de que un gráfico es plano si y solo si su matroide gráfico también es cográfico, el criterio de planaridad de Mac Lane que caracteriza los gráficos planos por las bases de sus espacios de ciclo , el teorema de Schnyder que caracteriza los gráficos planos por la dimensión del orden de un orden parcial asociado , y el criterio de planaridad de Colin de Verdière utilizando la teoría de los gráficos espectrales .

Algoritmos [ editar ]

Método de adición de ruta [ editar ]

El clásico Además trayectoria método de Hopcroft y Tarjan ^[1] fue el primero publicado lineal en tiempo algoritmo de prueba planaridad en 1974. implementación Una de Hopcroft y Tarjan algoritmo 's se proporciona en la Biblioteca de tipos de datos eficiente y Algoritmos por Mehlhorn , Mutzel y Näher ^[2] [3] . ^[4] En 2012, Taylor ^[5] extendió este algoritmo para generar todas las permutaciones de orden de borde cíclico para incrustaciones planas de componentes biconnectados.

Método de adición de vértices [ editar ]

Los métodos de adición de vértices funcionan manteniendo una estructura de datos que representa las posibles incorporaciones de un subgrafo inducido del gráfico dado, y agregando vértices uno a la vez a esta estructura de datos. Estos métodos comenzaron con un método O ( n ² ) ineficiente concebido por Lempel , Even y Cederbaum en 1967. ^[6] Fue mejorado por Even y Tarjan, quienes encontraron una solución de tiempo lineal para el paso de numeración s , t , ^{[ 7]} y por Booth y Lueker , quienes desarrollaron el árbol PQestructura de datos. Con estas mejoras, es de tiempo lineal y supera el método de adición de ruta en la práctica. ^[8] Este método también se extendió para permitir que una incrustación plana (dibujo) se calcule eficientemente para un gráfico plano. ^[9] En 1999, Shih y Hsu simplificaron estos métodos usando el árbol de PC (una variante no enraizada del árbol PQ) y un recorrido postorder del árbol de búsqueda de profundidad de los vértices. ^[10]

Método de adición de bordes [ editar ]

En 2004, John Boyer y Wendy Myrvold ^[11] desarrollaron un algoritmo O ( n ) simplificado , inspirado originalmente en el método del árbol PQ, que elimina el árbol PQ y usa adiciones de bordes para calcular una inserción plana, si es posible. De lo contrario, se calcula una subdivisión de Kuratowski (de K ₅ o K _3,3 ). Este es uno de los dos algoritmos actuales de última generación (el otro es el algoritmo de prueba de planaridad de de Fraysseix, de Mendez y Rosenstiehl ^[12] [13] ). Ver ^[14]para una comparación experimental con una versión preliminar de la prueba de planaridad de Boyer y Myrvold. Además, la prueba de Boyer-Myrvold se extendió para extraer múltiples subdivisiones de Kuratowski de un gráfico de entrada no plano en un tiempo de ejecución linealmente dependiente del tamaño de salida. ^[15] El código fuente para la prueba de planaridad ^[16] [17] y la extracción de múltiples subdivisiones de Kuratowski ^[16] está disponible públicamente. Williamson desarrolló los algoritmos que ubican una subgrafía de Kuratowski en tiempo lineal en vértices en la década de 1980. ^[18]

Método de secuencia de construcción [ editar ]

Un método diferente utiliza una construcción inductiva de gráficos conectados a 3 para construir de forma incremental incrustaciones planas de cada componente de G conectado a 3 (y, por lo tanto, una incrustación plana de G ). ^[19] La construcción comienza con K ₄y se define de tal manera que cada gráfico intermedio en el camino hacia el componente completo está nuevamente conectado a 3. Dado que tales gráficos tienen una incrustación única (hasta el volteo y la elección de la cara externa), el siguiente gráfico más grande, si aún es plano, debe ser un refinamiento del gráfico anterior. Esto permite reducir la prueba de planaridad a solo probar para cada paso si el siguiente borde agregado tiene ambos extremos en la cara externa de la incrustación actual. Si bien esto es conceptualmente muy simple (y proporciona un tiempo de ejecución lineal), el método en sí mismo tiene la complejidad de encontrar la secuencia de construcción.

De Wikipedia, la enciclopedia libre

Saltar a navegaciónSaltar a búsqueda

En este gráfico, el triángulo rojo formado por los vértices 1, 2 y 5 es un ciclo periférico: los cuatro bordes restantes forman un solo puente. Sin embargo, el pentágono 1–2–3–4–5 no es periférico, ya que los dos bordes restantes forman dos puentes separados.

En la teoría de gráficos , un ciclo periférico (o circuito periférico ) en un gráfico no dirigido es, intuitivamente, un ciclo que no separa ninguna parte del gráfico de ninguna otra parte. Los ciclos periféricos (o, como se los llamó inicialmente, polígonos periféricos , porque Tutte llamó a los ciclos "polígonos") fueron estudiados por primera vez por Tutte (1963) , y juegan papeles importantes en la caracterización de gráficos planos y en la generación de espacios de ciclo de gráficos no planos. .

Definiciones [ editar ]

Un ciclo periférico $${\ displaystyle C} en un gráfico $${\ displaystyle G} se puede definir formalmente en una de varias formas equivalentes:

• $${\ displaystyle C}es periférico si es un ciclo simple en un gráfico conectado con la propiedad que, por cada dos aristas$${\ displaystyle e_ {1}} y $${\ displaystyle e_ {2}} en $${\ displaystyle G \ setminus C}, existe un camino en $${\ displaystyle G} eso comienza con $${\ displaystyle e_ {1}}, termina con $${\ displaystyle e_ {2}}y no tiene vértices interiores pertenecientes a $${\ displaystyle C}. ^[2]
• $${\ displaystyle C}es periférico si es un ciclo inducido con la propiedad de que el subgrafo$${\ displaystyle G \ setminus C} formado al eliminar los bordes y vértices de $${\ displaystyle C}está conectado. ^[3]
• Si $${\ displaystyle C} es cualquier subgrafo de $${\ displaystyle G}, un puente ^[4] de$${\ displaystyle C} es un subgrafo mínimo $${\ displaystyle B} de $${\ displaystyle G} eso es un filo disjunto de $${\ displaystyle C} y que tiene la propiedad de que todos sus puntos de conexión (vértices adyacentes a los bordes en ambos $${\ displaystyle B} y $${\ displaystyle G \ setminus B}) pertenece a $${\ displaystyle C}. ^[5] Un ciclo simple$${\ displaystyle C}es periférico si tiene exactamente un puente. ^[6]

La equivalencia de estas definiciones no es difícil de ver: un subgráfico conectado de $${\ displaystyle G \ setminus C} (junto con los bordes que lo unen $${\ displaystyle C}), o un acorde de un ciclo que hace que no se induzca, en cualquier caso debe ser un puente, y también debe ser una clase de equivalencia de la relación binaria en los bordes en los que dos bordes están relacionados si son los extremos de un camino sin vértices interiores en$${\ displaystyle C}. ^[7]

Propiedades [ editar ]

Los ciclos periféricos aparecen en la teoría de los gráficos poliédricos , es decir, los gráficos planos conectados a 3 vértices . Para cada grafo plano$${\ displaystyle G}y cada incrustación plana de $${\ displaystyle G}, las caras de la incrustación que son ciclos inducidos deben ser ciclos periféricos. En un gráfico poliédrico, todas las caras son ciclos periféricos, y cada ciclo periférico es una cara. ^[8] Se deduce de este hecho que (hasta la equivalencia combinatoria, la elección de la cara externa y la orientación del plano) cada gráfico poliédrico tiene una incrustación plana única. ^[9]

En los gráficos planos, el espacio del ciclo es generado por las caras, pero en los gráficos no planos los ciclos periféricos juegan un papel similar: por cada gráfico finito conectado a 3 vértices, el espacio del ciclo es generado por los ciclos periféricos. ^[10] El resultado también puede extenderse a gráficos localmente finitos pero infinitos. ^[11] En particular, se deduce que se garantiza que los gráficos de 3 conectados contienen ciclos periféricos. Existen gráficos conectados a 2 que no contienen ciclos periféricos (un ejemplo es el gráfico bipartito completo $${\ displaystyle K_ {2,4}}, para el cual cada ciclo tiene dos puentes) pero si un gráfico de 2 conectados tiene un grado mínimo de tres, entonces contiene al menos un ciclo periférico. ^[12]

Los ciclos periféricos en gráficos conectados a 3 pueden calcularse en tiempo lineal y se han utilizado para diseñar pruebas de planaridad. ^[13] También se extendieron a la noción más general de descomposición del oído sin separación. En algunos algoritmos para probar la planaridad de los gráficos, es útil encontrar un ciclo que no sea periférico, para dividir el problema en subproblemas más pequeños. En un gráfico biconconectado de rango de circuito inferior a tres (como un gráfico de ciclo o un gráfico theta ) cada ciclo es periférico, pero cada gráfico biconnectado con un rango de circuito tres o más tiene un ciclo no periférico, que se puede encontrar en tiempo lineal. ^[14]

Generalizando gráficos de cuerdas , Seymour y Weaver (1984) definen un gráfico estrangulada a ser un gráfico en el que cada ciclo periférica es un triángulo. Caracterizan estas gráficas como las sumas clicas de las gráficas cordales y las gráficas planas máximas . ^[15]

Conceptos relacionados [ editar ]

Los ciclos periféricos también se han denominado ciclos sin separación, ^[2] pero este término es ambiguo, ya que también se ha utilizado para dos conceptos relacionados pero distintos: ciclos simples cuya eliminación desconectaría el gráfico restante, ^[16] y ciclos de un gráfico incrustado topológicamente de modo que cortar a lo largo del ciclo no desconecte la superficie en la que se incrusta el gráfico. ^[17]

En los matroides , un circuito sin separación es un circuito del matroide (es decir, un conjunto dependiente mínimo) de modo que al eliminar el circuito se deja un matroide más pequeño que está conectado (es decir, que no puede escribirse como una suma directa de matroides) . ^[18] Estos son análogos a los ciclos periféricos, pero no son los mismos incluso en los matroides gráficos (los matroides cuyos circuitos son los ciclos simples de un gráfico). Por ejemplo, en el gráfico bipartito completo $${\ displaystyle K_ {2,3}}, cada ciclo es periférico (solo tiene un puente, una ruta de dos bordes) pero el matroide gráfico formado por este puente no está conectado, por lo que no hay circuito del matroide gráfico de $${\ displaystyle K_ {2,3}} No se separa.