Contele de Petersen

Graficul Petersen  este un grafic nedirecționat cu 10 vârfuri și 15 muchii; un grafic destul de simplu folosit ca exemplu și contraexemplu pentru multe probleme din teoria grafurilor.

Numit după Julius Petersen , care l-a construit în 1898 ca cel mai mic grafic cubic fără punte care nu are o colorare a marginilor în trei culori [1] . În același timp, prima mențiune a unui astfel de graf este remarcată într-un articol din 1886 al lui Kempe [2] , în care se remarcă faptul că vârfurile sale pot fi considerate ca zece linii ale configurației Desargues , iar muchiile sunt perechi de linii. a căror intersecţie nu aparţine configuraţiei.

Donald Knuth notează că graficul este remarcabil pentru că oferă contraexemple pentru multe afirmații „optimiste” despre grafice în general [3] .

Graficul Petersen apare și în geometria tropicală : conul deasupra graficului Petersen este identificat în mod natural prin spațiul modular al curbelor tropicale raționale în cinci puncte.

Clădire

Graficul Petersen este complementul graficului cu linii pentru . Numărul este, de asemenea, un număr Kneser . Aceasta înseamnă că graficul are câte un vârf pentru fiecare submulțime de 2 elemente dintr-o mulțime de 5 elemente și două vârfuri sunt conectate printr-o muchie dacă și numai dacă submulțimile corespunzătoare de 2 elemente nu se intersectează. Ca un grafic Kneser al formei, graficul este un grafic impar .

Din punct de vedere geometric, un grafic Petersen este un grafic format din vârfurile și muchiile unui semidodecaedru , adică un dodecaedru cu vârfuri, muchii și fețe opuse identificate.

Atasamente

Graficul Petersen nu este planar . Orice graf non-plan are fie un graf complet , fie un graf bipartit complet ca minori , dar graficul Petersen are ambele grafice ca minore. Minorul poate fi obținut prin contractarea muchiilor unei potriviri perfecte , de exemplu, cele cinci muchii scurte din prima figură. Un minor poate fi obținut prin ștergerea unui vârf (de exemplu, vârful central al unui model cu 3 simetrice) și contractarea muchiilor incidente cu fiecare vecin al vârfului eliminat.

Desenul planar cel mai simetric acceptat în general al grafului Petersen ca pentagon într-un pentagon are cinci intersecții. Cu toate acestea, acesta nu este cel mai optim model, minimizând numărul de intersecții. Există un alt model (arat în dreapta) cu doar două intersecții. Astfel, graficul Petersen are numărul de intersecție 2. Fiecare muchie din această figură este încrucișată cel mult o dată, deci graficul Petersen este 1-plan . Pe un tor , graficul Petersen poate fi desenat fără margini încrucișate. Astfel, graficul are genul orientabil 1.

De asemenea, graficul Petersen poate fi desenat (cu intersecții) pe plan în așa fel încât toate muchiile să aibă aceeași lungime. Astfel, graficul este un grafic de unitate de distanță .

Cea mai simplă suprafață neorientabilă în care graficul Petersen poate fi încorporat fără intersecții este planul proiectiv . Aceasta este o încorporare care este dată prin construirea graficului Petersen ca un semidodecaedru . O încorporare în planul proiectiv poate fi, de asemenea, formată din desenul pentagonal standard Petersen, plasând o peliculă (o sticlă Klein tăiată) în interiorul stelei pentagonale în centrul desenului și direcționând marginile stelei prin acest film. Modelul rezultat are șase fețe pentagonale. Această construcție formează o hartă obișnuită și arată că graful Petersen are genul 1 neorientabil .

Simetrii

Graficul Petersen este puternic regulat (cu semnătura srg(10,3,0,1)). Graficul este, de asemenea , simetric , ceea ce înseamnă că este tranzitiv la margine și tranzitiv la vârf . Mai strict, graficul este tranzitiv cu 3 arcuri — orice cale direcționată a celor trei căi din graficul Petersen poate fi mapată la orice altă astfel de cale prin simetria graficului [4] . Graficul este unul dintre cele 13 grafice cubice-distanță regulată . [5]

Grupul de automorfism al grafului Petersen este grupul simetric . Acțiunea asupra grafului Petersen decurge din construcția sa ca graf Kneser . Orice homeomorfism al grafului Petersen asupra lui însuși care nu identifică vârfuri adiacente este un automorfism. După cum se arată în ilustrații, desenele graficului Petersen pot prezenta simetrii în cinci direcții sau în trei direcții, dar nu este posibil să desenați un grafic Petersen pe plan în așa fel încât desenul să prezinte simetria completă a grupului de grafice.

În ciuda simetriei sale ridicate, graful Petersen nu este un graf Cayley , este cel mai mic graf tranzitiv de vârf care nu este un graf Cayley. [6]

Căi și cicluri hamiltoniene

Graficul Petersen are o cale hamiltoniană, dar nu un ciclu hamiltonian . Un grafic este cel mai mic grafic cubic fără punte care nu are un ciclu Hamiltonian. Graficul este hipo -hamiltonian, ceea ce înseamnă că, deși nu are un ciclu hamiltonian, eliminarea oricărui vârf îl face hamiltonian și este cel mai mic graf hipo-hamiltonian.

Fiind un graf tranzitiv-vertix conex finit, fără ciclu hamiltonian, graful Petersen este un contraexemplu al unei variante a conjecturii Lovas , dar formularea canonică a conjecturii cere o cale hamiltoniană, iar pentru graful Petersen această presupunere este valabilă.

Sunt cunoscute doar cinci grafice tranzitive vârfuri conectate fără cicluri hamiltoniene - graficul K 2 complet , graficul Petersen , graficul Coxeter și două grafice obținute din graficele Petersen și Coxeter prin înlocuirea fiecărui vârf cu un triunghi [7] . Dacă G este un graf r - regulat cu 2 conexiuni cu cel mult 3r  + 1 vârfuri, atunci G este hamiltonian sau G este un graf Petersen [8] .

Pentru a arăta că graficul Petersen nu are un ciclu hamiltonian C , luăm în considerare muchiile care conectează ciclul interior cu 5 vârfuri de ciclul exterior. Dacă există un ciclu hamiltonian, trebuie ales un număr par din aceste muchii. Dacă sunt selectate doar două muchii, vârfurile lor de capăt trebuie să fie adiacente în ambele cicluri de 5 vârfuri, ceea ce nu este posibil. Astfel, trebuie selectate 4 muchii. Să presupunem că marginea superioară nu este selectată (toate celelalte cazuri sunt similare din cauza simetriei). Dintre cele 5 muchii ale ciclului exterior, cele două muchii de sus trebuie incluse în ciclul hamiltonian, astfel încât cele două margini laterale nu ar trebui să fie incluse în ciclu, iar apoi marginea de jos trebuie să fie inclusă în ciclu. Cele două muchii de sus din ciclul interior trebuie alese, dar apoi acele două muchii închid un ciclu care nu este complet, deci nu poate face parte dintr-un ciclu hamiltonian. Alternativ, putem lua în considerare grafice regulate cu zece vârfuri 3 care au un ciclu hamiltonian și să arătăm că niciunul dintre aceste grafice nu este un grafic Petersen, găsind în fiecare dintre ele un ciclu mai scurt decât orice ciclu al graficului Petersen. Orice grafic hamiltonian cu 3 obișnuiți cu zece vârfuri constă dintr-un ciclu C cu zece vârfuri , plus cinci acorduri. Dacă orice coardă conectează două vârfuri de-a lungul C la o distanță de două sau trei unul de celălalt, atunci graficul are un ciclu de 3 sau un ciclu de 4 și, prin urmare, nu poate fi un grafic Petersen. Dacă două coarde conectează vârfuri opuse ale unui ciclu C la o distanță de patru de-a lungul C , există din nou un ciclu de 4. Rămâne doar cazul scării Möbius , format prin unirea fiecărei perechi de laturi opuse printr-o coardă, care are din nou un ciclu de 4. Deoarece circumferința grafului Petersen este de cinci, acesta nu poate fi format în acest fel și, prin urmare, nu are un ciclu hamiltonian.

Plansa de colorat

Graficul Petersen are numărul cromatic 3, ceea ce înseamnă că vârfurile graficului pot fi colorate cu trei culori, dar nu cu două, astfel încât nicio margine să conecteze două vârfuri de aceeași culoare. Graficul are o colorare prescrisă de 3 culori conform teoremei lui Brooks pentru colorații prescrise. Graficul Petersen are indicele cromatic 4, ceea ce înseamnă că colorarea marginilor necesită patru culori. Cu alte cuvinte, graficul nu este suma a trei 1-factori , care a fost arătat de Petersen însuși [9] . Pentru a demonstra acest lucru, patru cazuri trebuie verificate pentru a arăta că nu există 3-colorări ale marginilor. Ca un grafic cubic conectat fără punte cu indice cromatic patru, graficul Petersen este un snark . Acest grafic este cel mai mic snark posibil. A fost singurul snark cunoscut în perioada 1898-1946. Teorema snark , enunțată sub forma conjecturii Tutt (demonstrată în 2001 de Robertson, Sanders, Seymour și Thomas [10] ), afirmă că orice snark are un graf Petersen ca minor .

În plus, graficul are un indice cromatic fracționar de 3, ceea ce susține afirmația că diferența dintre indicele cromatic și indicele cromatic fracționar poate fi 1. Conjectura Goldberg-Seymour de lungă durată sugerează că aceasta este cea mai mare diferență posibilă.

Numărul Thue (o variantă a indexului cromatic) al graficului Petersen este 5.

Graficul Petersen necesită cel puțin trei culori în orice colorare (posibil necorespunzătoare) care rupe toate simetriile. Adică, numărul caracteristic de colorare al graficului este egal cu trei. Cu excepția graficelor complete, există doar un grafic Kneser al cărui număr caracteristic nu este egal cu doi [11] .

Alte proprietăți

Contele Petersen:

• este 3-conectat și, prin urmare, 3-margini conectat și fără punte. Vezi graficul conectat .
• are un număr de independență de 4 și este tripartit. Consultați Problema setului independent .
• este un grafic cubic , are un număr de dominanță de 3, are o potrivire perfectă și un factor 2 .
• are 6 potriviri perfecte distincte.
• este cel mai mic grafic cubic cu circumferința 5. (Este singurul - o celulă . Graficul are doar 10 vârfuri, deci este singurul - un grafic Moore .) [12] .
• are raza 2 și diametrul 2. Acesta este cel mai mare grafic cubic cu diametrul 2 [13]
• are spectrul graficului −2, −2, −2, −2, 1, 1, 1, 1, 1, 3.
• are 2000 de arbori care se întind , mai mult decât orice grafic cubic cu 10 vârfuri [14]
• are un polinom cromatic [15]
• are un polinom caracteristic , ceea ce îl face un graf întreg  — un graf al cărui spectru este format în întregime din numere întregi.
• Între oricare două vârfuri există o cale unică de lungime de cel mult două.

Conjectura de colorare a lui Petersen

Potrivit lui Devos, Nexetril și Raspo, „ Ciclul unui grafic G este o mulțime C E(G) astfel încât orice vârf al graficului (V(G),C) are un grad par. Dacă G, H sunt grafice, definim o mapare φ: E(G) -> E(H) ca ciclu-continuă dacă imaginea prealabilă a oricărui ciclu din H este un ciclu în G. François Jaeger a formulat o presupunere care afirmă că orice grafic fără punte are o hartă ciclu-continuă la graficul Petersen. Jaguer a arătat că, dacă conjectura este adevărată, atunci sunt adevărate și conjectura de acoperire dublă cu cicluri de lungime 5 și conjectura Berge-Fulkerson. [16] .

Grafice înrudite

Graficul Petersen generalizat G ( n , k ) se formează prin conectarea vârfurilor unui n - gon regulat cu vârfurile corespunzătoare ale unui poligon stea cu simbolul Schläfli { n / k } [17] [18] . De exemplu, în aceste notații, graficul Petersen este notat cu G (5,2) - poate fi format prin conectarea vârfurilor corespunzătoare ale unui pentagon și unei stele pentagonale, în timp ce vârfurile stelei sunt conectate printr-un singur. Graficele Petersen generalizate includ, de asemenea, n -prisme G ( n ,1), graficul Dürer G (6,2), graficul Möbius-Cantor G (8,3), graficul dodecaedru G (10,2), graficul Desargues G (10, 3) și Contele Nauru G (12,5).

Familia de grafice Petersen este formată din șapte grafice care pot fi formate dintr-un grafic Petersen prin aplicarea zero sau mai multe transformări Δ-Y sau Y-Δ . Graficul complet K 6 aparține și familiei Petersen. Aceste grafice formează minore interzise pentru graficele încorporabile fără linkuri , grafice care pot fi încorporate în spațiul tridimensional astfel încât să nu fie legate două cicluri din grafic [19]

Graficul Clebsch constă din copii ale graficului Petersen ca subgrafe generate  — pentru fiecare vârf v al graficului Clebsch, zece vârfuri non-vecinate v generează o copie a graficului Petersen.

Note

1. ↑ Graficul Petersen .
2. ↑ Kempe, 1886 .
3. ↑ Knuth, 2011 .
4. ↑ Babai, 1995 , p. 1447–1540.
5. ↑ Conform listei Foster .
6. ↑ După cum sa menționat, aceasta presupune că graficele Cayley nu sunt neapărat conectate. Unele surse necesită conectarea graficelor Cayley, făcând din graficul gol cu ​​două vârfuri cel mai mic grafic tranzitiv de vârf care nu este un grafic Cayley. Prin definiția dată în aceste surse, un graf Petersen este cel mai mic graf tranzitiv-vertex conectat care nu este un graf Cayley.
7. ↑ Royle, G. „Cubic Symmetric Graphs (The Foster Census).” Arhivat din original pe 20 iulie 2008.
8. ↑ Holton, Sheehan, 1993 , p. 32.
9. ↑ Harari, 2003 , p. 113.
10. ↑ Pegg, 2002 , p. 1084–1086.
11. ↑ Albertson, Boutin, 2007 , p. R20.
12. ↑ Hoffman, Singleton, 1960 , p. 497–504.
13. ↑ Aceasta rezultă din faptul că graficul este un grafic Moore, deoarece graficul Moore este cel mai mare grafic regulat posibil cu acel grad de vârfuri și diametru ( Hoffman, Singleton 1960 ).
14. ↑ Jakobson, Rivin, 1999 ; Valdes, 1991 . Graficele cubice cu 6 și 8 vârfuri pe care este maximizat numărul de arbori de întindere sunt scări Möbius .
15. ↑ Biggs, 1993 .
16. ↑ DeVos, Nešetřil, Raspaud, 2007 , p. 109–138.
17. ↑ Coxeter, 1950 .
18. ↑ Watkins, 1969 .
19. ↑ Bailey, 1997 , p. 187.

Literatură

• F. Harari. Teoria grafurilor. - M .: URSS , 2003. - ISBN 5-354-00301-6 .
• O. Minereu . Teoria grafurilor. — M .: URSS , 2008. — ISBN 978-5-397-00044-4 .
• Ed Pegg, Jr. Recenzie de carte: The Colossal Book of Mathematics  //  Notices of the American Mathematical Society. - 2002. - Vol. 49 , iss. 9 . - doi : 10.1109/TED.2002.1003756 . - Cod biblic .
• Rosemary A. Bailey. Sondaje în combinatorică. - Cambridge University Press, 1997. - ISBN 978-0-521-59840-8 .
• Matt DeVos, Jaroslav Nešetřil, André Raspaud. Pe hărți de margine a căror inversă păstrează curgeri sau tensiuni // Teoria grafurilor la Paris. - Basel: Birkhäuser, 2007. - P. 109-138. - (Trends Math.). - doi : 10.1007/978-3-7643-7400-6_10 .
• Norman Biggs. Teoria algebrică a graficelor. — al 2-lea. - Cambridge: Cambridge University Press, 1993. - ISBN 0-521-45897-8 .
• Laszlo Babai. Grupuri de automorfism, izomorfism, reconstrucție // Handbook of Combinatorics / Ronald L. Graham, Martin Grötschel, László Lovász. - North-Holland, 1995. - T. I. Arhivat 11 iunie 2010 la Wayback Machine
• Alan J. Hoffman, Robert R. Singleton. Grafice Moore cu diametrul 2 și 3  // IBM Journal of Research and Development. - 1960. - V. 5 , nr. 4 . - S. 497-504 . - doi : 10.1147/rd.45.0497 .
• Michael O. Albertson, Debra L. Boutin. Utilizarea seturilor determinante pentru a distinge graficele Kneser  // Electronic Journal of Combinatorics. - 2007. - T. 14 , nr. 1 .
• Geoffrey Exoo, Frank Harary, Frank Harary. Numerele de încrucișare ale unor grafice Petersen generalizate // Mathematica Scandinavica. - 1981. - T. 48 . - S. 184-188 .
• HSM Coxeter. Configurații auto-duale și grafice regulate  // Buletinul Societății Americane de Matematică  . - 1950. - Vol. 56 , iss. 5 . - P. 413-455 . - doi : 10.1090/S0002-9904-1950-09407-5 .
• D. A. Holton, J. Sheehan. Graficul Petersen . - Cambridge University Press , 1993. - ISBN 0-521-43594-3 . - doi : 10.2277/0521435943 . Arhivat pe 8 februarie 2008 la Wayback Machine
• Dmitry Jakobson, Igor Rivin. Despre unele probleme extreme din teoria grafurilor. - 1999. - arXiv : math.CO/9907050 .
• AB Kempe. Un memoriu despre teoria formei matematice // Philosophical Transactions of the Royal Society of London. - 1886. - T. 177 . - S. 1-70 . - doi : 10.1098/rstl.1886.0002 .
• Laszlo Lovasz . Probleme și exerciții combinatorii. — al 2-lea. - Olanda de Nord, 1993. - ISBN 0-444-81504-X .
• Julius Peterson. Sur le théorème de Tait // L'Intermédiaire des Mathematiciens. - 1898. - T. 5 . - S. 225-227 .
• AJ Schwenk. Enumerarea ciclurilor hamiltoniene în anumite grafice Petersen generalizate // Journal of Combinatorial Theory . - 1989. - T. 47 , nr. 1 . - S. 53-59 . - doi : 10.1016/0095-8956(89)90064-6 .
• L. Valdes. Proprietăți extreme ale copacilor de întindere în grafice cubice // Congressus Numerantium. - 1991. - T. 85 . - S. 143-160 .
• Mark E. Watkins. O teoremă asupra colorărilor Tait cu o aplicație la graficele Petersen generalizate // Journal of Combinatorial Theory . - 1969. - T. 6 , nr. 2 . - S. 152-164 . - doi : 10.1016/S0021-9800(69)80116-X .
• Donald E. Knuth . O schiță a secțiunii 7: Introducere în căutarea combinatorie // Arta programarii pe computer . - V. 4, prefasciclul 0A.
  • Donald E. Knuth . Algoritmi combinatori, partea 1. - Upper Saddle River, New Jersey: Addison-Wesley, 2011. - ISBN 0-201-03804-8 .
  • Donald E. Knuth . Capitolul 7: Căutare combinatorie // Arta programarii. — Moscova, Sankt Petersburg, Kiev: I.D. Williams, 2013. - V. 4, A / Combinatorial Algorithms, Part 1. - ISBN 978-5-8459-1744-7 BBC 32.973.26-18.2.75.

Link -uri

• Keller, Mitch. Grafice Kneser Arhivat 5 mai 2018 la Wayback Machine PlanetMath
• Weisstein, Eric W. Petersen Graph  (engleză) pe site-ul web Wolfram MathWorld .
• Petersen Graph la Encyclopedia of Integer Sequences