En la teoría de grafos , una orientación bipolar o st -orientación de un grafo no dirigido es una asignación de una dirección a cada borde (una orientación ) que hace que el grafo se convierta en un grafo acíclico dirigido con una sola fuente sy un solo sumidero t , y una numeración st del gráfico es un orden topológico del gráfico acíclico dirigido resultante. [1] [2]
Definiciones y existencia
Sea G = ( V , E ) una gráfica no dirigida con n = | V | vértices. Una orientación de G es una asignación de una dirección a cada borde de G , convirtiéndola en un gráfico dirigido . Es una orientación acíclica si el gráfico dirigido resultante no tiene ciclos dirigidos . Cada gráfico de orientación acíclica tiene al menos una fuente (un vértice sin bordes entrantes) y al menos un sumidero (un vértice sin bordes salientes); es una orientación bipolar si tiene exactamente una fuente y exactamente un sumidero. En algunas situaciones, G se puede dar junto con dos vértices designados s y t ; en este caso, una orientación bipolar para s y t debe tener s como su fuente única y t como su disipador único. [1] [2]
Un st -numbering de G (de nuevo, con dos vértices designados s y t ) es una asignación de los números enteros de 1 a n a los vértices de G , de manera que
- a cada vértice se le asigna un número distinto,
- s se le asigna el número 1,
- t se le asigna el número n , y
- si a un vértice v se le asigna el número i con 1 < i < n , entonces al menos a un vecino de v se le asigna un número menor que i y al menos a un vecino de v se le asigna un número mayor que i . [1] [2] [3]
Un gráfico tiene una orientación bipolar si y solo si tiene una numeración st . Porque, si tiene una orientación bipolar, entonces se puede construir una numeración st encontrando un orden topológico del gráfico acíclico dirigido dado por la orientación, y numerando cada vértice por su posición en el orden. En la otra dirección, cada numeración st da lugar a un ordenamiento topológico, en el que cada borde de G está orientado desde su punto final con el número más bajo hasta su punto con el número más alto. [1] [2] En un gráfico que contiene la arista st , una orientación es bipolar si y solo si es acíclica y la orientación formada invirtiendo la arista st es totalmente cíclica . [2]
Un gráfico conectado G , con vértices designados s y t , tiene una orientación bipolar y un st -numbering si y sólo si el gráfico formado a partir de G mediante la adición de un borde de s a t es conectado-2-vértice . [3] En una dirección, si este gráfico está conectado por 2 vértices, entonces se puede obtener una orientación bipolar al orientar consistentemente cada oído en una descomposición de oído del gráfico. [4] En la otra dirección, si el gráfico no está conectado-2-vértice, entonces tiene una articulación vértice v separar algunos vértice de corte 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 el 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 en el componente no puede tener un vecino con un número superior.
Aplicaciones a la planicidad
Lempel, Even y Cederbaum (1967) formularon las numeraciones st como parte de un algoritmo de prueba de planaridad , [3] y Rosenstiehl y Tarjan (1986) formularon orientaciones bipolares como parte de un algoritmo para construir representaciones de teselación de gráficos planos . [1]
Una 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 son de cierta importancia en la teoría de la celosía , así como en el dibujo de gráficos : el diagrama de Hasse de una celosía bidimensional es necesariamente st -planar, y todo gráfico st -planar reducido transitivamente representa una retícula bidimensional de esta manera. [5] Un gráfico acíclico dirigido G tiene un dibujo plano hacia arriba si y solo si G es un subgráfico de un gráfico st -planar. [6]
Algoritmos
Es posible encontrar un st -numbering, y una orientación bipolar, de un gráfico dado con vértices designados s y t , en tiempo lineal usando la búsqueda en profundidad . [7] [8] [9] El algoritmo de Tarjan (1986) utiliza una búsqueda en profundidad que comienza en el vértice sy primero atraviesa el borde st . Al igual que en el algoritmo basado en la búsqueda en profundidad para probar si un gráfico está biconectado, este algoritmo define pre ( v ), para un vértice v , como el número de preorden de v en el recorrido en profundidad primero, y bajo ( v ) para ser el número de preorden más pequeño que se puede alcanzar siguiendo un solo borde de un descendiente de v en el árbol de búsqueda en profundidad. Ambos números se pueden calcular en tiempo lineal como parte de la búsqueda en profundidad. El gráfico dado estará biconectado (y tendrá una orientación bipolar) si y solo si t es el único hijo de s en el árbol de búsqueda en profundidad y bajo ( v )
v ) para todos los vértices v distintos de s . Una vez que se han calculado estos números, el algoritmo de Tarjan realiza un segundo recorrido del árbol de búsqueda en profundidad, manteniendo un signo de número ( v ) para cada vértice v y una lista vinculada de vértices que eventualmente enumerará todos los vértices del gráfico en el orden dado por una st -numbering. Inicialmente, la lista contiene s y t , y signo ( s ) = -1. Cuando cada vértice v es encontrado por primera vez por este segundo recorrido, v se inserta en la lista, ya sea antes o después de su padre p ( v ) en el árbol de búsqueda en profundidad según si el signo (bajo ( v )) es negativo o positivo respectivamente; entonces sign (p ( v )) se establece en −sign (low ( v )). Como muestra Tarjan, la ordenación de vértices resultante de este procedimiento da una numeración st del gráfico dado. [9]Alternativamente, los algoritmos secuenciales y paralelos eficientes pueden basarse en la descomposición del oído . [4] [10] [11] Si bien los algoritmos basados en DFS anteriores dependen inherentemente de la descomposición de oído abierto especial causada por el árbol DFS subyacente, la descomposición de oído abierto aquí puede ser arbitraria. Este enfoque más general se utiliza en realidad en varias aplicaciones, por ejemplo, para calcular árboles de expansión independientes (de los bordes). Existe una descomposición de oído abierto si y solo si la gráfica formada a partir de la gráfica dada agregando un borde st está biconectada (la misma condición que la existencia de una orientación bipolar), y se puede encontrar en tiempo lineal. Se puede obtener fácilmente una orientación st (y por lo tanto también una numeración st ) dirigiendo cada oído en una dirección consistente, teniendo cuidado de que si ya existe un camino dirigido que conecta los mismos dos puntos finales entre los bordes de los oídos anteriores, entonces el nuevo La oreja debe estar orientada en la misma dirección. Sin embargo, a pesar de la simplicidad de este enfoque folclórico, obtener un tiempo de ejecución lineal es más complicado. Siempre que se agrega una oreja, los puntos finales de esta oreja deben verificarse en cuanto a la accesibilidad o, de manera equivalente, para la numeración st , qué vértice viene primero en la numeración st preliminar antes. Este obstáculo puede resolverse en el peor de los casos en tiempo constante utilizando la estructura de datos de orden (algo complicada) , [11] o por métodos más directos. Maon, Schieber y Vishkin (1986) proporcionan un procedimiento de búsqueda complicado pero localizado para determinar una orientación apropiada para cada oído que (a diferencia del enfoque que utiliza la búsqueda en profundidad) es adecuado para el cálculo paralelo. [4]
Se da un algoritmo moderno y simple que calcula st -numeraciones y -orientaciones en tiempo lineal. [11] La idea de este algoritmo es reemplazar la estructura de datos de orden por un esquema de numeración sencillo, en el que los vértices llevan intervalos en lugar de st - números.
Papamanthou y Tollis (2006) informan sobre algoritmos para controlar las longitudes de las rutas dirigidas en una orientación bipolar de un gráfico dado, lo que a su vez conduce a cierto control sobre el ancho y la altura de ciertos tipos de dibujo de gráficos . [12]
El espacio de todas las orientaciones
Para los gráficos 3-vértices conectados, con vértices designados s y t , cualquiera de las dos orientaciones bipolares pueden estar conectados entre sí por una secuencia de operaciones que revierten un borde a la vez, en cada paso el mantenimiento de una orientación bipolar. [2] Más fuertemente, para grafos planos conectados en 3 , al conjunto de orientaciones bipolares se le puede dar la estructura de una celosía distributiva finita , con la operación de inversión de borde correspondiente a la relación de cobertura de la celosía. [2] Para cualquier gráfico con fuente y sumidero designados, el conjunto de todas las orientaciones bipolares se puede enumerar en tiempo polinómico por orientación. [2]
st -edge-numeraciones y -orientaciones
Se puede construir un orden que sea similar a las numeraciones st al numerar los bordes en lugar de los vértices. Esto es equivalente a st -numerar el gráfico lineal del gráfico de entrada. Aunque la construcción de la línea de gráfico de explícitamente llevaría tiempo cuadrática, los algoritmos en tiempo lineal para calcular una st -Edge-numeración y st son conocidos -Edge-orientación de un gráfico. [11]
Ver también
- Incrustación convexa , una generalización de mayor dimensión de orientaciones bipolares
Referencias
- ↑ a b c d e Rosenstiehl, Pierre ; Tarjan, Robert E. (1986), "Diseños planos rectilíneos y orientaciones bipolares de gráficos planos", Geometría discreta y computacional , 1 (4): 343–353, doi : 10.1007 / BF02187706 , MR 0866369.
- ^ a b c d e f g h de Fraysseix, Hubert; Ossona de Méndez, Patrice ; Rosenstiehl, Pierre (1995), "Orientaciones bipolares revisitadas", Matemáticas aplicadas discretas , 56 (2-3): 157-179, doi : 10.1016 / 0166-218X (94) 00085-R , MR 1318743.
- ^ a b c Lempel, A .; Incluso, S .; Cederbaum, I. (1967), "Un algoritmo para la prueba de planaridad de gráficos", Teoría de los gráficos (Simposios Internacionales, Roma, 1966) , Nueva York: Gordon y Breach, págs. 215-232, MR 0220617.
- ^ a b c Maon, Y .; Schieber, B .; Vishkin, U. (1986), "Búsqueda de descomposición del oído paralelo (EDS) y numeración ST en gráficos", Theoretical Computer Science , 47 (3): 277-298, doi : 10.1016 / 0304-3975 (86) 90153-2 , MR 0882357.
- ^ Platt, CR (1976), "Rejillas planas y gráficos planas", Journal of Combinatorial Theory , Ser. B, 21 (1): 30–39, doi : 10.1016 / 0095-8956 (76) 90024-1.
- ^ Di Battista, Giuseppe; Tamassia, Roberto (1988), "Algoritmos para representaciones planas de dígrafos acíclicos", Informática teórica , 61 (2-3): 175-198, doi : 10.1016 / 0304-3975 (88) 90123-5.
- ^ Ebert, J. (1983), " st -ordering the vértices of biconnected graphs", Computación , 30 (1): 19–33, doi : 10.1007 / BF02253293 , MR 0691948.
- ^ Incluso, Shimon ; Tarjan, Robert Endre (1976), "Computing an st -numbering", Theoretical Computer Science , 2 (3): 339–344, doi : 10.1016 / 0304-3975 (76) 90086-4 , MR 0414406.
- ^ a b Tarjan, Robert Endre (1986), "Dos algoritmos optimizados de búsqueda en profundidad primero" (PDF) , Fundamenta Informaticae , 9 (1): 85–94, doi : 10.3233 / FI-1986-9105 , MR 0848212.
- ^ Gazit, Hillel (1991), "Algoritmos paralelos EREW óptimos para conectividad, descomposición del oído y numeración st de gráficos planos", Proc. 5to Simposio Internacional de Procesamiento Paralelo , págs. 84–91, doi : 10.1109 / IPPS.1991.153761.
- ^ a b c d Schlipf, Lena; Schmidt, Jens M. (2019), "Cálculo simple de las numeraciones st-edge y st a partir de las descomposiciones del oído", Information Processing Letters , 145 : 58–63, doi : 10.1016 / j.ipl.2019.01.008.
- ^ Papamanthou, Charalampos; Tollis, Ioannis G. (2006), "Aplicaciones de las orientaciones st parametrizadas en algoritmos de dibujo de gráficos" (PDF) , Dibujo de gráficos: 13th International Symposium, GD 2005, Limerick, Irlanda, 12 al 14 de septiembre de 2005, Revised Papers , Lecture Notes in Computer Science, 3843 , Berlín: Springer, págs. 355–367, doi : 10.1007 / 11618058_32 , MR 2244524.