En teoría de grafos , una oreja de un grafo no dirigido G es un camino P donde los dos puntos finales del camino pueden coincidir, pero donde de lo contrario no se permite la repetición de aristas o vértices, por lo que cada 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 de orejas, de modo que uno o dos puntos finales de cada oreja pertenecen a orejas anteriores en la secuencia y de modo 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 en la secuencia debe ser un ciclo. Una descomposición en orejas abiertas o una descomposición en orejas propiamente dicha es una descomposición en orejas en la que los dos puntos finales de cada oreja después de la primera son distintos entre sí.
Las descomposiciones de orejas se pueden utilizar para caracterizar varias clases de grafos importantes y como parte de algoritmos de grafos eficientes . También se pueden generalizar de grafos a matroides .
Varias clases importantes de gráficos pueden caracterizarse como gráficos 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):
El siguiente resultado se debe a Herbert Robbins (1939):
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 conexos por dos aristas como una herramienta para demostrar el teorema de Robbins , que afirma que estos son exactamente los grafos a los que se les puede dar una orientación fuertemente conectada . Debido al trabajo pionero de Whitney y Robbins sobre las descomposiciones en orejas, a veces a una descomposición en orejas también se la denomina síntesis de Whitney-Robbins (Gross y Yellen, 2006).
Una descomposición en orejas sin separación es una descomposición en orejas abiertas de modo que, para cada vértice v con una sola excepción, v tiene un vecino cuya primera aparición en la descomposición es en una oreja posterior a la primera aparición de v . Este tipo de descomposición en orejas se puede utilizar para generalizar el resultado de Whitney:
Si existe tal descomposición, 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 sea una oreja de una sola arista. Este resultado fue establecido explícitamente por primera vez por Cheriyan y Maheshwari (1988), pero como describe Schmidt (2013b), es equivalente a un resultado en la tesis doctoral de 1971 de Lee Mondshein. Las estructuras estrechamente relacionadas con las descomposiciones de orejas no separadoras de grafos planares maximalistas, llamadas ordenamientos canónicos, también son una herramienta estándar en el dibujo de grafos .
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 de entrada y grado de salida igual a 1. Un grafo dirigido está fuertemente conectado si contiene un camino dirigido desde cada vértice a cada uno de los demás vértices. Entonces tenemos el siguiente teorema (Bang-Jensen y Gutin 2007, Teorema 7.2.2):
Una descomposición en orejas es impar si cada una de sus orejas utiliza un número impar de aristas. Un grafo factorialmente crítico es un grafo con un número impar de vértices, de modo que para cada vértice v , si v se elimina del grafo, entonces los vértices restantes tienen una correspondencia perfecta . László Lovász (1972) descubrió que:
De manera más general, un resultado de Frank (1993) permite encontrar en cualquier grafo G la descomposición en espigas con el menor número de espigas pares.
Una descomposición en orejas de árbol es una descomposición en orejas propia en la que la primera oreja es una arista única y para cada oreja posterior , hay una sola oreja , , tal que ambos puntos finales de se encuentran en (Khuller 1989). Una descomposición en orejas anidadas es una descomposición en orejas de árbol tal que, dentro de cada oreja , el conjunto de pares de puntos finales 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 pueden formar recursivamente combinando grafos serie-paralelos más pequeños de una 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 paralela (identificando ambos pares de terminales de los dos grafos más pequeños).
El siguiente resultado se debe a David Eppstein (1992):
Además, cualquier descomposición en orejas abiertas de un grafo serie-paralelo conexo por dos vértices debe estar anidada. El resultado puede extenderse a grafos serie-paralelos que no estén conexos por dos vértices mediante descomposiciones en orejas abiertas que comiencen 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:
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 una descomposición en orejas 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. 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 & Szegedy 2006).
En las computadoras clásicas, las descomposiciones de orejas de grafos conectados por dos aristas y las descomposiciones de orejas abiertas de grafos conectados por dos vértices se pueden encontrar mediante algoritmos voraces que encuentran cada oreja una a la vez. En Schmidt (2013a) se presenta un enfoque voraz simple que calcula al mismo tiempo las descomposiciones de orejas, las descomposiciones de orejas abiertas, las numeraciones st y las 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 de generación de trayectorias. Schmidt (2013b) muestra que las descomposiciones de orejas no separables también se pueden construir 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 con dos aristas conectadas, el algoritmo de Maon, Schieber y Vishkin (1986) procede de acuerdo con los siguientes pasos:
Estos algoritmos pueden usarse como subrutinas para otros problemas, incluidas las pruebas de conectividad, el reconocimiento de gráficos en serie-paralelo y la construcción de numeraciones st de gráficos (una subrutina importante en las pruebas de planaridad ).
Se puede encontrar 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, en tiempo polinomial dado el acceso a un oráculo de independencia para el matroide (Coullard y Hellerstein 1996).
