Graf de Petersen

En l'àmbit matemàtic de la teoria de grafs, el graf de Petersen és un graf no dirigit amb 10 vèrtexs i 15 arestes. És un graf petit que serveix com a exemple i com a contraexemple per a molts problemes de teoria de grafs. El graf de Petersen rep aquest nom pel matemàtic danès Julius Petersen, qui el va construir l'any 1898 com el més petit graf cúbic sense arestes de tall que no admet una 3-aresta-coloració.

El graf de Petersen s'acostuma a representar com un pentàgon amb un pentacle a l'interior.

Tot i que s'acostuma a atribuir el descobriment del graf a Petersen, de fet va sorgir 12 anys abans en una publicació d'Alfred Kempe. Kempe observà que els seus vèrtexs poden representar les 10 rectes de la configuració de Desargues, i les seves arestes representen parells de rectes que no s'intersecten a un dels 10 punts de la configuració.

Donald Knuth afirma que el graf de Petersen és

«	(anglès) a remarkable configuration that serves as a counterexample to many optimistic predictions about what might be true for graphs in general.	(català) una configuració notable que serveix com a contraexemple a moltes prediccions optimistes sobre allò que hauria de ser cert per a grafs en general.	»
— Donald Knuth, The Art of Computer Programming

Construccions

El graf de Petersen com a graf de Kneser $KG_{5,2}$

El graf de Petersen és el complement del graf línia de $K_{5}$. També és el graf de Kneser $KG_{5,2}$; és a dir, té un vèrtex per a cada subconjunt de 2 elements d'un conjunt de 5 elements, i dos vèrtexs estan connectats per una aresta si i només si els corresponents subconjunts de 2 elements no tenen elements en comú. Com que el graf de Petersen és un graf de Kneser de la forma $KG_{2n-1,n-1}$, és un exemple de graf senar.

Geomètricament, el graf de Petersen és el graf format pels vèrtexs i arestes del semidodecàedre, això és, un dodecàedre on s'identifiquen els vèrtexs, arestes i cares oposats.

Immersions

El graf de Petersen és no planar. Tot graf no planar té com a menors o bé el graf complet $K_{5}$, o bé el graf bipartit complet $K_{3,3}$, però el graf de Petersen els conté tots dos com a menors. El menor $K_{5}$ es pot formar per contracció de les arestes d'un aparellament perfecte, per exemple les cinc arestes petites de la primera figura. El menor $K_{3,3}$ es pot formar per supressió d'un vèrtex (per exemple el vèrtex central de la representació 3-simètrica), i contraient una aresta cap a cada veí del vèrtex suprimit.

(Figura 1) El graf de Petersen té nombre de creuament 2 i és 1-planar.

La representació gràfica plana més habitual i simètrica del graf de Petersen, amb un pentacle a l'interior d'un pentàgon, té 5 encreuaments. Tot i això, aquesta no és la representació òptima que minimitza el nombre d'encreuaments; existeix una altra representació (il·lustrada en la figura 1) amb només 2 encreuaments. Per tant, el graf de Petersen té nombre d'encreuament 2. Tota aresta d'aquesta representació té, com a màxim, un encreuament, i per tant el graf de Petersen és 1-planar. Sobre un tor, es pot dibuixar el graf de Petersen de tal manera que no tingui arestes creuades; per tant, té gènere orientable 1.

El graf de Petersen és un graf distància unitat: es pot dibuixar sobre el pla de manera que cada aresta tingui longitud 1.

El graf de Petersen també es pot dibuixar (amb encreuaments) sobre el pla de manera que totes les arestes tinguin idèntica longitud. És a dir, és un graf distància unitat.

La superfície no orientable més simple sobre la qual es pot dibuixar sense encreuaments el graf de Petersen és el pla projectiu. Aquesta és la immersió donada per la construcció del graf de Petersen com un semidodecàedre.

Simetries

El graf de Petersen és fortament regular (amb signatura srg(10,3,0,1)). També és simètric, la qual cosa vol dir que és aresta-transitiu i vèrtex-transitiu. De fet, és 3-aresta-transitiu: tot camí dirigit format per 3 arestes del graf de Petersen es pot transformar en un altre camí dirigit de longitud 3 mitjançant una simetria del graf. És un dels únics 13 grafs cúbics distància-regulars.

El grup d'automorfismes del graf de Petersen és el grup simètric $S_{5}$; l'acció de $S_{5}$ sobre el graf de Petersen és una conseqüència de la seva construcció com a graf de Kneser. Tot homomorfisme del graf de Petersen en ell mateix que no identifiqui vèrtexs adjacents és un automorfisme.

Tot i el seu alt grau de simetria, el graf de Petersen no és un graf de Cayley. És el graf vèrtex-transitiu més petit que no és un graf de Cayley.

Camins i cicles hamiltonians

El graf de Petersen és hipohamiltonià: si s'elimina un vèrtex qualsevol, com el vèrtex central d'aquesta representació, el graf resultant és hamiltonià. Aquesta representació amb simetria d'ordre 3 fou donada per Kempe (1886).

El graf de Petersen té un camí hamiltonià, però no té cap cicle hamiltonià. És el graf cúbic sense arestes de tall més petit que no conté cap cicle hamiltonià. És hipohamiltonià, en el sentit que, encara que no tingui cap cicle hamiltonià, si s'elimina un vèrtex qualsevol s'obté un graf hamiltonià, i és el graf hipohamiltonià més petit.

Com que és un graf vèrtex-transitiu connex finit que no conté cap cicle hamiltonià, el graf de Petersen és un contraexemple d'una variant de la conjectura de Lovász, però la formulació estàndard de la conjectura es pregunta per un camí hamiltonià, i el graf de Petersen la compleix.

Només es coneixen 5 grafs vèrtex-transitius connexos que no contenen cap cicle hamiltonià: el graf complet K₂, el graf de Petersen, el graf de Coxeter i dos grafs obtinguts a partir dels grafs de Petersen i de Coxeter substituint cada vèrtex per un triangle. Si G és un graf r-regular i 2-connex amb, com a màxim, 3r + 1 vèrtexs, llavors o bé G és hamiltonià o bé G és el graf de Petersen.

Per veure que el graf de Petersen no té cap cicle hamiltonià C, considerem les arestes del tall que desconnecta el cicle interior de longitud 5 del cicle exterior (en vermell, a la figura):

Si hi ha un cicle hamiltonià, cal escollir un nombre parell d'aquestes arestes. Si només se n'escullen dues, els seus vèrtexs terminals han de ser adjacents en els dos 5-cicles, la qual cosa no és possible; per tant, cal escollir 4 de les arestes del tall. Suposem que l'aresta que no s'escull és la superior (els altres casos són equivalents per simetria). De les 5 arestes del cicle exterior, cal escollir les dues arestes superiors, s'han de deixar les dues arestes laterals, i per tant cal prendre l'aresta inferior. Llavors cal prendre les dues arestes superiors del cicle interior, però això completa un cicle no generador, que no pot formar part d'un cicle hamiltonià.

Dues vistes de l'escala de Möbius M₁₆

Alternativament, es poden descriure els grafs 3-regulars de 10 vèrtexs i mostrar que cap d'ells és el graf de Petersen, trobant-hi un cicle més curt que qualsevol cicle del graf de Petersen. Tot graf 3-regular hamiltonià de 10 vèrtexs consisteix d'un cicle C de 10 vèrtexs i 5 arestes. Si una aresta qualsevol connecta dos vèrtexs que estan a una distància igual a 2 o 3 en el cicle C, llavors el graf conté un cicle de longitud 3 o 4, i per tant no pot ser el graf de Petersen. Si dues arestes connecten vèrtexs oposats de C amb vèrtexs situats a una distància igual a 4 per C, llavors hom té, de nou, un cicle de longitud 4. L'últim cas restant és una escala de Möbius formada connectant cada parell de vèrtexs oposats mitjançant una aresta, que de nou conté un cicle de longitud 4. Com que el graf de Petersen té cintura igual a 5, no es pot formar per aquest procediment, i no conté cap cicle hamiltonià.

Coloració

Una 4-coloració de les arestes del graf de Petersen

Una 3-coloració dels vèrtexs del graf de Petersen

El graf de Petersen té nombre cromàtic 3, la qual cosa vol dir que els seus vèrtexs es poden acolorir amb 3 colors, de tal manera que cap aresta connecta vèrtexs del mateix color.

El graf de Petersen té índex cromàtic 4; una coloració de les arestes requereix 4 colors. Per tal de donar-ne una demostració, cal comprovar quatre casos per veure que no existeix cap 3-coloració de les arestes.

Addicionalment, el graf té índex cromàtic fraccionari 3, demostrant així que la diferència entre l'índex cromàtic i l'índex cromàtic fraccionari és, com a màxim, 1. La conjectura de Goldberg-Seymour afirma que aquesta és la màxima diferència possible.

El nombre de Thue (una variant de l'índex cromàtic) del graf de Petersen és 5.

El graf de Petersen necessita almenys 3 colors en qualsevol coloració (possiblement impròpia) que trenqui totes les seves simetries; és a dir, el seu nombre diferenciador és 3. Llevat dels grafs complets, és l'únic graf de Kneser que té un nombre diferenciador diferent de 2.

Altres propietats

El graf de Petersen:

• és 3-connex, i per tant, és 3-aresta-connex i no té arestes de tall.
• té nombre d'independència igual a 4 i és tripartit.
• és cúbic, té nombre dominant 3, i té un aparellament perfecte i un 2-factor.
• té 6 aparellaments perfectes diferents.
• és el més petit graf cúbic amb cintura igual a 5. (És l'única (3,5)-gàbia. De fet, com que només té 10 vèrtexs, és l'únic (3,5)-graf de Moore.)
• té radi 2 i diàmetre 2. És el graf cúbic més gran amb diàmetre igual a 2.
• té espectre −2, −2, −2, −2, 1, 1, 1, 1, 1, 3.
• té 2.000 arbres d'expansió, el màxim d'entre tots els grafs cúbics amb 10 vèrtexs.
• té com a polinomi cromàtic l'expressió $t(t-1)(t-2)\left(t^{7}-12t^{6}+67t^{5}-230t^{4}+529t^{3}-814t^{2}+775t-352\right)$.
• té com a polinomi característic l'expressió $(t-1)^{5}(t+2)^{4}(t-3)$, cosa que fa que sigui un graf integral (és a dir, un graf per al qual el seu espectre està format només per nombres enters).

Conjectura de coloració de Petersen

Segons DeVos, Nešetřil i Raspaud,

«	(anglès) A cycle of a graph G is a set C ⊆ E(G) so that every vertex of the graph (V(G),C) has even degree. If G,H are graphs, we define a map φ: E(G) → E(H) to be cycle-continuous if the pre-image of every cycle of H is a cycle of G. A fascinating conjecture of [François] Jaeger asserts that every bridgeless graph has a cycle-continuous mapping to the Petersen graph. Jaeger showed that if this conjecture is true, then so are the 5-cycle-double-cover conjecture and the Berge-Fulkerson conjecture.	(català) Un cicle d'un graf G és un conjunt C ⊆ E(G) tal que tot vèrtex del graf (V(G), C) té grau parell. Si G i H són dos grafs, diem que una aplicació φ: E(G) → E(H) és cicle-contínua si la antiimatge de qualsevol cicle de H és un cicle de G. Una conjectura fascinant de [François] Jaeger afirma que tot graf sense arestes de tall té una aplicació cicle-contínua cap al graf de Petersen. Jaeger demostrà que, si aquesta conjectura és certa, llavors també són certes la conjectura del 5-cicle de doble cobertura i la conjectura de Berge-Fulkerson.	»
— Matt DeVos, Jaroslav Nešetřil i André Raspaud, On edge-maps whose inverse preserves flows or tensions

Grafs relacionats

La família de Petersen

El graf de Petersen generalitzat G(n,k) es construeix connectant els vèrtexs d'un n-gon als corresponents vèrtexs d'un polígon estrellat amb símbol de Schläfli {n/k}. Per exemple, amb aquesta notació, el graf de Petersen és G(5,2): es pot formar connectant els vèrtexs corresponents d'un pentàgon i una estrella de cinc puntes, i les arestes de l'estrella connecten un de cada dos vèrtexs.

Els grafs de Petersen generalitzats inclouen l'n-prisma G(n,1), el graf de Dürer G(6,2), el graf de Möbius-Kantor G(8,3), el dodecàedre G(10,2), el graf de Desargues G(10,3) i el graf de Nauru G(12,5).

La família de Petersen consisteix dels set grafs que es poden formar a partir del graf de Petersen per zero o més aplicacions de transformacions Δ-Y o Y-Δ. El graf complet K₆ també forma part de la família de Petersen. Aquests grafs formen els menors prohibits per als grafs submergibles sense enllaços, grafs que es poden submergir en l'espai tridimensional de tal manera que no hi ha dos cicles enllaçats.

El graf de Clebsch conté múltiples còpies del graf de Petersen com a subgrafs induïts: per a cada vèrtex v del graf de Clebsch, els 10 vèrtexs no adjacents a v indueixen una còpia del graf de Petersen.

Bibliografia

• Exoo, Geoffrey; Harary, Frank; Kabell, Jerald «The crossing numbers of some generalized Petersen graphs». Mathematica Scandinavica, 48, 1981, pàg. 184–188.
• Coxeter, H. S. M. «Self-dual configurations and regular graphs». Bulletin of the American Mathematical Society, 56, 5, 1950, pàg. 413–455. DOI: 10.1090/S0002-9904-1950-09407-5.
• Holton, D. A.; Sheehan, J. The Petersen Graph. Cambridge University Press, 1993. DOI 10.2277/0521435943. ISBN 0-521-43594-3 [Consulta: 22 juny 2016]. 
• Jakobson, Dmitry; Rivin, Igor «On some extremal problems in graph theory». Cornell University Library, 1999. arXiv: math.CO/9907050.
• Kempe, A. B. «A memoir on the theory of mathematical form». Philosophical Transactions of the Royal Society of London, 177, 1886, pàg. 1–70. DOI: 10.1098/rstl.1886.0002.
• Lovász, László. Combinatorial Problems and Exercises. 2a edició. North-Holland, 1993. ISBN 0-444-81504-X. 
• Petersen, Julius «Sur le théorème de Tait». L'Intermédiaire des Mathématiciens, 5, 1898, pàg. 225–227.
• Schwenk, A. J. «Enumeration of Hamiltonian cycles in certain generalized Petersen graphs». Journal of Combinatorial Theory, 47, 1, 1989, pàg. 53–59. DOI: 10.1016/0095-8956(89)90064-6.
• Valdes, L. «Extremal properties of spanning trees in cubic graphs». Congressus Numerantium, 85, 1991, pàg. 143–160.
• Watkins, Mark E. «A Theorem on Tait Colorings with an Application to the Generalized Petersen Graphs». Journal of Combinatorial Theory, 6, 2, 1969, pàg. 152–164. DOI: 10.1016/S0021-9800(69)80116-X.
• Foster, Ronald M.; Bouwer, I.Z.. Charles Babbage Research Centre. The Foster Census: R.M. Foster's Census of Connected Symmetric Trivalent Graphs. Universitat de Michigan, 1988. ISBN 0-919611-19-2. 

Enllaços externs

• Keller, Mitch. Kneser graphs a PlanetMath
• Weisstein, Eric W., «Petersen Graph» a MathWorld (en anglès).
• Petersen Graph a la On-Line Encyclopedia of Integer Sequences