En la teoría de grafos , una oreja de un grafo no dirigido G es un camino P , donde los dos puntos extremos de la trayectoria pueden coincidir, pero que de otro modo no se permite ninguna repetición de bordes o vértices, por lo que cada vértice interno de P tiene grado dos en G . Una descomposición del oído de un gráfico no dirigido G es una particiónde su conjunto de bordes en una secuencia de orejas, de modo que uno o dos extremos de cada oreja pertenezcan a orejas anteriores en la secuencia y de manera que los vértices internos de cada oreja no pertenezcan a ninguna oreja 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 adecuada del oído es una descomposición del oído en la que los dos puntos finales 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 pueden generalizarse de gráficos a matroides .
Caracterizar clases de grafos
Varias clases importantes de gráficos pueden caracterizarse como gráficos que tienen ciertos tipos de descomposición del oído.
Conectividad gráfica
Un gráfico está conectado con k -vértices si la eliminación de cualquier ( k - 1) vértice deja un subgrafo conectado, y k -edge-conectado si la eliminación de cualquier ( k - 1) arista deja un subgrafo conectado.
El siguiente resultado se debe a Hassler Whitney ( 1932 ):
- Un gráfico con está conectado a 2 vértices si y solo si tiene una descomposición de oído abierto.
El siguiente resultado se debe a Herbert Robbins ( 1939 ):
- Un gráfico está conectado por 2 bordes si y solo si tiene una descomposición del oído.
En ambos casos, el número de oídos es necesariamente igual al rango de circuito del gráfico dado. Robbins introdujo la descomposición del oído de gráficos conectados por dos bordes como una herramienta para demostrar el teorema de Robbins , que estos son exactamente los gráficos a los que se les puede dar una orientación fuertemente conectada . Debido al trabajo pionero de Whitney y Robbins sobre la descomposición del oído, la descomposición del oído a veces también se denomina síntesis de Whitney-Robbins ( Gross y Yellen 2006 ).
Una descomposición de la oreja sin separación es una descomposición de la oreja 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 en una oreja posterior a la primera aparición de v . Este tipo de descomposición del oído se puede utilizar para generalizar el resultado de Whitney:
- Un gráfico con está conectado a 3 vértices si y solo si G tiene una descomposición de la oreja que no se separa.
Si existe tal descomposición, se puede elegir con respecto a un borde uv particular 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 un borde y uv sea un 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. de 1971. tesis de Lee Mondshein. Las estructuras estrechamente relacionadas con las descomposiciones de las orejas sin separación de los gráficos planos máximos, llamadas ordenaciones canónicas, también son una herramienta estándar en el dibujo de gráficos .
Fuerte conectividad de gráficos dirigidos
Las definiciones anteriores también se pueden aplicar a gráficos dirigidos . Entonces, una oreja sería un camino dirigido donde todos los vértices internos tienen un grado y un grado exterior iguales a 1. Un grafo dirigido está fuertemente conectado si contiene un camino dirigido desde cada vértice a cada otro vértice. Entonces tenemos el siguiente teorema ( Bang-Jensen & Gutin 2007 , Teorema 7.2.2):
- Un gráfico dirigido está fuertemente conectado si y solo si tiene una descomposición del oído.
Gráficos de factor crítico
La descomposición de una oreja es extraña si cada una de sus orejas usa un número impar de bordes. Un gráfico de factor crítico es un gráfico con un número impar de vértices, de modo que para cada vértice v , si v se elimina del gráfico, los vértices restantes tienen una coincidencia perfecta . László Lovász ( 1972 ) encontró que:
- Un gráfico G es un factor crítico si y solo si G tiene una descomposición de oído extraña.
De manera más general, un resultado de Frank (1993) permite encontrar en cualquier gráfico G la descomposición de la oreja con la menor cantidad de orejas pares.
Gráficos en serie-paralelo
La descomposición de una mazorca de árbol es una descomposición adecuada de la mazorca en la que la primera mazorca es un solo borde y para cada mazorca posterior, hay una sola oreja , , de modo que ambos puntos finales de acostarse ( Khuller 1989 ). Una descomposición de mazorcas anidadas es una descomposición de mazorcas de árbol tal que, dentro de cada mazorca, el conjunto de pares de puntos finales de otros oídos que se encuentran dentro forman un conjunto de intervalos anidados. Un gráfico de serie-paralelo es un gráfico con dos terminales designados s y t que se puede formar de forma recursiva mediante la combinación de serie-paralelo más pequeños gráficos en una de dos maneras: composición de la serie (la identificación de un terminal de un gráfico más pequeño con un terminal de la otra más pequeña 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 ):
- Un gráfico conectado a 2 vértices es paralelo en serie si y solo si tiene una descomposición de oreja anidada.
Además, cualquier descomposición de oído abierto de un gráfico en serie-paralelo conectado a dos vértices debe anidarse. El resultado puede extenderse 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.
Matroides
El concepto de descomposición de una oreja puede extenderse desde gráficos a matroides . Una descomposición del oído de un matroide se define como una secuencia de circuitos del matroide, con dos propiedades:
- cada circuito de 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 a la matriz gráfica de un gráfico G , esta definición de una descomposición de la oreja coincide con la definición de una descomposición de la oreja adecuada de G : las descomposiciones inapropiadas se excluyen por el requisito de que cada circuito incluya al menos un borde que también pertenezca a circuitos anteriores. . Usando esta definición, un matroide puede definirse como factor crítico cuando tiene una descomposición de la oreja 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, las descomposiciones de oído de gráficos conectados por 2 bordes y las descomposiciones de oído abierto de gráficos conectados por 2 vértices se pueden encontrar mediante algoritmos codiciosos que encuentran cada oído de uno en uno. En Schmidt (2013a) se da un enfoque simple y codicioso que calcula al mismo tiempo las descomposiciones de la oreja, las descomposiciones de la oreja abierta, las numeraciones st y las orientaciones en tiempo lineal (si existen ) . El enfoque se basa en calcular una descomposición de oído especial denominada descomposición en cadena mediante una regla de generación de ruta. Schmidt (2013b) muestra que las descomposiciones de las mazorcas 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 paralelos eficientes para construir descomposiciones de oído de varios tipos. Por ejemplo, para encontrar una descomposición del oído de un gráfico conectado por 2 bordes, el algoritmo de Maon, Schieber y Vishkin (1986) procede de acuerdo con los siguientes pasos:
- Encuentre un árbol de expansión del gráfico dado y elija una raíz para el árbol.
- Determine, para cada borde uv que no sea parte del árbol, la distancia entre la raíz y el antepasado común más bajo de u y v .
- Para cada arista uv que sea parte del árbol, encuentre la "arista maestra" correspondiente, una arista que no sea del árbol wx tal que el ciclo formado al sumar wx al árbol pase a través de uv y tal que, entre tales aristas, w y x tener un ancestro común más bajo que esté lo más cerca posible de la raíz (con los lazos rotos por los identificadores de borde).
- Forme una oreja para cada borde que no sea un árbol, que consiste en él y los bordes del árbol de los que es el maestro, y ordene las orejas por la distancia de sus bordes maestros desde la raíz (con la misma regla de desempate).
Estos algoritmos pueden ser utilizados como subrutinas para otros problemas, incluyendo pruebas de conectividad, reconociendo gráficas serie-paralelo, y la construcción de st -numberings de gráficos (una subrutina importante en pruebas de planaridad ).
Una descomposición de la oreja de una matroide dada, con la restricción adicional de que cada oreja contiene el mismo elemento fijo de la matroide, se puede encontrar en el tiempo polinomial dado acceso a un oráculo de independencia para la matroide ( Coullard y Hellerstein 1996 ).
Referencias
- Bang-Jensen, Jørgen; Gutin, Gregory (2007), "7.2 Descomposiciones del oído", Dígrafos: teoría, algoritmos y aplicaciones , Springer-Verlag, págs. 349–352
- Cheriyan, J .; Maheshwari, SN (1988), "Encontrar ciclos inducidos sin separación y árboles de expansión independientes en gráficos de 3 conexiones", Journal of Algorithms , 9 (4): 507–537, doi : 10.1016 / 0196-6774 (88) 90015-6 , Señor 0970192.
- Coullard, Collette R .; Hellerstein, Lisa (1996), "Independencia y oráculos portuarios para matroides, con una aplicación a la teoría del aprendizaje computacional", Combinatorica , 16 (2): 189-208, doi : 10.1007 / BF01844845 , MR 1401892.
- Eppstein, D. (1992), "Reconocimiento paralelo de series-gráficas paralelas" (PDF) , Information and Computation , 98 (1): 41–55, doi : 10.1016 / 0890-5401 (92) 90041-D , MR 1161075.
- Frank, András (1993), "Ponderaciones conservadoras y descomposiciones auditivas de gráficos", Combinatorica , 13 (1): 65–81, doi : 10.1007 / BF01202790 , MR 1221177.
- Gross, Jonathan L .; Yellen, Jay (2006), "Caracterización de grafos fuertemente orientables", Teoría de grafos y sus aplicaciones , Matemáticas discretas y sus aplicaciones (Boca Raton) (2ª ed.), Chapman & Hall / CRC, Boca Raton, FL, págs. 498– 499, ISBN 978-1-58488-505-4, MR 2181153.
- Khuller, Samir (1989), "Descomposiciones del oído" (PDF) , SIGACT News , 20 (1): 128.
- Lovász, László (1972), "Una nota sobre gráficos factor-críticos", Studia Sci. Matemáticas. Colgado. , 7 : 279–280, MR 0335371.
- Lovász, László (1985), "Computación oídos y ramificaciones en paralelo", 26º Simposio anual sobre los fundamentos de la informática , págs. 464–467, doi : 10.1109 / SFCS.1985.16.
- Maon, Y .; Schieber, B .; Vishkin, U. (1986), "Búsqueda de descomposición del oído paralelo (EDS) y numeración ST en gráficos", Theoretical Computer Science , 47 (3): 277-298, doi : 10.1016 / 0304-3975 (86) 90153-2 , MR 0882357.
- Miller, G .; Ramachandran, V. (1986), Eficiente descomposición paralela del oído con aplicaciones , Manuscrito inédito.
- Robbins, HE (1939), "Un teorema sobre gráficos, con una aplicación a un problema de control de tráfico" (PDF) , American Mathematical Monthly , 46 (5): 281-283, doi : 10.2307 / 2303897 , JSTOR 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), la secuencia de Mondshein , arXiv : 1311.0750 , bibcode : 2013arXiv1311.0750S.
- Schrijver, Alexander (2003), Optimización combinatoria. Poliedros y eficiencia. Vol A , Springer-Verlag, ISBN 978-3-540-44389-6.
- Szegedy, Balázs ; Szegedy, Christian (2006), "Espacios simplécticos y descomposición auricular de matroides", Combinatorica , 26 (3): 353–377, doi : 10.1007 / s00493-006-0020-3 , MR 2246153.
- Whitney, H. (1932), "Gráficos planos y no separables", Transactions of the American Mathematical Society , 34 (2): 339–362, doi : 10.1090 / S0002-9947-1932-1501641-2 , JSTOR 1989545.