teorema de petersen

Un emparejamiento perfecto (bordes rojos), en el gráfico de Petersen . Dado que el gráfico de Petersen es cúbico y no tiene puentes , cumple las condiciones del teorema de Petersen.

Un gráfico cúbico (pero no sin puente) sin coincidencia perfecta, que muestra que la condición sin puente en el teorema de Petersen no se puede omitir

En la disciplina matemática de la teoría de grafos , el teorema de Petersen , que lleva el nombre de Julius Petersen , es uno de los primeros resultados de la teoría de grafos y se puede enunciar de la siguiente manera:

Teorema de Petersen. Cada gráfico cúbico sin puentes contiene una coincidencia perfecta . ^[1]

En otras palabras, si un gráfico tiene exactamente tres aristas en cada vértice, y cada arista pertenece a un ciclo, entonces tiene un conjunto de aristas que tocan cada vértice exactamente una vez.

Prueba

Demostramos que para cada gráfico cúbico sin puentes G = ( V , E ) tenemos que para cada conjunto U ⊆ V el número de componentes conectados en el gráfico inducido por V  −  U con un número impar de vértices es como máximo la cardinalidad de Ud . Entonces, según el teorema de Tutte, G contiene una coincidencia perfecta.

Sea G _i una componente con un número impar de vértices en el gráfico inducido por el conjunto de vértices V  −  U. Sea V _i los vértices de G _i y sea m _i el número de aristas de G con un vértice en _Vi y un vértice en U. Por un simple argumento de doble conteo tenemos que

${\displaystyle \sum \nolimits _{v\in V_{i}}\deg _{G}(v)=2|E_{i}|+m_{i},}$

donde E _i es el conjunto de aristas de G _i con ambos vértices en V _i . Desde

${\displaystyle \sum \nolimits _{v\in V_{i}}\deg _{G}(v)=3|V_{i}|}$

es un número impar y 2| mi _yo | es un número par, se deduce que m _i tiene que ser un número impar. Además, dado que G no tiene puentes, tenemos que m _i  ≥ 3 .

Sea m el número de aristas en G con un vértice en U y un vértice en el gráfico inducido por V  −  U. Cada componente con un número impar de vértices aporta al menos 3 aristas a m , y estas son únicas, por lo tanto, el número de dichos componentes es como máximo m /3 . En el peor de los casos, cada arista con un vértice en U contribuye a m , y por tanto m  ≤ 3| U | . Obtenemos

${\displaystyle |U|\geq {\frac {1}{3}}m\geq |\{{\text{components with an odd number of vertices}}\}|,}$

lo que muestra que se cumple la condición del teorema de Tutte .

Historia

El teorema se debe a Julius Petersen , un matemático danés. Puede considerarse como uno de los primeros resultados de la teoría de grafos . El teorema aparece por primera vez en el artículo de 1891 " Die Theorie der regulären graphs ". ^[1] Según los estándares actuales, la demostración del teorema de Petersen es complicada. Una serie de simplificaciones de la prueba culminaron en las pruebas de Frink (1926) y König (1936).

En los libros de texto modernos, el teorema de Petersen se aborda como una aplicación del teorema de Tutte .

Aplicaciones

• En un gráfico cúbico con una coincidencia perfecta, los bordes que no están en la coincidencia perfecta forman un factor de 2 . Al orientar el factor 2, los bordes de la combinación perfecta se pueden extender a caminos de longitud tres, por ejemplo, tomando los bordes orientados hacia afuera. Esto muestra que cada gráfico cúbico sin puentes se descompone en caminos de aristas disjuntas de longitud tres. ^[2]
• El teorema de Petersen también se puede aplicar para demostrar que cada gráfico plano máximo se puede descomponer en un conjunto de caminos de bordes disjuntos de longitud tres. En este caso, la gráfica dual es cúbica y no tiene puentes, por lo que según el teorema de Petersen tiene una coincidencia, que corresponde en la gráfica original a un par de caras de triángulos adyacentes. Cada par de triángulos da un camino de longitud tres que incluye el borde que conecta los triángulos con dos de los cuatro bordes restantes del triángulo. ^[3]
• Aplicando el teorema de Petersen a la gráfica dual de una malla triangular y conectando pares de triángulos que no coinciden, se puede descomponer la malla en franjas cíclicas de triángulos . Con algunas transformaciones adicionales, se puede convertir en una sola franja y, por lo tanto, proporciona un método para transformar una malla triangular de modo que su gráfico dual se vuelva hamiltoniano . ^[4]

Extensiones

Número de coincidencias perfectas en gráficos cúbicos sin puente

Lovász y Plummer conjeturaron que el número de coincidencias perfectas contenidas en un gráfico cúbico sin puentes es exponencial en el número de vértices del gráfico n . ^[5] La conjetura fue probada por primera vez para gráficos bipartitos , cúbicos y sin puente por Voorhoeve (1979), más tarde para gráficos planos , cúbicos y sin puente por Chudnovsky y Seymour (2012). El caso general fue resuelto por Esperet et al. (2011), donde se demostró que cada gráfico cúbico sin puentes contiene al menos coincidencias perfectas. ${\displaystyle 2^{n/3656}}$

Versiones algorítmicas

Biedl et al. (2001) analizan versiones eficientes del teorema de Petersen. Basado en la prueba de Frink ^[6] obtienen un algoritmo O ( n log ⁴ n ) para calcular una coincidencia perfecta en un gráfico cúbico sin puentes con n vértices. Si el gráfico es además plano, el mismo artículo proporciona un algoritmo O ( n ) . Su límite de tiempo O ( n log ⁴ n ) se puede mejorar en función de mejoras posteriores en el tiempo para mantener el conjunto de puentes en un gráfico dinámico. ^[7] Diks y Stanczyk (2010) ofrecieron mejoras adicionales, reduciendo el tiempo vinculado a O ( n log ² n ) o (con estructuras de datos aleatorios adicionales ) O ( n log n (log log n ) ³ ) .

Mayor grado

Si G es un grafo regular de grado d cuya conectividad de aristas es al menos d  − 1, y G tiene un número par de vértices, entonces tiene una coincidencia perfecta. Más claramente, cada arista de G pertenece al menos a una combinación perfecta. La condición sobre el número de vértices se puede omitir en este resultado cuando el grado es impar, porque en ese caso (según el lema del protocolo de enlace ) el número de vértices siempre es par. ^[8]

Notas

1. Petersen (1891).
2. Véase, por ejemplo, Bouchet y Fouquet (1983).
3. Häggkvist y Johansson (2004).
4. Meenakshisundaram y Eppstein (2004).
5. Lovász y Plummer (1986).
6. Frink (1926).
7. Thorup (2000).
8. Naddef y Pulleyblank (1981), Teorema 4, p. 285.

Referencias

• Biedl, Teresa C .; Bosé, Prosenjit ; Demaine, Erik D .; Lubiw, Anna (2001), "Algoritmos eficientes para el teorema de coincidencia de Petersen", Journal of Algorithms , 38 (1): 110–134, doi :10.1006/jagm.2000.1132, MR  1810434
• Bouchet, André; Fouquet, Jean-Luc (1983), "Trois type de décompositions d'un graphe en chaînes", en C. Berge; D. Bresson; P. Camión; JF Maurras; F. Sterboul (eds.), Matemáticas combinatorias: Actas del Coloquio internacional sobre teoría de grafos y combinatoria (Marsella-Luminy, 1981) , Estudios de matemáticas de Holanda Septentrional (en francés), vol. 75, Holanda Septentrional, págs. 131-141, doi :10.1016/S0304-0208(08)73380-2, ISBN 978-0-444-86512-0, señor  0841287
• Chudnovsky, María ; Seymour, Paul (2012), "Emparejamientos perfectos en gráficos cúbicos planos", Combinatorica , 32 (4): 403–424, doi :10.1007/s00493-012-2660-9, SEÑOR  2965284
• Diks, Krzysztof; Stanczyk, Piotr (2010), "Emparejamiento perfecto para gráficos cúbicos biconectados en tiempo O ( n log ² n ) ", en van Leeuwen, Jan ; Muscholl, Anca ; Péleg, David ; Pokorný, Jaroslav; Rumpe, Bernhard (eds.), SOFSEM 2010: 36.ª Conferencia sobre tendencias actuales en la teoría y la práctica de la informática, Špindlerův Mlýn, República Checa, 23 al 29 de enero de 2010, Actas , Lecture Notes in Computer Science, vol. 5901, Springer, págs. 321–333, doi :10.1007/978-3-642-11266-9_27, ISBN 978-3-642-11265-2
• Espéret, Louis; Kardoš, František; Rey, Andrés D.; Král', Daniel ; Norine, Serguei (2011), "Muchas coincidencias perfectas exponencialmente en gráficas cúbicas", Avances en Matemáticas , 227 (4): 1646–1664, arXiv : 1012.2878 , doi : 10.1016/j.aim.2011.03.015 , MR  2799808
• Frink, Orrin (1926), "Una prueba del teorema de Petersen", Annals of Mathematics , segunda serie, 27 (4): 491–493, doi :10.2307/1967699, JSTOR  1967699
• Häggkvist, Roland; Johansson, Robert (2004), "Una nota sobre las descomposiciones de bordes de gráficos planos", Matemáticas discretas , 283 (1–3): 263–266, doi : 10.1016/j.disc.2003.11.017 , MR  2061501
• König, Dénes (1936), Theorie der endlichen und unendlichen Graphen; kombinatorische Topologie der Streckenkomplexe.
• Lovász, László ; Plummer, MD (1986), Teoría de correspondencias , Annals of Discrete Mathematics, vol. 29, Holanda Septentrional, ISBN 0-444-87916-1, señor  0859549
• Meenakshisundaram, Gopi; Eppstein, David (2004), "Triangulación de variedades de una sola tira con topología arbitraria", Proc. 25ª Conferencia. EUR. Asociación. para gráficos por computadora (Eurographics '04) , Foro de gráficos por computadora, vol. 23, págs. 371–379, arXiv : cs.CG/0405036 , doi : 10.1111/j.1467-8659.2004.00768.x
• Naddef, D.; Pulleyblank, WR (1981), "Emparejamientos en gráficos regulares", Matemáticas discretas , 34 (3): 283–291, doi : 10.1016/0012-365X(81)90006-6 , SEÑOR  0613406.
• Petersen, Julius (1891), "Die Theorie der regulären Graphs", Acta Mathematica , 15 : 193–220, doi : 10.1007/BF02392606
• Thorup, Mikkel (2000), "Conectividad gráfica totalmente dinámica casi óptima", Proc. 32º Simposio ACM sobre Teoría de la Computación , págs. 343–350, doi :10.1145/335305.335345, ISBN 1-58113-184-4, señor  2114549
• Voorhoeve, Marc (1979), "Un límite inferior para los permanentes de ciertas matrices (0,1), Indagationes Mathematicae , 82 (1): 83–86, doi : 10.1016/1385-7258(79)90012-X , señor  0528221