Orientación bipolar

La orientación bipolar u orientación st de un grafo no dirigido  es la asignación de una orientación a cada borde ( orientación ), lo que convierte al grafo en un grafo acíclico dirigido con una sola fuente s y un solo sumidero t , y la numeración st de el gráfico es una clasificación topológica del gráfico acíclico dirigido resultante [1] [2] .

Definiciones y existencia

Sea un grafo no dirigido con vértices. La orientación de un grafo G  es la asignación de una dirección a cada arista del grafo G , lo que lo convierte en un grafo dirigido . Una orientación es acíclica si el gráfico dirigido resultante no tiene ciclos dirigidos . Cualquier gráfico dirigido acíclico tiene al menos una fuente (un vértice desde el que no entran arcos) y al menos un sumidero (un vértice desde el que no se originan arcos). Una orientación es bipolar si hay exactamente una fuente y exactamente un sumidero. En algunas situaciones, G se puede dar junto con los vértices seleccionados s y t . En este caso, la orientación bipolar debería tener s como única fuente y t como único sumidero [1] [2] .

La numeración st del gráfico G (nuevamente, con los dos vértices s y t resaltados ) es la asignación de números enteros del 1 al n a los vértices del gráfico G tal que

• todos los vértices obtienen números diferentes,
• al nodo s se le asigna el número 1,
• al nodo t se le asigna el número n ,
• si al nodo v se le asigna el número i ( ), entonces al menos a un vecino de v se le asigna un número menor que i , y a un vecino se le asigna un número mayor que [1] [2] [3] .

Un gráfico tiene una orientación bipolar si y solo si tiene una numeración st . Si el gráfico tiene una orientación bipolar, entonces se puede construir una numeración st encontrando el tipo topológico del gráfico acíclico dirigido dada la orientación y numerando cada vértice según su posición en ese orden. En la dirección opuesta, cualquier numeración st genera un orden topológico en el que cada borde del gráfico G está orientado desde un punto final con un número más bajo hasta un punto final con un número más alto [1] [2] . En un gráfico que contiene el borde st , una orientación es bipolar si y solo si es acíclica y la orientación formada al invertir el borde st es completamente cíclica [2] .

Un grafo conectado G con vértices distinguidos s y t tiene una orientación bipolar y una numeración st si y solo si el grafo formado a partir de G al agregar un borde de s a t es conectado por 2 vértices [3] . En una dirección, si este gráfico está conectado por 2 vértices, se puede obtener una orientación bipolar orientando secuencialmente cada oído en la descomposición de oídos del gráfico [4] . En la otra dirección, si el gráfico no está conectado por 2 vértices, entonces tiene un vértice articulado v que separa algún componente biconectado de G de s y t . Si este componente contiene un vértice con un número menor que v , entonces el vértice con el número más bajo en el componente no puede tener un vecino con un número más bajo, y simétricamente, si contiene un vértice con un número mayor que v , entonces el vértice con el número más alto El vértice numerado en el componente no puede tener un vecino con un número grande.

Aplicaciones a la planaridad

Lempel, Even y Zederbaum [3] formularon numeraciones de st como parte del algoritmo de comprobación de planaridad [3] , mientras que Rosenstiel [5] y Tarjan [1] formularon la orientación bipolar como parte del algoritmo de mosaico de gráficos planos [1] .

La orientación bipolar de un gráfico plano da como resultado un gráfico st - planar , un gráfico plano acíclico dirigido con una fuente y un sumidero. Estos gráficos juegan un papel importante en la teoría de la red , así como en la visualización de gráficos  : el diagrama de Hasse de una red bidimensional es necesariamente st -planar, y cualquier gráfico st -planar transitivamente reducido representa una red bidimensional. de esta manera [6] . Un grafo acíclico dirigido G tiene una representación plana ascendente si y solo si el grafo G es un subgrafo de un grafo st -planar [7] .

Algoritmos

Uno puede encontrar la numeración st y la orientación bipolar de un gráfico dado con vértices distinguidos s y t en tiempo lineal usando la búsqueda primero en profundidad [8] [9] [10] . El algoritmo de Tarjan [10] utiliza una búsqueda en profundidad que comienza en el vértice s . Al igual que en el algoritmo de búsqueda primero en profundidad para verificar si un gráfico está doblemente conectado, este algoritmo primero pasa un valor pre( v ) para el vértice v , que es el número de preorden de paso en profundidad del vértice v , y un número bajo( v ) , que es el número de preorden más pequeño que se puede lograr siguiendo un borde desde v en un árbol de búsqueda en profundidad. Ambos números se pueden calcular en tiempo lineal como parte de una búsqueda en profundidad. Un gráfico dado estará biconectado (y tendrá una orientación bipolar) si y solo si t es el único hijo de un vértice s en el árbol de búsqueda en profundidad y para todos los vértices v excepto s . Una vez que estos números han sido calculados, el algoritmo de Tarjan realiza una segunda pasada por el árbol df, manteniendo un signo de número ( v ) para cada vértice v y una lista enlazada de vértices que eventualmente produce una lista de todos los vértices en el gráfico en el orden dado por la numeración st . Inicialmente, la lista contiene s y t y . Cuando se encuentra v en el primer paso, v se inserta en la lista antes o después de su padre p( v ) en el árbol de búsqueda en profundidad según sign(low( v )). Entonces sign(p( v )) se establece en -sign(low( v )). Como lo muestra Tarjan, el orden resultante de los vértices de este procedimiento da la numeración st del gráfico dado [10] .

Alternativamente, los algoritmos seriales y paralelos eficientes pueden basarse en la descomposición del oído [4] [11] . Una descomposición en oído abierto de un gráfico dado con vértices distinguidos s y t se puede definir como una partición de los bordes del gráfico en una secuencia de caminos llamados "orejas", en los que los puntos finales de la primera oreja son s y t , los puntos finales de cada oído siguiente pertenece a los oídos anteriores en la secuencia, y cada vértice interno de cada oído aparece primero en ese oído. Existe una descomposición en oreja abierta si y solo si el gráfico obtenido al sumar el borde st es biconexo (la misma condición que para la existencia de una orientación bipolar) y se puede encontrar en tiempo lineal. st -La orientación se puede obtener dando una dirección adecuada para cada oído, teniendo la precaución de que si ya existe un camino orientado que conecta los mismos dos extremos en los oídos anteriores, entonces el nuevo oído debe tener la misma dirección. Sin embargo, verificar esto directamente con un cálculo de accesibilidad será lento. Mahon, Shiber y Vyshkin [4] han proporcionado un procedimiento de búsqueda complejo pero localizado para determinar la orientación adecuada para cada oído, que (a diferencia del enfoque DFS) es adecuado para la computación paralela [4] .

Papamentow y Tollis [12] informan sobre algoritmos para controlar la longitud de las rutas dirigidas en una orientación bipolar de un gráfico dado, lo que a su vez conduce al control de la longitud y la altura de algunas visualizaciones de gráficos [12] .

El espacio de todas las orientaciones

Para gráficos conectados por vértice-3 con vértices distinguidos s y t , cualquiera de las dos orientaciones bipolares se puede conectar entre sí mediante una secuencia de operaciones que invierten la dirección de un arco, manteniendo la orientación bipolar en cada paso [2] . Más estrictamente, para grafos planos 3 conectados, el conjunto de orientaciones bipolares puede recibir la estructura de un retículo distributivo finito con la operación de invertir la dirección del arco correspondiente a la relación de cobertura retículo [ 2] . Para cualquier gráfico con una fuente y un sumidero dedicados, el conjunto de todas las orientaciones bipolares se puede enumerar en tiempo polinomial por orientación [2] .

Notas

1. ↑ 1 2 3 4 5 6 Pierre Rosentiehl, Robert Tarjan. Diseños planos rectilíneos y orientaciones bipolares de grafos planos  // Geometría discreta y computacional . - 1986. - T. 1 , nº. 4 . — S. 343–353 . -doi : 10.1007/ BF02187706 . .
2. ↑ 1 2 3 4 5 6 7 8 Hubert de Fraysseix, Patrice Ossona de Méndez, Pierre. Orientaciones bipolares revisadas // Matemática aplicada discreta. - 1995. - T. 56 , núm. 2-3 . — S. 157–179 . - doi : 10.1016/0166-218X(94)00085-R .
3. ↑ 1 2 3 4 Abraham Lempel, Shimon Even, Cederbaum I. Un algoritmo para la prueba de planaridad de gráficos // Teoría de gráficos (Internat. Sympos., Roma, 1966). - Nueva York: Gordon and Breach, 1967. - S. 215-232.
4. ↑ 1 2 3 4 Maon Y., Schieber B., Vishkin U. Búsqueda de descomposición de orejas paralelas (EDS) y numeración ST en gráficos // Ciencias de la computación teórica . - 1986. - T. 47 , núm. 3 . - doi : 10.1016/0304-3975(86)90153-2 .
5. ↑ El apellido Rosentiehl es de origen alemán y en alemán se lee como Rosenstiel. En inglés, puede sonar como Rosenstiel
6. ↑ Platt CR Redes planas y gráficos planos // Journal of Combinatorial Theory . - 1976. - T. 21 , núm. 1 . — S. 30–39 . - doi : 10.1016/0095-8956(76)90024-1 .
7. ↑ Giuseppe Di Battista, Roberto Tamassia. Algoritmos para representaciones planas de dígrafos acíclicos // Informática Teórica . - 1988. - T. 61 , núm. 2-3 . — S. 175–198 . - doi : 10.1016/0304-3975(88)90123-5 .
8. ↑ Ebert J. st - ordenar los vértices de grafos biconectados // Informática . - 1983. - T. 30 , núm. 1 . — P. 19–33 . -doi : 10.1007/ BF02253293 .
9. ↑ Shimon Even, Robert Tarjan. Cálculo de una numeración st // Informática Teórica . - 1976. - Vol. 2 , número. 3 . — S. 339–344 . - doi : 10.1016/0304-3975(76)90086-4 .
10. ↑ 1 2 3 Robert Tarjan. Dos algoritmos optimizados de búsqueda en profundidad // Fundamenta Informaticae . - 1986. - T. 9 , núm. 1 . — P. 85–94 .
11. ↑ Hillel Gazit. Algoritmos paralelos EREW óptimos para conectividad, descomposición de orejas y numeración st de gráficos planos // Proc. V Simposio Internacional de Procesamiento Paralelo. - 1991. - S. 84-91. -doi : 10.1109/ IPPS.1991.153761 .
12. ↑ 1 2 Charalampos Papamanthou, Ioannis G. Tollis. Aplicaciones de orientaciones de st parametrizadas en algoritmos de dibujo de gráficos // Dibujo de gráficos: 13º Simposio internacional, GD 2005, Limerick, Irlanda, 12 al 14 de septiembre de 2005, Documentos revisados . - Berlín: Springer, 2006. - T. 3843. - S. 355–367. — (Apuntes de clase en informática). -doi : 10.1007/ 11618058_32 .