Graficul Petersen

Graficul Petersen este desenat cel mai frecvent ca un pentagon cu o pentagramă în interior, cu cinci raze.

În câmpul matematic al teoriei graficelor , graficul Petersen este un grafic nedirecționat cu 10 vârfuri și 15 muchii . Este un mic grafic care servește ca un exemplu util și contraexemplu pentru multe probleme de teorie a graficelor. Graficul Petersen este numit după Julius Petersen , care, în 1898, l-a construit pentru a fi cel mai mic grafic cub cu punte, fără colorare pe trei margini. ^[1]

Deși graficul este în general atribuit lui Petersen, el a apărut de fapt cu 12 ani mai devreme, într-un eseu de AB Kempe (1886) . Kempe a observat că vârfurile sale pot reprezenta cele zece linii ale configurației Desargues și că marginile sale reprezintă perechi de linii care nu se întâlnesc la unul dintre cele zece puncte ale configurației.

Donald Knuth afirmă că graficul Petersen este „o configurație remarcabilă care servește drept contraexemplu la multe previziuni optimiste despre ceea ce ar putea fi adevărat pentru graficele în general”. ^[2]

Clădiri

Graficul Petersen ca grafic Kneser

KG_{5,2}

{\ displaystyle KG_ {5,2}}

{\ displaystyle KG_ {5,2}}

.

Graficul Petersen este complementul graficului liniar al $K_{5}$ ${\ displaystyle K_ {5}}$ ${\ displaystyle K_ {5}}$ . Este, de asemenea, graficul Kneser $KG_{5,2}$ ${\ displaystyle KG_ {5,2}}$ ${\ displaystyle KG_ {5,2}}$ ; aceasta înseamnă că are un singur vârf pentru fiecare subset de 2 elemente dintr-un set de 5 elemente, iar două vârfuri sunt conectate printr-o margine dacă și numai dacă subseturile corespunzătoare de 2 elemente sunt disjuncte între ele. Ca grafic Kneser al formei $KG_{2n-1,n-1}$ ${\ displaystyle KG_ {2n-1, n-1}}$ ${\ displaystyle KG_ {2n-1, n-1}}$ este un exemplu de grafic impar .

Geometric, graficul Petersen este graficul format din vârfurile și marginile hemidodecaedrului , adică un dodecaedru cu puncte, linii și fețe opuse identificate împreună.

Încorporări

Graficul Petersen nu este plan . Orice grafic non-plan are ca grafic minor sau complet $K_{5}$ ${\ displaystyle K_ {5}}$ ${\ displaystyle K_ {5}}$ , sau graficul bipartit complet $K_{3,3}$ ${\ displaystyle K_ {3,3}}$ ${\ displaystyle K_ {3,3}}$ , dar graficul Petersen are ambele ca minori. Minorul $K_{5}$ ${\ displaystyle K_ {5}}$ ${\ displaystyle K_ {5}}$ se poate forma prin contractarea marginilor unei potriviri perfecte, de exemplu pentru cele cinci margini scurte ale primei figuri. Minorul $K_{3,3}$ ${\ displaystyle K_ {3,3}}$ ${\ displaystyle K_ {3,3}}$ se poate forma prin ștergerea unui vârf (de exemplu vârful central al desenului 3-simetric) și prin contractarea unei margini incidente la fiecare vecin al vârfului șters.

Graficul Petersen are numărul de treceri 2.

Cel mai comun și simetric design plan al graficului Petersen, cum ar fi o pentagramă într-un pentagon, are cinci încrucișări. Cu toate acestea, acesta nu este cel mai bun design pentru minimizarea traversărilor; există un alt design (prezentat în figură) cu doar două intersecții. Astfel, graficul Petersen are numărul de traversări 2. Pe un tor , graficul Petersen poate fi desenat fără intersecțiile marginilor; prin urmare are gen orientabil 1.

Graficul Petersen este un grafic al distanței unitare : poate fi desenat în plan cu fiecare margine având lungimea unității

Graficul Petersen poate fi, de asemenea, desenat (cu încrucișări) în plan, astfel încât toate muchiile să aibă lungime egală. Adică este un grafic al distanței unitare .

Cea mai simplă suprafață neorientabilă pe care graficul Petersen poate fi încorporat fără încrucișare este planul proiectiv . Aceasta este încorporarea dată de construcția hemidodecaedrului graficului Petersen. Incorporarea planului proiectiv poate fi, de asemenea, formată din designul pentagonal normal al graficului Petersen prin plasarea unui capac transversal în interiorul stelei cu cinci colțuri în centrul designului și direcționarea marginilor stelei prin acest capac transversal. ; designul rezultat are șase fețe pentagonale. Această construcție formează o hartă regulată și arată că graficul Petersen are un gen 1 neorientabil .

Simetriile

Graficul Petersen este puternic regulat (cu semnătura srg (10,3,0,1)). De asemenea, este simetric , ceea ce înseamnă că este tranzitiv pe margini și tranzitiv pe vârfuri . Mai clar, este 3-tranzitiv pe margini: orice cale orientată cu trei margini în graficul Petersen poate fi transformată în orice altă cale de acest tip prin intermediul unei simetrii a graficului. ^[3] Este unul dintre cele 13 grafice cubice cu distanțe regulate . ^[4]

Grupul de automorfism al graficului Petersen este grupul simetric $S_{5}$ ${\ displaystyle S_ {5}}$ $S_ {5}$ ; acțiunea de $S_{5}$ ${\ displaystyle S_ {5}}$ $S_ {5}$ pe graficul Petersen rezultă din construcția sa ca grafic Kneser . Orice omomorfism al graficului Petersen pe sine care nu identifică vârfurile adiacente este un automorfism. Așa cum se arată în figuri, desenele grafice Petersen pot prezenta simetrie în cinci sau trei căi, dar nu este posibil să desenăm graficul Petersen în plan astfel încât desenul să prezinte întregul grup de simetrie al graficului.

În ciuda gradului său ridicat de simetrie, graficul Petersen nu este un grafic Cayley . Este cel mai mic grafic tranzitiv de pe vârfuri care nu este un grafic Cayley. ^[5]

Căi și cicluri hamiltoniene

Graficul Petersen este hipohamiltonian: prin ștergerea oricărui vârf, cum ar fi vârful central din desen, graficul rămas este hamiltonian. Acest desen cu simetrie de ordinul 3 este cel dat de Kempel1886 , Kempel (1886) .

Graficul Petersen are o cale hamiltoniană, dar nu are un ciclu hamiltonian . Este cel mai mic grafic cub fără punte fără cicluri hamiltoniene. Este hipohamiltonian , ceea ce înseamnă că, deși nu are cicluri hamiltoniene, ștergerea oricărui vârf îl face hamiltonian și, în acest context, este cel mai mic grafic hipohamiltonian.

Ca grafic tranzitiv finit conectat pe vârfuri care nu au un ciclu hamiltonian, graficul Petersen este un contraexemplu al unei variante a conjecturii Lovász , dar formularea canonică a conjecturii necesită o cale Hamiltoniană și este verificată de graficul Petersen.

Se cunosc doar cinci grafice conectate tranzitive pe vârfuri fără cicluri hamiltoniene: graficul complet K ₂ , graficul Petersen, graficul Coxeter și două grafice derivate din graficele Petersen și Coxeter prin înlocuirea fiecărui vârf cu un triunghi. ^[6] Dacă G este un grafic r- regulat cu 2 conexiuni cu cel mult 3 vârfuri r + 1, atunci fie G este hamiltonian, fie este graficul Petersen. ^[7]

Pentru a vedea că graficul Petersen nu are un ciclu hamiltonian C , vom descrie graficele cu 3 reguli cu zece vârfuri care au de fapt un ciclu hamiltonian și arătăm că niciunul dintre ele nu este graficul Petersen, găsind în fiecare dintre ele un ciclu care este mai scurt decât orice ciclu din graficul Petersen. Orice grafic hamiltonian cu 3 vârfuri cu zece vârfuri constă dintr-un ciclu de zece vârf plus cinci coarde C. Dacă orice coardă conectează două vârfuri la o distanță de două sau trei unul de celălalt de-a lungul lui C , graficul are un ciclu de 3 sau 4 cicluri și, prin urmare, nu poate fi un grafic Petersen. Dacă două coarde conectează două vârfuri opuse ale lui C la vârfuri la o distanță de patru de-a lungul lui C , există din nou o 4-buclă. Singurul caz rămas este o scară Mobius formată prin conectarea fiecărei perechi de vârfuri opuse printr-o coardă, care are încă 4 bucle. Deoarece graficul Petersen are calibru cinci, acesta nu poate fi format în acest fel și nu are un ciclu hamiltonian.

Colorare

O 4-colorare a marginilor grafului Petersen.

O 3-colorare a vârfurilor grafului Petersen.

Graficul Petersen are numărul cromatic 3, ceea ce înseamnă că vârfurile sale pot fi colorate cu trei culori - dar nu cu două - astfel încât nici o margine să nu conecteze vârfurile de aceeași culoare.

Graficul Petersen are indicele cromatic 4; colorarea marginilor necesită patru culori. O dovadă a acestui lucru necesită verificarea a patru cazuri pentru a demonstra că nu există o culoare cu 3 margini. Ca un grafic cub conectat fără punte cu index cromatic patru, graficul Petersen este un snark . Este cel mai mic snark posibil și a fost singurul snark cunoscut din 1898 până în 1946. Teorema snark , rezultat conjecturat de WT Tutti și anunțat în 2001 de Robertson, Sanders, Seymour și Thomas, ^[8] afirmă că fiecare snark are Graficul Petersen ca minor .

În plus, graficul are indicele cromatic fracțional 3, demonstrând că diferența dintre indicele cromatic și indicele cromatic fracționat poate fi egală cu 1. Conjectura de lungă durată Goldberg-Seymour propune că acesta este decalajul maxim posibil.

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

Alte proprietăți

Graficul Petersen:

este 3-conectat și deci 3-conectat pe margini și fără punți. Vezi glosarul .
are independența numărul 4 și este formată din 3 partide. Vezi glosarul .
este cubic , are numărul de domeniu 3 și are o potrivire și un factor 2 .
are 6 potriviri perfecte distincte.
este cel mai mic grafic cub cu calibru 5. (Este singurul $(3,5)$ ${\ displaystyle (3,5)}$ $(3,5)$ - cușcă . De fapt, deoarece are doar 10 vârfuri, este singurul $(3,5)$ ${\ displaystyle (3,5)}$ $(3,5)$ - Graficul lui Moore .) ^[9]
are raza 2 și diametrul 2. Este cel mai mare grafic cub cu diametrul 2. ^[10]
are spectrul graficelor −2, −2, −2, −2, 1, 1, 1, 1, 1, 3.
are 2000 de copaci întinși , cel mai mare număr din orice grafic cub cu 10 vârfuri. ^[11]
are polinom cromatic $t(t-1)(t-2)\left(t^{7}-12t^{6}+67t^{5}-230t^{4}+529t^{3}-814t^{2}+775t-352\right).$ ${\ displaystyle t (t-1) (t-2) \ left (t ^ {7} -12t ^ {6} + 67t ^ {5} -230t ^ {4} + 529t ^ {3} -814t ^ { 2} + 775t-352 \ dreapta).}$ ${\ displaystyle t (t-1) (t-2) \ left (t ^ {7} -12t ^ {6} + 67t ^ {5} -230t ^ {4} + 529t ^ {3} -814t ^ { 2} + 775t-352 \ dreapta).}$ ^[12]
are un polinom caracteristic $(t-1)^{5}(t+2)^{4}(t-3)$ ${\ displaystyle (t-1) ^ {5} (t + 2) ^ {4} (t-3)}$ ${\ displaystyle (t-1) ^ {5} (t + 2) ^ {4} (t-3)}$ , ceea ce îl face un grafic integral - un grafic al cărui spectru constă în întregime din numere întregi.

Conjectura colorării Petersen

Potrivit lui DeVos, Nesetril și Raspaud, „Un ciclu al unui grafic G este un set C $\subseteq$ ${\ displaystyle \ subseteq}$ $\ subseteq$ E ( G ) astfel încât fiecare vârf al graficului (V (G), C) să aibă un nivel egal. Dacă G , H sunt grafice, definim o hartă φ : E ( G ) → E ( H ) ciclu continuu dacă preimaginea fiecărui ciclu H este un ciclu G. O conjectură fascinantă a lui Jaeger afirmă că fiecare grafic fără punte are o cartografiere continuă la graficul Petersen. Jaeger a arătat că, dacă această conjectură este adevărată, atunci la fel sunt și conjectura cu capac dublu de 5 cicluri și conjectura Berge-Fulkerson. " ^[13]

Grafice conexe

Familia Petersen.

Graficul Petersen generalizat G ( n , k ) este format prin conectarea vârfurilor unei n -gene regulate la vârfurile corespunzătoare ale unui poligon stelar cu simbolul Schläfli { n / k }. ^[14] De exemplu, în această notație, graficul Petersen este G (5,2): poate fi format prin conectarea vârfurilor corespunzătoare unui pentagon și a unei stele cu cinci colțuri, iar marginile stelei se conectează la fiecare al doilea vârf. . Graficele Petersen generalizate includ, de asemenea, n- prisma G ( n , 1), graficul Dürer G (6,2), graficul Möbius-Kantor G (8,3), dodecaedrul G (10,2), Desargues graficul G (10.3) și graficul Nauru G (12.5).

Familia Petersen este formată din cele șapte grafice care pot fi formate din graficul Petersen prin zero sau mai multe aplicații ale transformărilor Δ-Y sau Y-Δ . Graficul complet K ₆ este, de asemenea, în familia Petersen. Aceste grafice formează minori interzise pentru non - grafice încorporabile se pot conecta , grafice care pot fi integrate în spațiul tridimensional în așa fel încât nici o pereche de bucle în grafic sunt legate . ^[15]

Graficul Clebsch conține multe copii ale graficului Petersen ca subgrafe induse : pentru fiecare vârf v al graficului Clebsch, cei zece vecini ai lui v induc o copie a graficului Petersen.

Notă

^ Andries E. Brouwer , Graficul Petersen .
^ Donald E. Knuth, The Art of Computer Programming ; volumul 4, pre-fascicul 0A. O schiță a secțiunii 7: Introducere în căutarea combinatorie .
^ László Babai , Automorphism groups , isomorphism, reconstruction ( ps ), în Ronald L. Graham , Martin Grötschel și László Lovász (eds), Handbook of Combinatorics , I, North-Holland, 1995, 1447-1540, Corolar 1.8 (arhivat din adresa URL originală la 11 iunie 2010) . .
^ Conform Recensământului Foster .
^ După cum sa menționat, acest lucru presupune că graficele Cayley nu trebuie conectate. Unele surse necesită conectarea graficelor Cayley, făcând graficul gol cu două vârfuri cel mai mic grafic non-Caley tranzitiv al vârfurilor; conform definiției date de aceste surse, graficul Petersen este cel mai mic grafic tranzitiv conectat pe vârfuri, altele decât graficul Cayley.
^ Royle, G. "Cubic Symmetric Graphs (The Foster Census)" (Grafice simetrice cubice (recensământul adoptiv)). Arhivat la 20 iulie 2008 la Internet Archive .
^ Holton și Sheehan (1993) , p. 32 .
^ Ed, Jr. Pegg , Recenzie de carte: The Colossal Book of Mathematics ( PDF ), în Notices of the American Mathematical Society , vol. 49, nr. 9, 2002, 1084-1086, DOI : 10.1109 / TED.2002.1003756 .
^ Alan J. Hoffman și Robert R. Singleton, grafice Moore cu diametrul 2 și 3 ( PDF ), în IBM Journal of Research and Development , vol. 5, nr. 4, 1960, 497-504, DOI : 10.1147 / rd . 45.0497 , MR 0140437 . Adus la 1 mai 2019 (arhivat din original la 18 mai 2008) .
^ Acest lucru rezultă din faptul că este un grafic Moore, deoarece orice grafic Moore este cel mai mare grafic regulat posibil cu gradul și diametrul său ( Hoffman & Singleton 1960 ).
^ Jakobson & Rivin (1999) ; Valdes (1991) . Graficele cubice cu 6 și 8 vârfuri care maximizează numărul de copaci care se întind sunt scalele Mobius .
^ Biggs, Norman, Algebraic Graph Theory , ediția a II-a, Cambridge, Cambridge University Press, 1993, ISBN 0-521-45897-8 .
^ Matt DeVos, Jaroslav Nešetřil și André Raspaud, On edge-maps al căror invers păstrează fluxurile sau tensiunile , în Teoria graficelor la Paris , Trends Math., Basel, Birkhäuser, 2007, 109–138, DOI : 10.1007 / 978-3-7643 -7400-6_10 , MR 2279171 .
^ Coxeter (1950) ; Watkins (1980) .
^ Rosemary A. Bailey, Surveys in Combinatorics , Cambridge University Press, 1997, p. 187, ISBN 978-0-521-59840-8 .

Bibliografie

Geoffrey Exoo, Frank Harary și Jerald Kabell , Numerele de trecere ale unor grafice Petersen generalizate , în Mathematica Scandinavica , vol. 48, 1981, 184—188.
HSM Coxeter , configurații auto-duale și grafice regulate , în Buletinul Societății Americane de Matematică , vol. 56, nr. 5, 1950, 413–455, DOI :10.1090 / S0002-9904-1950-09407-5 .
DA Holton și J. Sheehan, The Petersen Graph , Cambridge University Press , 1993, DOI : 10.2277 / 0521435943 , ISBN 0-521-43594-3 . Adus la 17 februarie 2014 (arhivat din original la 8 februarie 2008) .
Dmitry Jakobson și Igor Rivin, Despre unele probleme extremale în teoria graficelor , 1999, arXiv : math.CO/9907050 .
AB Kempe, O memorie despre teoria formei matematice , în Philosophical Transactions of the Royal Society of London , vol. 177, 1886, 1-70, DOI : 10.1098 / rstl.1886.0002 .
László Lovász , Probleme și exerciții combinatorii , ediția a II-a, Olanda de Nord, 1993, ISBN 0-444-81504-X .
Julius Petersen, Sur le théorème de Tait , în L'Intermédiaire des Mathématiciens , vol. 5, 1898, 225—227.
AJ Schwenk, Enumerarea ciclurilor hamiltoniene în anumite grafuri Petersen generalizate , în J. Combin. Teoria B , vol. 47, nr. 1, 1989, pp. 53-59, DOI : 10.1016 / 0095-8956 (89) 90064-6 .
L. Valdes, Proprietăți extreme ale copacilor care se întind în grafice cubice , în Congressus Numerantium , vol. 85, 1991, pp. 143-160.
Mark E. Watkins, A Theorem on Tait Colorings with an Application to the Generalized Petersen Graphs , în Journal of Combinatorial Theory , vol. 6, nr. 2, 1969, pp. 152—164, DOI : 10.1016 / S0021-9800 (69) 80116-X .

Alte proiecte

Wikimedia Commons conține imagini sau alte fișiere pe un grafic Petersen

linkuri externe

Mitch Keller, (EN) grafice Kneser , în PlanetMath .
(EN) Eric W. Weisstein, Petersen Graph în MathWorld Wolfram Research.
(EN) Petersen Graph of On-Line Encyclopedia of Integer Sequences

Portalul de matematică : accesați intrările Wikipedia care se ocupă cu matematica

[1] Andries E. Brouwer , Graficul Petersen .

[2] Donald E. Knuth, The Art of Computer Programming ; volumul 4, pre-fascicul 0A. O schiță a secțiunii 7: Introducere în căutarea combinatorie .

[3] László Babai , Automorphism groups , isomorphism, reconstruction ( ps ), în Ronald L. Graham , Martin Grötschel și László Lovász (eds), Handbook of Combinatorics , I, North-Holland, 1995, 1447-1540, Corolar 1.8 (arhivat din adresa URL originală la 11 iunie 2010) . .

[4] Conform Recensământului Foster .

[5] După cum sa menționat, acest lucru presupune că graficele Cayley nu trebuie conectate. Unele surse necesită conectarea graficelor Cayley, făcând graficul gol cu două vârfuri cel mai mic grafic non-Caley tranzitiv al vârfurilor; conform definiției date de aceste surse, graficul Petersen este cel mai mic grafic tranzitiv conectat pe vârfuri, altele decât graficul Cayley.

[6] Royle, G. "Cubic Symmetric Graphs (The Foster Census)" (Grafice simetrice cubice (recensământul adoptiv)). Arhivat la 20 iulie 2008 la Internet Archive .

[7] Holton și Sheehan (1993) , p. 32 .

[8] Ed, Jr. Pegg , Recenzie de carte: The Colossal Book of Mathematics ( PDF ), în Notices of the American Mathematical Society , vol. 49, nr. 9, 2002, 1084-1086, DOI : 10.1109 / TED.2002.1003756 .

[hs60-9] Alan J. Hoffman și Robert R. Singleton, grafice Moore cu diametrul 2 și 3 ( PDF ), în IBM Journal of Research and Development , vol. 5, nr. 4, 1960, 497-504, DOI : 10.1147 / rd . 45.0497 , MR 0140437 . Adus la 1 mai 2019 (arhivat din original la 18 mai 2008) .

[10] Acest lucru rezultă din faptul că este un grafic Moore, deoarece orice grafic Moore este cel mai mare grafic regulat posibil cu gradul și diametrul său ( Hoffman & Singleton 1960 ).

[11] Jakobson & Rivin (1999) ; Valdes (1991) . Graficele cubice cu 6 și 8 vârfuri care maximizează numărul de copaci care se întind sunt scalele Mobius .

[biggs-12] Biggs, Norman, Algebraic Graph Theory , ediția a II-a, Cambridge, Cambridge University Press, 1993, ISBN 0-521-45897-8 .

[13] Matt DeVos, Jaroslav Nešetřil și André Raspaud, On edge-maps al căror invers păstrează fluxurile sau tensiunile , în Teoria graficelor la 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) .

[Bailey1997-15] Rosemary A. Bailey, Surveys in Combinatorics , Cambridge University Press, 1997, p. 187, ISBN 978-0-521-59840-8 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]