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 por lo demás 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 de oreja de un gráfico 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 manera que los vértices internos de cada oreja no pertenecen a cualquier oído anterior. Además, en la mayoría de los casos el primer oído de la secuencia debe ser un ciclo. Una descomposición del oído abierto o una descomposición del oído propiamente dicha es una descomposición del oído en la que los dos extremos de cada oído después del primero son distintos entre sí.
Las descomposiciones de oído se pueden utilizar para caracterizar varias clases de gráficos importantes y como parte de algoritmos de gráficos eficientes . También se pueden generalizar desde gráficos hasta matroides .
Varias clases importantes de gráficos pueden caracterizarse como gráficos que tienen ciertos tipos de descomposiciones del oído.
Un gráfico está k -conectado por vértices si la eliminación de cualquier ( k − 1) vértice deja un subgrafo conectado, y k -conectado por aristas si la eliminación de cualquier ( k − 1) arista deja un subgrafo conectado.
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 oídos es necesariamente igual al rango del circuito del gráfico dado. Robbins introdujo la descomposición auricular de gráficos de dos aristas conectadas como una herramienta para demostrar el teorema de Robbins , de que estos son exactamente los gráficos a los que se les puede dar una orientación fuertemente conexa . Debido al trabajo pionero de Whitney y Robbins sobre las descomposiciones del oído, a esta descomposición a veces también se le llama síntesis de Whitney-Robbins (Gross y Yellen 2006).
Una descomposición de oreja que no se separa es una descomposición de oreja abierta tal que, para cada vértice v con solo una 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 de la oreja se puede utilizar para generalizar el resultado de Whitney:
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 sea una oreja de un solo borde. Este resultado fue declarado explícitamente por primera vez por Cheriyan y Maheshwari (1988), pero, como describe Schmidt (2013b), es equivalente a un resultado del Ph.D. tesis de Lee Mondshein. Las estructuras estrechamente relacionadas con las descomposiciones de orejas no separativas de gráficos planos máximos, llamadas ordenamientos canónicos, también son una herramienta estándar en el dibujo de gráficos .
Las definiciones anteriores también se pueden aplicar a gráficos dirigidos . Una oreja sería entonces un camino dirigido donde todos los vértices internos tienen grados de entrada y de salida iguales a 1. Un gráfico dirigido está fuertemente conectado si contiene un camino dirigido desde cada vértice a todos los demás vértices. Entonces tenemos el siguiente teorema (Bang-Jensen & Gutin 2007, Teorema 7.2.2):
Una descomposición de oreja es impar si cada una de sus orejas utiliza un número impar de aristas. Un gráfico de factores críticos es un gráfico con un número impar de vértices, de modo que para cada vértice v , si se elimina v del gráfico, los vértices restantes tienen una coincidencia perfecta . László Lovász (1972) encontró que:
De manera más general, un resultado de Frank (1993) permite encontrar en cualquier gráfico G la descomposición de orejas con el menor número de orejas pares.
Una descomposición de oreja de árbol es una descomposición de oreja adecuada en la que la primera oreja es un solo borde y para cada oreja subsiguiente , hay una sola oreja , de modo que ambos puntos finales se encuentran (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 puntos finales de otras orejas que se encuentran dentro forman un conjunto de intervalos anidados. Un gráfico en series paralelas es un gráfico con dos terminales designados s y t que se pueden formar recursivamente combinando gráficos en series paralelas más pequeños de una de dos maneras: composición de series (identificando un terminal de un gráfico más pequeño con un terminal de otro gráfico más pequeño). gráfico, y manteniendo los otros dos terminales como los terminales del gráfico combinado) y composición paralela (identificando ambos pares de terminales de los dos gráficos más pequeños).
El siguiente resultado se debe a David Eppstein (1992):
Además, cualquier descomposición en oído abierto de un gráfico en serie-paralelo conectado con 2 vértices debe estar anidada. El resultado se puede extender a gráficos en serie-paralelo que no están conectados por 2 vértices mediante el uso de descomposiciones de oído abierto que comienzan con una ruta entre las dos terminales.
El concepto de descomposición del oído se puede ampliar desde gráficos hasta matroides . La descomposición del oído de una matroide se define como una secuencia de circuitos de la matroide, con dos propiedades:
Cuando se aplica a la matroide gráfica de un gráfico G , esta definición de descomposición del oído coincide con la definición de una descomposición del oído adecuada de G : las descomposiciones impropias quedan excluidas por el requisito de que cada circuito incluya al menos un borde que también pertenezca a circuitos anteriores. . Utilizando esta definición, una matroide puede definirse como de factor crítico cuando tiene una descomposición del oído en la que cada circuito de la secuencia tiene un número impar de elementos nuevos (Szegedy y Szegedy 2006).
En las computadoras clásicas, las descomposiciones en oído de gráficos conectados con 2 vértices y las descomposiciones en oído abierto de gráficos conectados con 2 vértices se pueden encontrar mediante algoritmos codiciosos que encuentran cada oído uno a la vez. En Schmidt (2013a) se ofrece un enfoque simple y codicioso que calcula al mismo tiempo descomposiciones de oído, descomposiciones de oído abierto, numeraciones st y orientaciones en tiempo lineal (si existen). El enfoque se basa en calcular una descomposición especial del oído denominada descomposición en cadena mediante una regla generadora de caminos. Schmidt (2013b) muestra que las descomposiciones de orejas que no se separan 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 oreja de varios tipos. Por ejemplo, para encontrar una descomposición oreja de un gráfico de dos aristas conectadas, el algoritmo de Maon, Schieber y Vishkin (1986) procede de acuerdo con los siguientes pasos:
Estos algoritmos se pueden utilizar como subrutinas para otros problemas, incluidas las pruebas de conectividad, el reconocimiento de gráficos en series paralelas y la construcción de numeraciones st de gráficos (una subrutina importante en las pruebas de planaridad ).
Una descomposición del oído de una matroide determinada, con la restricción adicional de que cada oído contiene el mismo elemento fijo de la matroide, se puede encontrar en tiempo polinomial si se tiene acceso a un oráculo de independencia para la matroide (Coullard y Hellerstein 1996).
