Contele de Petersen | |
---|---|
Numit după | Julius Petersen |
Vârfurile | zece |
coaste | cincisprezece |
Rază | 2 |
Diametru | 2 |
Circumferinţă | 5 |
Automorfisme | 120 ( S5 ) |
Număr cromatic | 3 |
Indicele cromatic | patru |
Gen | unu |
Proprietăți |
Cubic Strongly Regular Distanță- Snark tranzitiv |
Fișiere media la Wikimedia Commons |
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.
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.
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 .
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]
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.
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] .
Contele 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] .
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.