Orientación bipolar

En 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 arista (una orientación ) que hace que el grafo se convierta en un grafo dirigido acíclico con una única fuente s y un único sumidero t , y una st -numeración del grafo es un ordenamiento topológico del grafo dirigido acíclico resultante. ^{[ 1 ] [ 2 ]}

Sea G  =  ( V , E ) un grafo no dirigido con n  =  | V | vértices. Una orientación de G es la asignación de una dirección a cada arista de G , convirtiéndolo en un grafo dirigido . Es una orientación acíclica si el grafo dirigido resultante no tiene ciclos dirigidos . Todo grafo con orientación acíclica tiene al menos un origen (un vértice sin aristas entrantes) y al menos un sumidero (un vértice sin aristas salientes); es una orientación bipolar si tiene exactamente un origen y exactamente un sumidero. En algunas situaciones, G puede darse junto con dos vértices designados s y t ; en este caso, una orientación bipolar para s y t debe tener a s como su único origen y a t como su único sumidero. ^{[ 1 ] [ 2 ]}

Una numeración st de G (nuevamente, con dos vértices designados s y t ) es una asignación de los enteros del 1 al n a los vértices de G , de tal manera que

• A cada vértice se le asigna un número distinto,
• A s se le asigna el número 1,
• A 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 un vecino de v se le asigna un número menor que i y al menos un vecino de v se le asigna un número mayor que i . ^{[ 1 ] [ 2 ] [ 3 ]}   

Un grafo tiene una orientación bipolar si y solo si tiene una numeración st . Pues, si tiene una orientación bipolar, entonces una numeración st puede construirse encontrando un orden topológico del grafo dirigido acíclico dado por la orientación, y numerando cada vértice por su posición en el orden. En la otra dirección, toda numeración st da lugar a un orden topológico, en el que cada arista de G está orientada desde su extremo de menor número hasta su extremo de mayor número. ^{[ 1 ] [ 2 ]} En un grafo que contiene la arista st , una orientación es bipolar si y solo si es acíclica y la orientación formada al invertir la arista st es totalmente cíclica . ^{[ 2 ]}

Un grafo conexo G , con vértices designados 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 una arista de s a t es 2-conexo-vértice . ^{[ 3 ]} En una dirección, si este grafo es 2-conexo-vértice, entonces se puede obtener una orientación bipolar orientando consistentemente cada oreja en una descomposición de oreja del grafo. ^{[ 4 ]} En la otra dirección, si el grafo no es 2-conexo-vértice, entonces tiene un vértice de articulación v que separa algún componente biconexo 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 menor, 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 mayor.

Lempel, Even y Cederbaum (1967) formularon 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 grafos planares . ^{[ 1 ]}

Una orientación bipolar de un grafo planar resulta en un grafo st -planar , un grafo planar acíclico dirigido con una fuente y un sumidero. Estos grafos son de cierta importancia en la teoría de retículos, así como en el dibujo de grafos : el diagrama de Hasse de un retículo bidimensional es necesariamente st- planar, y todo grafo st- planar reducido transitivamente representa un retículo bidimensional de esta manera. ^{[ 5 ]} Un grafo acíclico dirigido G tiene un dibujo planar ascendente si y solo si G es un subgrafo de un grafo st -planar. ^{[ 6 ]}

Es posible encontrar una numeración st y una orientación bipolar de un grafo dado con vértices designados s y t en tiempo lineal usando búsqueda en profundidad . ^{[ 7 ] [ 8 ] [ 9 ]} El algoritmo de Tarjan (1986) usa una búsqueda en profundidad que comienza en el vértice s y primero recorre la arista st . Como en el algoritmo basado en búsqueda en profundidad para probar si un grafo es biconexo, este algoritmo define pre( v ), para un vértice v , como el número de preorden de v en el recorrido en profundidad, y low( v ) como el número de preorden más pequeño que se puede alcanzar siguiendo una sola arista de un descendiente de v en el árbol de búsqueda en profundidad. Ambos estos números se pueden calcular en tiempo lineal como parte de la búsqueda en profundidad. El grafo dado será biconexo (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 low( v )  <  pre( v ) para todos los vértices v distintos de s . Una vez calculados estos números, el algoritmo de Tarjan realiza un segundo recorrido del árbol de búsqueda en profundidad, manteniendo un número sign( v ) para cada vértice v y una lista enlazada de vértices que eventualmente listará todos los vértices del grafo en el orden dado por una numeración st . Inicialmente, la lista contiene s y t , y sign( 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 sign(low( v )) es negativo o positivo respectivamente; luego sign(p( v )) se establece en −sign (low( v )). Como muestra Tarjan, el ordenamiento de vértices resultante de este procedimiento proporciona una numeración st del grafo dado. ^{[ 9 ]}   

Alternativamente, los algoritmos secuenciales y paralelos eficientes pueden basarse en la descomposición en orejas . ^{[ 4 ] [ 10 ] [ 11 ]} Mientras que los algoritmos basados ​​en DFS anteriores dependen inherentemente de la descomposición especial en orejas abiertas causada por el árbol DFS subyacente, la descomposición en orejas abiertas aquí puede ser arbitraria. Este enfoque más general se utiliza en varias aplicaciones, por ejemplo, para calcular árboles de expansión (independientes de las aristas). Una descomposición en orejas abiertas existe si y solo si el grafo formado a partir del grafo dado al agregar una arista st es biconexo (la misma condición que la existencia de una orientación bipolar), y puede encontrarse en tiempo lineal. Una orientación st (y por lo tanto también una numeración st ) puede obtenerse fácilmente dirigiendo cada oreja en una dirección consistente, teniendo cuidado de que si ya existe un camino dirigido que conecta los mismos dos puntos finales entre las aristas de orejas anteriores, entonces la nueva oreja debe estar orientada en la misma dirección. Sin embargo, a pesar de la simplicidad de este enfoque popular, obtener un tiempo de ejecución lineal es más complejo. Cada vez que se agrega una oreja, se debe verificar la alcanzabilidad de los extremos de esta oreja o, equivalentemente para la numeración st , qué vértice aparece primero en la numeración st preliminar anterior. Este obstáculo se puede resolver en tiempo constante en el peor de los casos utilizando la estructura de datos de orden ( algo compleja) ^{[ 11 ]} o mediante métodos más directos. Maon, Schieber y Vishkin (1986) proporcionan un procedimiento de búsqueda complejo pero localizado para determinar una orientación apropiada para cada oreja que (a diferencia del enfoque que utiliza la búsqueda en profundidad) es adecuado para el cálculo paralelo. ^{[ 4 ]}

^{En [ 11 ]} se presenta un algoritmo moderno y sencillo que calcula numeraciones y orientaciones st en tiempo lineal. 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 contienen intervalos en lugar de números st .

Papamanthou y Tollis (2006) informan sobre algoritmos para controlar las longitudes de los caminos dirigidos en una orientación bipolar de un grafo dado, lo que a su vez conduce a cierto control sobre el ancho y la altura de ciertos tipos de dibujo de grafos . ^{[ 12 ]}

Para grafos con 3 vértices conexos, con vértices designados s y t , cualquier par de orientaciones bipolares pueden conectarse entre sí mediante una secuencia de operaciones que invierten una arista a la vez, manteniendo en cada paso una orientación bipolar. ^{[ 2 ]} De manera más fuerte, para grafos planares con 3 vértices conexos , el conjunto de orientaciones bipolares puede tener la estructura de un retículo distributivo finito , donde la operación de inversión de aristas corresponde a la relación de recubrimiento del retículo. ^{[ 2 ]} Para cualquier grafo con origen y destino designados, el conjunto de todas las orientaciones bipolares puede listarse en tiempo polinomial por orientación. ^{[ 2 ]}

Se puede construir un ordenamiento similar a las numeraciones st numerando las aristas en lugar de los vértices. Esto equivale a numerar st el grafo de líneas del grafo de entrada. Si bien la construcción explícita del grafo de líneas requeriría un tiempo cuadrático, se conocen algoritmos de tiempo lineal para calcular una numeración de aristas st y una orientación de aristas st de un grafo. ^{[ 11 ]}

• Incrustaciones convexas , una generalización de dimensiones superiores de las orientaciones bipolares.