Grafo di Petersen

Nel campo matematico della teoria dei grafi, il grafo di Petersen è un grafo non orientato con 10 vertici e 15 spigoli. È un piccolo grafo che serve come utile esempio e controesempio per molti problemi di teoria dei grafi. Il grafo di Petersen prende il nome da Julius Petersen, che nel 1898 lo costruì per essere il più piccolo grafo cubico privo di ponti senza nessuna colorazione dei tre spigoli.^[1]

Il grafo di Petersen è disegnato più comunemente come un pentagono con un pentagramma all'interno, con cinque raggi.

Sebbene il grafo sia generalmente attribuito a Petersen, esso era apparso in realtà 12 anni prima, in un saggio di A. B. Kempe (1886). Kempe osservò che i suoi vertici possono rappresentare le dieci linee della configurazione di Desargues, e che i suoi spigoli rappresentano coppie di linee che non s'incontrano in uno dei dieci punti della configurazione.

Donald Knuth afferma che il grafo di Petersen è "una notevole configurazione che serve da controesempio a molte previsioni ottimistiche su ciò che potrebbe essere vero per i grafi in generale".^[2]

Costruzioni

Il grafo di Petersen come grafo di Kneser ${\displaystyle KG_{5,2}}$.

Il grafo di Petersen è il complemento del grafo lineare di ${\displaystyle K_{5}}$. Esso è anche il grafo di Kneser ${\displaystyle KG_{5,2}}$; questo significa che ha un solo vertice per ciascun sottoinsieme di 2 elementi di un insieme di 5 elementi, e due vertici sono collegati da uno spigolo se e solo se i sottoinsiemi corrispondenti di 2 elementi sono disgiunti l'uno dall'altro. Come grafo di Kneser della forma ${\displaystyle KG_{2n-1,n-1}}$ è un esempio di grafo dispari.

Geometricamente, il grafo di Petersen è il grafo formato dai vertici e dagli spigoli dell'emidodecaedro, cioè, un dodecaedro con punti, linee e facce opposte identificate insieme.

Incorporazioni

Il grafo di Petersen è non planare. Qualsiasi grafo non planare ha come minori o il grafo completo ${\displaystyle K_{5}}$, o il grafo bipartito completo ${\displaystyle K_{3,3}}$, ma il grafo di Petersen ha entrambi come minori. Il minore ${\displaystyle K_{5}}$ può essere formato contraendo gli spigoli di un abbinamento perfetto, per esempio per i cinque spigoli corti della prima figura. Il minore ${\displaystyle K_{3,3}}$ può essere formato cancellando un vertice (per esempio il vertice centrale del disegno 3-simmetrico) e contraendo uno spigolo incidente a ciascun vicino del vertice cancellato.

Il grafo di Petersen ha numero di incroci 2.

Il disegno planare più comune e simmetrico del grafo di Petersen, come un pentagramma dentro un pentagono, ha cinque incroci. Tuttavia, questo non è il disegno migliore per minimizzare gli incroci; esiste un altro disegno (mostrato nella figura) con solo due incroci. Così, il grafo di Petersen ha numero di incroci 2. Su un toro il grafo di Petersen può essere disegnato senza gli incroci degli spigoli; esso perciò ha genere orientabile 1.

Il grafo di Petersen è un grafo a distanza unitaria: può essere disegnato nel piano con ogni spigolo che ha lunghezza unitaria

Il grafo di Petersen può anche essere disegnato (con gli incroci) nel piano in modo tale che tutti gli spigoli abbiano uguale lunghezza. Cioè, è un grafo a distanza unitaria.

La più semplice superficie non orientabile sulla quale il grafo di Petersen può essere incorporato senza incroci è il piano proiettivo. Questa è l'incorporazione data dalla costruzione a emidodecaedro del grafo di Petersen. L'incorporazione del piano proiettivo può anche essere formata dal normale disegno pentagonale del grafo di Petersen ponendo un cross-cap dentro la stella a cinque punte al centro del disegno, e indirizzando gli spigoli della stella attraverso questo cross-cap; il disegno risultante ha sei facce pentagonali. Questa costruzione forma una mappa regolare e mostra che il grafo di Petersen ha genere non orientabile 1.

Simmetrie

Il grafo di Petersen è fortemente regolare (con firma srg(10,3,0,1)). È anche simmetrico, che significa che è transitivo sugli spigoli e transitivo sui vertici. Più nettamente, è 3-transitivo sugli archi: ogni cammino orientato con tre spigoli nel grafo di the Petersen può essere trasformato in ogni altro cammino di questo tipo mediante una simmetria del grafo.^[3] È uno dei soli 13 grafi cubici con distanze regolari.^[4]

Il gruppo di automorfismo del grafo di Petersen è il gruppo simmetrico ${\displaystyle S_{5}}$; l'azione di ${\displaystyle S_{5}}$ sul grafo di Petersen segue dalla sua costruzione come grafo di Kneser. Ogni omomorfismo del grafo di Petersen su sé stesso che non identifica i vertici adiacenti è un automorfismo. Come mostrato nelle figure, i disegni del grafo di Petersen possono esibire una simmetria a cinque vie o a tre vie, ma non è possibile disegnare il grafo di Petersen nel piano in modo tale che il disegno esibisce il gruppo di simmetria piena del grafo.

Malgrado il suo alto grado di simmetria, il grafo di Petersen non è un grafo di Cayley. È il più piccolo grafico transitivo sui vertici che non sia un grafo di Cayley.^[5]

Cammini e cicli hamiltoniani

Il grafo di Petersen è ipohamiltoniano: cancellando un qualsiasi vertice, come il vertice centrale nel disegno, il grafo rimanente è hamiltoniano. Questo disegno con simmetria di ordine 3 è quello dato da Kempel1886, Kempel (1886).

Il grafo di Petersen ha un cammino hamiltoniano ma nessun ciclo hamiltoniano. È il più piccolo grafo cubico privo di ponti senza cicli hamiltoniani. È ipohamiltoniano, che significa che sebbene non abbia cicli hamiltoniani, cancellare un qualsiasi vertice lo rende hamiltoniano, e in questo ambito è il più piccolo grafo ipohamiltoniano.

Come grafo finito connesso transitivo sui vertici che non ha un ciclo hamiltoniano, il grafo di Petersen è un controesempio di una variante della congettura di Lovász, ma la formulazione canonica della congettura richiede un cammino hamiltoniano ed è verificata dal grafo di Petersen.

Sono noti solo cinque grafi connessi transitivi sui vertici senza cicli hamiltoniani: il grafo completo K₂, il grafo di Petersen, il grafo di Coxeter e due grafi derivati dai grafi di Petersen e Coxeter sostituendo ciascun vertice con un triangolo.^[6] Se G è un grafo 2-connesso, r-regolare con al massimo 3r + 1 vertici, allora o G è hamiltoniano o è il grafo di Petersen.^[7]

Per vedere che il grafo di Petersen non ha un ciclo hamiltoniano C, descriviamo i grafi 3-regolari a dieci vertici che hanno effettivamente un ciclo hamiltoniano e mostriamo che nessuno di essi è il grafo di Petersen, trovando in ciascuno di essi un ciclo che è più breve di qualsiasi ciclo nel grafo di Petersen. Qualsiasi grafo 3-regolare hamiltoniano a dieci vertici consiste in un ciclo C a dieci vertici più cinque corde. Se una qualsiasi corda collega due vertici a distanza due o tre l'uno dall'altro lungo C, il grafo ha un 3-ciclo o 4-ciclo, e perciò non può essere un grafo di Petersen. Se due corde collegano due vertici opposti di C a vertici a distanza quattro lungo C, c'è di nuovo un 4-ciclo. Il solo caso rimanente è una scala di Möbius formata collegando ciascuna coppia di vertici opposti mediante una corda, che ha ancora un 4-ciclo. Poiché il grafo di Petersen ha calibro cinque, non può essere formata in questo modo e non ha un ciclo hamiltoniano.

Colorazione

Una 4-colorazione degli spigoli del grafo di Petersen.

Una 3-colorazione dei vertici del grafo di Petersen.

Il grafo di Petersen ha numero cromatico 3, che significa che i suoi vertici possono essere colorati con tre colori — ma non con due — in modo tale che nessuno spigolo colleghi vertici dello stesso colore.

Il grafo di Petersen ha indice cromatico 4; la colorazione degli spigoli richiede quattro colori. Una prova di ciò richiede il controllo di quattro casi per dimostrare che non esiste alcuna 3-colorazione degli spigoli. In quanto grafo cubico connesso privo di ponti con indice cromatico quattro, il grafo di Petersen è uno snark. È il più piccolo snark possibile, e fu l'unico snark conosciuto dal 1898 fino al 1946. Il teorema degli snark, un risultato congetturato da W. T. Tutte e annunciato nel 2001 da Robertson, Sanders, Seymour e Thomas,^[8] afferma che ogni snark ha il grafo di Petersen come minore.

In aggiunta, il grafo ha indice cromatico frazionario 3, provando che la differenza tra l'indice cromatico e l'indice cromatico frazionario può essere pari a 1. La congettura di Goldberg-Seymour, che resiste da lungo tempo, propone che questo sia il massimo divario possibile.

Il numero di Thue (una variante dell'indice cromatico) del grafo di Petersen è 5.

Altre proprietà

Il grafo di Petersen:

• è 3-connesso e quindi 3-connesso sugli spigoli e privo di ponti. Vedi il glossario.
• ha numero d'indipendenza 4 ed è 3-partito. Vedi il glossario.
• è cubico, ha numero di dominio 3, e ha un abbinamento e un 2-fattore.
• ha 6 distinti abbinamenti perfetti.
• è il più piccolo grafo cubico di calibro 5. (È l'unico ${\displaystyle (3,5)}$-gabbia. In realtà, poiché ha solo 10 vertici, è l'unico ${\displaystyle (3,5)}$-grafo di Moore.)^[9]
• ha raggio 2 e diametro 2. È il più grande grafo cubico con diametro 2.^[10]
• ha spettro dei grafi −2, −2, −2, −2, 1, 1, 1, 1, 1, 3.
• ha 2000 alberi ricoprenti, il numero più alto di qualsiasi grafo cubico con 10 vertici.^[11]
• ha polinomio cromatico ${\displaystyle t(t-1)(t-2)\left(t^{7}-12t^{6}+67t^{5}-230t^{4}+529t^{3}-814t^{2}+775t-352\right).}$^[12]
• ha polinomio caratteristico ${\displaystyle (t-1)^{5}(t+2)^{4}(t-3)}$, che ne fa un grafo integrale—un grafo il cui spettro consiste completamente di numeri interi.

Congettura della colorazione di Petersen

Secondo DeVos, Nesetril e Raspaud, "Un ciclo di un grafo G è un insieme C ${\displaystyle \subseteq }$ E(G) tale che ogni vertice del grafo (V(G),C) ha grado pari. Se G, H sono grafi, definiamo una mappa φ: E(G) → E(H) ciclo-continua se la pre-immagine di ogni ciclo di H è un ciclo di G. Una congettura affascinante di Jaeger asserisce che ogni grafo privo di ponti ha una mappatura ciclo-continua al grafo di Petersen. Jaeger mostrò che se questa congettura è vera, allora lo sono anche la congettura della doppia copertura di 5-ciclo e la congettura di Berge-Fulkerson."^[13]

Grafi correlati

La famiglia di Petersen.

Il grafo di Petersen generalizzato G(n,k) è formato connettendo i vertici di un n-gono regolare ai vertici corrispondenti di un poligono a stella con simbolo di Schläfli {n/k}.^[14] Per esempio, in questa notazione, il grafo di Petersen graph è G(5,2): esso può essere formato connettendo i vertici corrispondenti di un pentagono e di una stella a cinque punte, e gli spigoli della stella connettono ogni secondo vertice. I grafi generalizzati di Petersen includono anche l'n-prisma G(n,1), il grafo di Dürer G(6,2), il grafo di Möbius-Kantor G(8,3), il dodecaedro G(10,2), il grafo di Desargues G(10,3) e il grafo di Nauru G(12,5).

The famiglia di Petersen consiste dei sette grafi che possono essere formati dal grafo di Petersen mediante zero o più applicazioni of trasformazioni Δ-Y o Y-Δ. Anche il grafo completo K₆ è nella famiglia di Petersen. Questi grafi formano i minori proibiti per grafi incorporabili senza collegamenti, grafi che possono essere incorporati nello spazio tridimensionale in modo tale che nessuna coppia di cicli nel grafo sia collegata.^[15]

Il grafo di Clebsch contiene molte copie del grafo di Petersen come sottografi indotti: per ciascun vertice v del grafo di Clebsch, i dieci nin vicini di v inducono una copia del grafo di Petersen.

Note

1. Andries E. Brouwer, The Petersen graph.
2. Donald E. Knuth, The Art of Computer Programming; volume 4, pre-fascicle 0A. A draft of section 7: Introduction to combinatorial searching.
3. László Babai, Automorphism groups, isomorphism, reconstruction (ps), in Ronald L. Graham, Martin Grötschel e László Lovász (a cura di), Handbook of Combinatorics, I, North-Holland, 1995, 1447–1540, Corollary 1.8 (archiviato dall'url originale l'11 giugno 2010)..
4. Secondo il censimento Foster.
5. Come affermato, ciò presume che i grafi di Cayley non abbiano bisogno di essere connessi. Alcune fonti richiedono che i grafi di Cayley siano connessi, rendendo il grafo vuoto con due vertici il più piccolo grafo non di Caley transitivo dei vertici; in base alla definizione data da queste fonti, il grafo di Petersen è il più piccolo grafo connesso transitivo sui vertici diverso da quello di Cayley.
6. Royle, G. "Cubic Symmetric Graphs (The Foster Census)." Archiviato il 20 luglio 2008 in Internet Archive.
7. Holton & Sheehan (1993), p. 32.
8. Ed, Jr. Pegg, Book Review: The Colossal Book of Mathematics (PDF), in Notices of the American Mathematical Society, vol. 49, n. 9, 2002, 1084–1086, DOI:10.1109/TED.2002.1003756.
9. Alan J. Hoffman e Robert R. Singleton, Moore graphs with diameter 2 and 3 (PDF), in IBM Journal of Research and Development, vol. 5, n. 4, 1960, 497–504, DOI:10.1147/rd.45.0497, MR 0140437. URL consultato il 1º maggio 2019 (archiviato dall'url originale il 18 maggio 2008).
10. Questo segue dal fatto che è un grafo di Moore, poiché qualsiasi grafo di Moore è il più grande grafo regolare possibile con il suo grado e diametro (Hoffman & Singleton 1960).
11. Jakobson & Rivin (1999); Valdes (1991). I grafi cubici con 6 e 8 vertici che massimizzano il numero di alberi ricoprenti sono le scale di Möbius.
12. Biggs, Norman, Algebraic Graph Theory, 2ª ed., Cambridge, Cambridge University Press, 1993, ISBN 0-521-45897-8.
13. Matt DeVos, Jaroslav Nešetřil e André Raspaud, On edge-maps whose inverse preserves flows or tensions, in Graph theory in Paris, Trends Math., Basel, Birkhäuser, 2007, 109–138, DOI:10.1007/978-3-7643-7400-6_10, MR 2279171.
14. Coxeter (1950); Watkins (1980).
15. Rosemary A. Bailey, Surveys in Combinatorics, Cambridge University Press, 1997, p. 187, ISBN 978-0-521-59840-8.

Bibliografia

• Geoffrey Exoo, Frank Harary e Jerald Kabell, The crossing numbers of some generalized Petersen graphs, in Mathematica Scandinavica, vol. 48, 1981, 184—188.
• H. S. M. Coxeter, Self-dual configurations and regular graphs, in Bulletin of the American Mathematical Society, vol. 56, n. 5, 1950, 413–455, DOI:10.1090/S0002-9904-1950-09407-5.
• D. A. Holton e J. Sheehan, The Petersen Graph, Cambridge University Press, 1993, DOI:10.2277/0521435943, ISBN 0-521-43594-3. URL consultato il 17 febbraio 2014 (archiviato dall'url originale l'8 febbraio 2008).
• Dmitry Jakobson e Igor Rivin, On some extremal problems in graph theory, 1999, arXiv:math.CO/9907050.
• A. B. Kempe, A memoir on the theory of mathematical form, in Philosophical Transactions of the Royal Society of London, vol. 177, 1886, 1—70, DOI:10.1098/rstl.1886.0002.
• László Lovász, Combinatorial Problems and Exercises, 2ª ed., North-Holland, 1993, ISBN 0-444-81504-X.
• Julius Petersen, Sur le théorème de Tait, in L'Intermédiaire des Mathématiciens, vol. 5, 1898, 225—227.
• A. J. Schwenk, Enumeration of Hamiltonian cycles in certain generalized Petersen graphs, in J. Combin. Theory B, vol. 47, n. 1, 1989, pp. 53—59, DOI:10.1016/0095-8956(89)90064-6.
• L. Valdes, Extremal properties of spanning trees in cubic graphs, in Congressus Numerantium, vol. 85, 1991, pp. 143–160.
• Mark E. Watkins, A Theorem on Tait Colorings with an Application to the Generalized Petersen Graphs, in Journal of Combinatorial Theory, vol. 6, n. 2, 1969, pp. 152—164, DOI:10.1016/S0021-9800(69)80116-X.

Altri progetti

Altri progetti

• Wikimedia Commons

• Wikimedia Commons contiene immagini o altri file su grafo di Petersen

Collegamenti esterni

• Mitch Keller, (EN) Kneser graphs, in PlanetMath.
• (EN) Eric W. Weisstein, Grafo di Petersen, su MathWorld, Wolfram Research.
• (EN) Grafo di Petersen, su Encyclopaedia of Mathematics, Springer e European Mathematical Society.
• (EN) Petersen Graph su On-Line Encyclopedia of Integer Sequences

Portale Matematica: accedi alle voci di Wikipedia che trattano di Matematica