Descomposición en orejas

Un ejemplo de descomposición en orejas de un grafo que contiene 3 orejas

En teoría de grafos, una oreja de un grafo G es un camino P en el que sus dos extremos pueden coincidir, pero donde no se permite la repetición de aristas o vértices, por lo que todo vértice interno de P tiene grado dos en G. Una descomposición en orejas de un grafo no dirigido G es una partición de su conjunto de aristas en una secuencia en orejas, tal que uno o dos extremos de cada oreja pertenecen a orejas anteriores en la secuencia y tal que los vértices internos de cada oreja no pertenecen a ninguna oreja anterior. Además, en la mayoría de los casos, la primera oreja de la secuencia debe ser un ciclo. Una descomposición en oreja abierta o una descomposición en oreja propia es aquella en la que los dos extremos de cada oreja después de la primera son distintos entre sí.​

Las descomposiciones en orejas se pueden usar para caracterizar varias clases de grafos importantes y como parte de algoritmos de grafo eficientes. También pueden generalizarse de grafos a matroides.

Caracterización de clases de grafos

Varias clases importantes de grafos se pueden caracterizar como grafos que tienen ciertos tipos de descomposiciones en orejas.

Conectividad gráfica

Un grafo es k-vértices-conectado si la eliminación de un grupo de (k − 1) vértices deja un subgrafo conectado, y k-aristas-conectado si la eliminación de un grupo de (k − 1) aristas deja un subgrafo conectado.

El siguiente resultado se debe a Hassler Whitney (1932):

Un grafo $G=(V,E)$ con $|E|\geq 2$ tiene dos vértices conectados si y solo si tiene una descomposición en oreja abierta.

El siguiente resultado se debe a Herbert Robbins (1939):

Un grafo es conectado por 2 aristas si y solo si tiene una descomposición en orejas.

En ambos casos el número de orejas es necesariamente igual al rango de circuito del grafo dado. Robbins introdujo la descomposición en orejas de grafos conectados por 2 aristas como una herramienta para probar el teorema de Robbins, que estos son exactamente los grafos a los que se les puede dar una orientación fuertemente conexa. Debido al trabajo pionero de Whitney y Robbins sobre las descomposiciones en orejas, a veces también se denominan "síntesis de Whitney-Robbins" (Gross y Yellen, 2006).

Una descomposición en orejas sin separación es una descomposición abierta tal que, para cada vértice v con una sola excepción, v tiene un vecino cuya primera aparición en la descomposición es una oreja posterior a la primera aparición de v. Este tipo de descomposición en orejas puede usarse para generalizar el resultado de Whitney:

Un grafo $G=(V,E)$ con $|V|\geq 2$ es conexo en 3 vértices si y solo si "G" tiene una descomposición en orejas sin separación.

Si tal descomposición existe, se puede elegir con respecto a una arista particular uv de G de tal manera que u esté en la primera oreja, v sea el nuevo vértice en la última oreja con más de una arista, y uv es una oreja de una sola arista. Este resultado fue declarado explícitamente por primera vez por Cheriyan y Maheshwari (1988), pero como lo describe Schmidt (2013b), es equivalente a un resultado incluido en la tesis doctoral de Lee Mondshein publicada en 1971. Las estructuras estrechamente relacionadas con las descomposiciones en orejas sin separación de grafos planos máximos, llamadas ordenaciones canónicas, también son una herramienta estándar en el dibujo de grafos.

Fuerte conectividad de grafos dirigidos

Las definiciones anteriores también se pueden aplicar a los grafos dirigidos. Una oreja sería entonces un camino dirigido donde todos los vértices internos tienen grado interior y grado exterior iguales a 1. Un grafo dirigido es fuertemente conexo si contiene un camino dirigido de cada vértice a cualquier otro vértice. Entonces, se verifica el siguiente teorema (Bang-Jensen y Gutin, 2007, Theorem 7.2.2):

Un grafo dirigido es fuertemente conexo si y solo si tiene una descomposición en orejas.

Grafos de factor crítico

Una descomposición en orejas es impar si cada una de sus orejas incluye un número impar de aristas. Un grafo factor crítico es un grafo con un número impar de vértices, de modo que para cada vértice v, si se elimina v del grafo, los vértices restantes tienen un emparejamiento perfecto.László Lovász (1972) encontró que:

Un grafo G es un factor crítico si y solo si G tiene una descomposición en orejas impares.

De forma más general, un resultado de Frank (1993) permite encontrar en cualquier grafo G la descomposición en orejas con el menor número posible de orejas pares.

Grafos serie-paralelo

Una descomposición en orejas en árbol es una descomposición en orejas propiamente dicha en la que la primera oreja es una única arista y para cada oreja subsiguiente $P_{i}$, hay una única oreja $P_{j}$, $i>j$, tal que ambos extremos de $P_{i}$ se encuentran en $P_{j}$ (Khuller, 1989). Una descomposición en orejas anidada es una descomposición de orejas en árbol tal que, dentro de cada oreja $P_{j}$, el conjunto de puntos finales de otras orejas $P_{i}$ que se encuentran dentro de $P_{j}$ forman un conjunto de intervalos anidados. Un grafo serie-paralelo es un grafo con dos terminales designados s y t que se puede formar recursivamente al combinar grafos más pequeños en serie-paralelo en una de dos formas: mediante la composición en serie (identificando un terminal de un grafo con un terminal del otro, y manteniendo los otros dos terminales como los terminales del grafo combinado) y mediante la composición en paralelo (identificando ambos pares de terminales de los dos grafos).

El siguiente resultado se debe a David Eppstein (1992):

Un grafo conectado por 2 vértices es serie-paralelo si y solo si tiene una descomposición en orejas anidadas.

Además, cualquier descomposición en orejas abiertas de un grafo en serie-paralelo conectado por 2 vértices debe estar anidada. El resultado puede extenderse a grafos en serie-paralelo que no son 2-vértices-conectados mediante el uso de descomposiciones en orejas abiertas que comienzan con un camino entre los dos terminales.

Matroides

El concepto de descomposición en orejas se puede extender de grafos a matroides. Una descomposición en orejas de un matroide se define como una secuencia de circuitos del matroide, con dos propiedades:

• Cada circuito en la secuencia tiene una intersección no vacía con los circuitos anteriores, y
• Cada circuito de la secuencia sigue siendo un circuito incluso si se contraen todos los circuitos anteriores de la secuencia.

Cuando se aplica al matroide gráfico de un grafo G, esta definición de descomposición en orejas coincide con la definición de descomposición en orejas propia en G: las descomposiciones impropias están excluidas por el requisito de que cada circuito incluya al menos una arista que también pertenece a circuitos anteriores. Usando esta definición, un matroide puede definirse como factor crítico cuando tiene una descomposición en orejas en la que cada circuito en la secuencia tiene un número impar de elementos nuevos (Szegedy y Szegedy, 2006).

Algoritmos

En las computadoras clásicas, un algoritmo voraz puede encontrar descomposiciones en orejas de grafos conectados por 2 aristas y descomposiciones en orejas abiertas de grafos 2-vértices conectados que encuentran cada oreja uno cada vez. En Schmidt (2013a) se proporciona un enfoque voraz simple que calcula al mismo tiempo las descomposiciones en orejas, las descomposiciones en orejas abiertas, las numeraciones y las orientaciones en tiempo lineal (si existen). El enfoque se basa en el cálculo de una descomposición en orejas especial denominada descomposición en cadena mediante una regla de generación de rutas.Schmidt (2013b) muestra que las descomposiciones en orejas sin separación también pueden construirse en tiempo lineal.Lovász (1985),Maon, Schieber y Vishkin (1986) y Miller y Ramachandran (1986) proporcionaron algoritmos en paralelo eficientes para obtener descomposiciones en orejas de varios tipos. Por ejemplo, para encontrar una descomposición en orejas de un grafo 2-aristas conectado, el algoritmo de Maon, Schieber y Vishkin (1986) procede de acuerdo con los siguientes pasos:

1. Encuentra un árbol de expansión del grafo dado y elige una raíz para el árbol.
2. Determina, para cada arista uv que no sea parte del árbol, la distancia entre la raíz y el ancestro común más bajo de u y v.
3. Para cada arista uv que sea parte del árbol, encuentre la arista maestra correspondiente, una arista que no sea un árbol wx tal que el ciclo formado al agregar wx al árbol pase a través de uv y tal que, entre tales aristas, w y x tienen un ancestro común más bajo que está lo más cerca posible de la raíz (con vínculos rotos por identificadores de arista).
4. Forma una oreja para cada arista que no sea de árbol, compuesta por ella y las aristas de árbol de las que es maestra, y ordena las orejas por la distancia de sus aristas maestras desde la raíz (con la misma regla de desempate).

Estos algoritmos se pueden usar como subrutinas para otros problemas, incluida la prueba de conectividad, el reconocimiento de grafos en serie-paralelo y la construcción de numeraciones "st" de grafos (una subrutina importante en la prueba de planaridad).

Una descomposición en orejas de un matroide dado, con la restricción adicional de que cada oreja contiene el mismo elemento fijo del matroide, se puede encontrar en tiempo polinómico con acceso a un oráculo de independencia para el matroide (Coullard y Hellerstein, 1996).

Bibliografía

• Bang-Jensen, Jørgen; Gutin, Gregory (2007), «7.2 Ear Decompositions», Digraphs: Theory, Algorithms and Applications, Springer-Verlag, pp. 349-352 .
• Cheriyan, J.; Maheshwari, S. N. (1988), «Finding nonseparating induced cycles and independent spanning trees in 3-connected graphs», Journal of Algorithms 9 (4): 507-537, MR 970192, doi:10.1016/0196-6774(88)90015-6 ..
• Coullard, Collette R.; Hellerstein, Lisa (1996), «Independence and port oracles for matroids, with an application to computational learning theory», Combinatorica 16 (2): 189-208, MR 1401892, doi:10.1007/BF01844845 ..
• Eppstein, D. (1992), «Parallel recognition of series–parallel graphs», Information and Computation 98 (1): 41-55, MR 1161075, doi:10.1016/0890-5401(92)90041-D ..
• Frank, András (1993), «Conservative weightings and ear-decompositions of graphs», Combinatorica 13 (1): 65-81, MR 1221177, doi:10.1007/BF01202790 ..
• Gross, Jonathan L.; Yellen, Jay (2006), «Characterization of strongly orientable graphs», Graph theory and its applications, Discrete Mathematics and its Applications (Boca Raton) (2nd edición), Chapman &Hall/CRC, Boca Raton, FL, pp. 498-499, ISBN 978-1-58488-505-4, MR 2181153 ..
• Khuller, Samir (1989), «Ear decompositions», SIGACT News 20 (1): 128 ..
• Lovász, László (1972), «A note on factor-critical graphs», Studia Sci. Math. Hung. 7: 279-280, MR 0335371 ..
• Lovász, László (1985), «Computing ears and branchings in parallel», 26th Annual Symposium on Foundations of Computer Science, pp. 464-467, doi:10.1109/SFCS.1985.16 ..
• Maon, Y.; Schieber, B.; Vishkin, U. (1986), «Parallel ear decomposition search (EDS) and ST-numbering in graphs», Theoretical Computer Science 47 (3): 277-298, MR 0882357, doi:10.1016/0304-3975(86)90153-2 ..
• Miller, G.; Ramachandran, V. (1986), Efficient parallel ear decomposition with applications, Unpublished manuscript ..
• Robbins, H. E. (1939), «A theorem on graphs, with an application to a problem of traffic control», American Mathematical Monthly 46 (5): 281-283, JSTOR 2303897, doi:10.2307/2303897 ..
• Schmidt, Jens M. (2013a), «A Simple Test on 2-Vertex- and 2-Edge-Connectivity», Information Processing Letters 113 (7): 241-244, arXiv:1209.0700, doi:10.1016/j.ipl.2013.01.016 ..
• Schmidt, Jens M. (2013b), The Mondshein sequence, Bibcode:2013arXiv1311.0750S, arXiv:1311.0750 ..
• Schrijver, Alexander (2003), Combinatorial Optimization. Polyhedra and efficiency. Vol A, Springer-Verlag, ISBN 978-3-540-44389-6 ..
• Szegedy, Balázs; Szegedy, Christian (2006), «Symplectic spaces and ear-decomposition of matroids», Combinatorica 26 (3): 353-377, MR 2246153, doi:10.1007/s00493-006-0020-3 ..
• Whitney, H. (1932), «Non-separable and planar graphs», Transactions of the American Mathematical Society 34 (2): 339-362, JSTOR 1989545, doi:10.1090/S0002-9947-1932-1501641-2 ..

• Datos: Q5325632