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 en la teoría de grafos y puede enunciarse de la siguiente manera:
![](http://wikiimg.tojsiabtv.com/wikipedia/commons/thumb/a/a9/Petersen-graph-factors.svg/300px-Petersen-graph-factors.svg.png)
![](http://wikiimg.tojsiabtv.com/wikipedia/commons/thumb/4/44/Sylvester_counter.svg/220px-Sylvester_counter.svg.png)
Teorema de Petersen. Cada cúbica , sin puente gráfico que contiene una correspondencia perfecta . [1]
En otras palabras, si una gráfica tiene exactamente tres aristas en cada vértice, y cada arista pertenece a un ciclo, entonces tiene un conjunto de aristas que toca cada vértice exactamente una vez.
Prueba
Mostramos que por cada cúbico, sin puente gráfico G = ( V , E ) hemos que por cada conjunto U ⊆ V el número de componentes conectados en el gráfico inducida por V - U con un número impar de vértices es como máximo la cardinalidad de T . Entonces, según el teorema de Tutte, G contiene una correspondencia perfecta.
Deje G i ser un componente con un número impar de vértices en el gráfico inducida por el conjunto de vértices V - U . Deje V i denotan los vértices de G i y dejar m i denota el número de bordes de G con un vértice en V i y un vértice en U . Por un simple argumento de doble conteo tenemos que
donde E i es el conjunto de aristas de G i con ambos vértices en V i . Desde
es un número impar y 2 | E i | 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 .
Deje que m sea el número de aristas en G con un vértice en U y un vértice en el gráfico inducida por V - U . Cada componente con un número impar de vértices aporta al menos 3 aristas am , y estos son únicos, 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 am , y por lo tanto m ≤ 3 | U | . Obtenemos
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 primero 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 culminó en las pruebas de Frink (1926) y König (1936) .
En los libros de texto modernos, el teorema de Petersen se trata 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 coincidencia perfecta se pueden extender a trayectos de longitud tres, por ejemplo, tomando los bordes orientados hacia afuera. Esto muestra que cada grafo cúbico sin puentes se descompone en trayectorias de borde disjunto de longitud tres. [2]
- El teorema de Petersen también se puede aplicar para demostrar que cada grafo plano máximo se puede descomponer en un conjunto de trayectorias de borde disjunto de longitud tres. En este caso, el gráfico dual es cúbico y sin puentes, por lo que según el teorema de Petersen tiene una coincidencia, que corresponde en el gráfico original a un emparejamiento 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 al gráfico dual de una malla triangular y conectando pares de triángulos que no coinciden, se puede descomponer la malla en tiras cíclicas de triángulos . Con algunas transformaciones adicionales, se puede convertir en una sola tira 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 puentes
Se conjeturó por Lovász y Plummer que el número de emparejamientos perfectos contenida en un cúbico , sin puente gráfica es exponencial en el número de los vértices de la gráfica n . [5] La conjetura fue probada primero para grafos bipartitos , cúbicos, sin puentes por Voorhoeve (1979) , más tarde para grafos planos , cúbicos, sin puentes por Chudnovsky y Seymour (2012) . El caso general fue resuelto por Esperet et al. (2011) , donde se demostró que cada grafo cúbico sin puentes contiene al menos combinaciones perfectas.
Versiones algorítmicas
Biedl y col. (2001) discuten versiones eficientes del teorema de Petersen. Con base en la prueba de Frink [6] , obtienen un algoritmo O ( n log 4 n ) para calcular una correspondencia perfecta en un grafo cúbico sin puentes con n vértices. Si el gráfico es además plano, el mismo papel da un algoritmo O ( n ) . Su límite de tiempo O ( n log 4 n ) se puede mejorar en función de las mejoras posteriores en el tiempo para mantener el conjunto de puentes en un gráfico dinámico. [7] Otras mejoras, reduciendo el tiempo ligado a O ( n log 2 n ) o (con adicionales aleatorios estructuras de datos ) O ( n log n (log log n ) 3 ) , se les dio por Diks y Stanczyk (2010) .
Mayor grado
Si G es un gráfico regular de grado d cuya conectividad de borde es al menos d - 1, y G tiene un número par de vértices, entonces tiene una coincidencia perfecta. Más fuertemente, cada borde de G pertenece al menos a una coincidencia perfecta. La condición sobre el número de vértices se puede omitir de este resultado cuando el grado es impar, porque en ese caso (por el lema de apretón de manos ) el número de vértices es siempre par. [8]
Notas
- ↑ a b Petersen (1891) .
- ^ Véase, por ejemplo, Bouchet y Fouquet (1983) .
- ^ Häggkvist y Johansson (2004) .
- ^ Meenakshisundaram y Eppstein (2004) .
- ^ Lovász y Plummer (1986) .
- ^ Frink (1926) .
- ^ Thorup (2000) .
- ^ Naddef y Pulleyblank (1981) , Teorema 4, p. 285.
Referencias
- Biedl, Therese C .; Bose, 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 types de décompositions d'un graphe en chaînes", en C. Berge, P. Camion, D. Bresson; Sterboul, F. (eds.), Combinatorial Mathematics: Proceedings of the International Colloquium on Graph Theory and Combinatorics (Marseille-Luminy, 1981) , North-Holland Mathematics Studies (en francés), 75 , North-Holland, págs. 131– 141, doi : 10.1016 / S0304-0208 (08) 73380-2 , Sr. 0841287
- Chudnovsky, Maria ; Seymour, Paul (2012), " Emparejamientos perfectos en gráficas cúbicas planas", Combinatorica , 32 (4): 403–424, doi : 10.1007 / s00493-012-2660-9 , MR 2965284
- Diks, Krzysztof; Stanczyk, Piotr (2010), "Concordancia perfecta para gráficas cúbicas biconectadas en tiempo O ( n log 2 n ) ", en van Leeuwen, Jan ; Muscholl, Anca ; Peleg, David ; Pokorný, Jaroslav; Rumpe, Bernhard (eds.), SOFSEM 2010: 36th Conference on Current Trends in Theory and Practice of Computer Science, Špindlerův Mlýn, República Checa, 23 al 29 de enero de 2010, Actas , Lecture Notes in Computer Science, 5901 , Springer, págs. 321–333, doi : 10.1007 / 978-3-642-11266-9_27
- Esperet, Louis; Kardoš, František; King, Andrew D .; Králʼ, Daniel ; Norine, Serguei (2011), "Exponencialmente muchos emparejamientos perfectos en gráficas cúbicas", Advances in Mathematics , 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 , Second Series, 27 (4): 491–493, doi : 10.2307 / 1967699
- Häggkvist, Roland; Johansson, Robert (2004), "A note on edge-descompositions of planar graphs", Discrete Mathematics , 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 emparejamiento , Annals of Discrete Mathematics, 29 , Holanda Septentrional, ISBN 0-444-87916-1, MR 0859549
- Meenakshisundaram, Gopi; Eppstein, David (2004), "Triangulación de una sola tira de variedades con topología arbitraria", Proc. 25ª Conf. EUR. Assoc. for Computer Graphics (Eurographics '04) , Computer Graphics Forum, 23 , págs. 371–379, arXiv : cs.CG/0405036 , doi : 10.1111 / j.1467-8659.2004.00768.x
- Naddef, D .; Pulleyblank, WR (1981), "Coincidencias en gráficas regulares", Matemáticas discretas , 34 (3): 283–291, doi : 10.1016 / 0012-365X (81) 90006-6 , MR 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, MR 2114549
- Voorhoeve, Marc (1979), "Un límite inferior para las permanentes de ciertas matrices (0,1)", Indagationes Mathematicae , 82 (1): 83-86, doi : 10.1016 / 1385-7258 (79) 90012-X , MR 0528221