Descomposición del oído

En teoría de grafos , una oreja de un grafo no dirigido G es un camino P cuyos dos extremos pueden coincidir, pero donde no se permite la repetición de aristas ni vértices, de modo que cada vértice interno de P tiene un grado de al menos dos en G. Una descomposición en orejas de G es una partición de su conjunto de aristas en una secuencia de orejas, de manera que uno o dos extremos de cada oreja pertenecen a orejas anteriores en la secuencia y los vértices internos de cada oreja no pertenecen a ninguna oreja anterior. A menudo, la primera oreja de la secuencia se considera un ciclo. Una descomposición en orejas abierta o propia es una descomposición en orejas en la que los dos extremos de cada oreja posterior a la primera son distintos entre sí.

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

Varias clases importantes de grafos pueden caracterizarse como grafos que tienen ciertos tipos de descomposiciones de orejas.

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

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

Un grafo es 2-conexo por vértices si y solo si tiene una descomposición de oreja abierta.${\displaystyle G=(V,E)}$${\displaystyle |E|\geq 2}$

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

Un grafo es 2-arista-conexo si y solo si tiene una descomposición en orejas.

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

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

Un grafo con es 3-vértices-conexo si y solo si G tiene una descomposición de orejas no separables.${\displaystyle G=(V,E)}$${\displaystyle |V|\geq 2}$

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

Las definiciones anteriores también se pueden aplicar a grafos dirigidos . Una oreja es entonces un camino dirigido donde todos los vértices internos tienen grado de entrada y grado de salida iguales a 1. Un grafo dirigido es fuertemente conexo si contiene un camino dirigido desde cada vértice a todos los demás vértices. Entonces tenemos el siguiente teorema ( Bang-Jensen y Gutin 2007 , Teorema 7.2.2):

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

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

Un grafo G es crítico por factores si y solo si G tiene una descomposición de orejas impares.

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

Una descomposición de oreja de árbol es una descomposición de oreja propia en la que la primera oreja es una sola arista y para cada oreja subsiguiente , hay una sola oreja , , tal que ambos extremos de se encuentran en ( Khuller 1989 ). Una descomposición de oreja anidada es una descomposición de oreja de árbol tal que, dentro de cada oreja , el conjunto de pares de extremos de otras orejas que se encuentran dentro 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 combinando grafos serie-paralelo más pequeños de dos maneras: composición en serie (identificando un terminal de un grafo más pequeño con un terminal del otro grafo más pequeño, y manteniendo los otros dos terminales como los terminales del grafo combinado) y composición en paralelo (identificando ambos pares de terminales de los dos grafos más pequeños). ${\displaystyle P_{i}}$${\displaystyle P_{j}}$${\displaystyle i>j}$${\displaystyle P_{i}}$${\displaystyle P_{j}}$${\displaystyle P_{j}}$${\displaystyle P_{i}}$${\displaystyle P_{j}}$

El siguiente resultado se debe a Eppstein ( 1992 ):

Un grafo conexo de 2 vértices es serie-paralelo si y solo si tiene una descomposición de oreja anidada.

Además, cualquier descomposición de oreja abierta de un grafo serie-paralelo con 2 vértices conexos debe estar anidada. El resultado puede extenderse a grafos serie-paralelo que no tienen 2 vértices conexos mediante descomposiciones de oreja abierta que comienzan con un camino entre los dos terminales.

El concepto de descomposición en orejas se puede extender de los grafos a los 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 aunque todos los circuitos anteriores de la secuencia se contraigan.

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

Las descomposiciones de orejas de grafos 2-conexos por aristas y las descomposiciones de orejas abiertas de grafos 2-conexos por vértices pueden encontrarse mediante algoritmos voraces que encuentran cada oreja de una en una. En Schmidt (2013a) se presenta un enfoque voraz simple que calcula simultáneamente descomposiciones de orejas, descomposiciones de orejas abiertas, numeraciones st y orientaciones en tiempo lineal (si existen). El enfoque se basa en el cálculo de una descomposición de orejas especial denominada descomposición en cadena mediante una regla generadora de caminos. Schmidt (2013b) muestra que las descomposiciones de orejas no separables también pueden construirse en tiempo lineal.

Lovász (1985) , Maon, Schieber y Vishkin (1986) y Miller y Ramachandran (1986) proporcionaron algoritmos paralelos eficientes para construir descomposiciones de orejas de varios tipos. Por ejemplo, para encontrar una descomposición de orejas de un grafo 2-arista-conexo, el algoritmo de Maon, Schieber y Vishkin (1986) procede según 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 forma 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 forma parte del árbol, encuentre la "arista maestra" correspondiente, una arista wx que no pertenece al árbol, de tal manera que el ciclo formado al agregar wx al árbol pase por uv y de tal manera que, entre dichas aristas, w y x tengan un ancestro común más bajo que esté lo más cerca posible de la raíz (los empates se resuelven mediante identificadores de aristas).
4. Forme una oreja para cada arista que no sea de árbol, compuesta por ella y las aristas de árbol para las que es maestra, y ordene las orejas según la distancia de sus aristas maestras a la raíz (con la misma regla de desempate).

Estos algoritmos pueden utilizarse como subrutinas para otros problemas, como la comprobación de la conectividad, el reconocimiento de grafos serie-paralelo y la construcción de numeraciones st de grafos (una subrutina importante en la comprobación 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 polinomial dado el acceso a un oráculo de independencia para el matroide ( Coullard y Hellerstein 1996 ).