Wykres Petersena - Petersen graph

Wykres Petersena
Wykres Petersena jest najczęściej rysowany jako pięciokąt z pentagramem w środku i pięcioma szprychami.
Nazwany po	Juliusz Petersen
Wierzchołki	10
Krawędzie	15
Promień	2
Średnica	2
Obwód	5
Automorfizmy	120 (S 5 )
Liczba chromatyczna	3
Indeks chromatyczny	4
Ułamkowy indeks chromatyczny	3
Rodzaj	1
Nieruchomości	Sześcienny Silnie regularny Snark przechodni na odległość
Tabela wykresów i parametrów

W matematycznej dziedzinie teorii wykres The wykres Petersen jest nieukierunkowane wykres z 10 wierzchołków i 15 krawędzi . Jest to mały graf, który służy jako użyteczny przykład i kontrprzykład dla wielu problemów teorii grafów. Graf Petersena nosi imię Juliusa Petersena , który w 1898 skonstruował go jako najmniejszy bezmostkowy sześcienny graf bez kolorowania trzech krawędzi.

Chociaż wykres jest powszechnie przypisywany Petersenowi, w rzeczywistości pojawił się po raz pierwszy 12 lat wcześniej, w artykule AB Kempe  ( 1886 ). Kempe zauważył, że jego wierzchołki mogą reprezentować dziesięć linii konfiguracji Desarguesa , a krawędzie reprezentują pary linii, które nie przecinają się w jednym z dziesięciu punktów konfiguracji.

Donald Knuth twierdzi, że graf Petersena jest „niezwykłą konfiguracją, która służy jako kontrprzykład dla wielu optymistycznych przewidywań dotyczących tego, co może być prawdziwe dla grafów w ogóle”.

Wykres Petersena pojawia się również w geometrii tropikalnej . Stożek nad wykresem Petersena jest naturalnie utożsamiany z przestrzenią modułów pięcioramiennych racjonalnych krzywych tropikalnych.

Konstrukcje

Wykres Petersena jako wykres Knesera ${\ Displaystyle KG_ {5,2}}$

Wykres Petersen jest dopełnieniem tego wykresu liniowego z . Jest to również wykres Knesera ; oznacza to, że ma jeden wierzchołek na każdy 2-elementowy podzbiór zestawu 5-elementowego, a dwa wierzchołki są połączone krawędzią wtedy i tylko wtedy, gdy odpowiadające im podzbiory 2-elementowe są od siebie rozłączne. Jako graf Knesera w postaci jest przykładem grafu nieparzystego . ${\ Displaystyle K_ {5}}$ ${\ Displaystyle KG_ {5,2}}$${\ Displaystyle KG_ {2n-1,n-1}}$

Geometrycznie graf Petersena jest grafem utworzonym przez wierzchołki i krawędzie półdwunastościanu , czyli dwunastościanu z przeciwległymi punktami, liniami i ścianami zidentyfikowanymi razem.

Osadzania

Wykres Petersena jest nieplanarny . Każdy ma na wykresie nie płaskie nieletnich albo całkowite wykres , lub pełną wykres dwustronnego , a wykres Petersen zarówno opieki. Moll może być utworzony przez zamawiających brzegach dopasowanie idealnej , na przykład pięć krótkich krawędzi na pierwszym zdjęciu. Podrzędnych może być utworzona przez usunięcie jednego wierzchołka (na przykład centralny wierzchołek rysunku 3-symetryczne) i zaciągnięcie zdarzenie krawędzi każdego sąsiada usuniętego wierzchołka. ${\ Displaystyle K_ {5}}$ ${\ Displaystyle K_ {3,3}}$${\ Displaystyle K_ {5}}$${\ Displaystyle K_ {3,3}}$

Wykres Petersena ma przecięcie numer 2 i jest 1-planarny .

Najpopularniejszy i symetryczny rysunek płaszczyzny wykresu Petersena, jako pentagram w pięciokącie, ma pięć przecięć. Nie jest to jednak najlepszy rysunek do minimalizowania skrzyżowań; istnieje inny rysunek (pokazany na rysunku) z tylko dwoma skrzyżowaniami. Ponieważ jest niepłaski, ma co najmniej jedno przecięcie na dowolnym rysunku, a jeśli krawędź przecięcia zostanie usunięta z dowolnego rysunku, pozostaje niepłaska i ma inne przecięcie; dlatego jego liczba przecięcia wynosi dokładnie 2. Każda krawędź na tym rysunku jest przecinana co najwyżej raz, więc wykres Petersena jest 1-planarny . Na torusie wykres Petersena można narysować bez przecinania się krawędzi; dlatego ma orientowalny rodzaj 1.

Wykres Petersena jest wykresem odległości jednostkowej : można go narysować w płaszczyźnie, przy czym każda krawędź ma jednostkę długości.

Wykres Petersena można również narysować (z przecięciami) w płaszczyźnie w taki sposób, aby wszystkie krawędzie miały jednakową długość. Oznacza to, że jest to wykres odległości jednostkowej .

Najprostszą nieorientowalną powierzchnią, na której można osadzić graf Petersena bez przecięć, jest płaszczyzna rzutowa . To osadzanie podane przez pół-dwunastościanów konstrukcji wykresu Petersen (pokazane na rysunku). Osadzanie płaszczyzny rzutowej można również utworzyć ze standardowego pięciokątnego rysunku wykresu Petersena, umieszczając nasadkę w pięcioramiennej gwieździe w środku rysunku i prowadząc krawędzie gwiazdy przez tę nasadkę; powstały rysunek ma sześć pięciokątnych ścian. Ta konstrukcja tworzy regularną mapę i pokazuje, że wykres Petersena ma niezorientowany rodzaj 1.

Wykres Petersena i związana z nim mapa osadzona w płaszczyźnie rzutowej . Zidentyfikowano przeciwległe punkty na okręgu, dając zamkniętą powierzchnię rodzaju 1.

Symetrie

Wykres Petersena jest silnie regularny (z sygnaturą srg(10,3,0,1)). Jest również symetryczny , co oznacza, że ​​jest przechodni od krawędzi i przechodni wierzchołków . Silniej, jest ona przechodnia 3-łukowa: każda ukierunkowana ścieżka trzech krawędzi w grafie Petersena może zostać przekształcona w każdą inną taką ścieżkę przez symetrię grafu. Jest to jeden z zaledwie 13 sześciennych wykresów regularnych odległości .

Grupa automorfizmu grafu Petersena jest grupą symetryczną ; Działanie na grafie Petersena wynika z jego konstrukcji jako grafu Knesera . Każdy homomorfizm samego grafu Petersena, który nie identyfikuje sąsiednich wierzchołków, jest automorfizmem. Jak pokazano na rysunkach, rysunki wykresu Petersena mogą wykazywać symetrię pięcio- lub trójczynnikową, ale nie jest możliwe narysowanie wykresu Petersena w płaszczyźnie w taki sposób, aby rysunek przedstawiał pełną grupę symetrii wykres. ${\ Displaystyle S_ {5}}$${\ Displaystyle S_ {5}}$

Pomimo wysokiego stopnia symetrii, wykres Petersena nie jest wykresem Cayleya . Jest to najmniejszy graf przechodni wierzchołków, który nie jest grafem Cayleya.

Ścieżki i cykle hamiltonowskie

Wykres Petersena jest hipohamiltonowski: po usunięciu dowolnego wierzchołka, takiego jak wierzchołek środkowy na rysunku, pozostały wykres jest hamiltonianem. Ten rysunek z symetrią rzędu 3 jest tym, który podał Kempe (1886) .

Wykres Petersena ma ścieżkę Hamiltona, ale nie ma cyklu Hamiltona . Jest to najmniejszy bezmostkowy graf sześcienny bez cyklu Hamiltona. Jest to wykres hipohamiltonowski , co oznacza, że ​​chociaż nie ma cyklu hamiltonowskiego, usunięcie dowolnego wierzchołka powoduje, że jest on hamiltonianem i jest najmniejszym grafem hipohamiltonowskim.

Jako skończenie połączony graf przechodni wierzchołków, który nie ma cyklu Hamiltona, graf Petersena jest kontrprzykładem dla wariantu hipotezy Lovásza , ale kanoniczne sformułowanie hipotezy wymaga podania ścieżki Hamiltona i jest weryfikowane przez graf Petersena.

Znanych jest tylko pięć połączonych grafów przechodnich wierzchołków bez cykli Hamiltona: pełny graf K ₂ , graf Petersena, graf Coxetera oraz dwa grafy wyprowadzone z grafów Petersena i Coxetera przez zastąpienie każdego wierzchołka trójkątem. Jeśli G jest 2-spójnym, r- regularnym grafem z co najwyżej 3 r  + 1 wierzchołkami, to G jest hamiltonianem lub G jest grafem Petersena.

Aby zobaczyć, że wykres Petersena nie ma cyklu Hamiltona C , rozważmy krawędzie w przecięciu oddzielające wewnętrzny 5-cykl od zewnętrznego. Jeśli istnieje cykl hamiltonowski, należy wybrać parzystą liczbę tych krawędzi. W przypadku wybrania tylko dwóch z nich, ich wierzchołki końcowe muszą przylegać do siebie w dwóch 5-cyklach, co nie jest możliwe. Dlatego wybrano 4 z nich. Załóżmy, że górna krawędź cięcia nie została wybrana (wszystkie pozostałe przypadki są takie same pod względem symetrii). Z 5 krawędzi w cyklu zewnętrznym należy wybrać dwie krawędzie górne, nie wolno wybierać dwóch krawędzi bocznych, a zatem należy wybrać krawędź dolną. Należy wybrać dwie górne krawędzie w cyklu wewnętrznym, ale to kończy cykl nieobejmujący, który nie może być częścią cyklu Hamiltona. Alternatywnie możemy również opisać grafy regularne z dziesięcioma wierzchołkami , które mają cykl Hamiltona i pokazać, że żaden z nich nie jest grafem Petersena, znajdując w każdym z nich cykl krótszy niż jakikolwiek cykl na grafie Petersena. Każdy dziesięciowierzchołkowy wykres 3-regularny hamiltonianu składa się z dziesięciowierzchołkowego cyklu C plus pięć akordów. Jeśli dowolny akord łączy dwa wierzchołki w odległości dwóch lub trzech wzdłuż C od siebie, wykres ma 3 lub 4 cykle, a zatem nie może być wykresem Petersena. Jeśli dwa akordy łączą przeciwległe wierzchołki C z wierzchołkami w odległości czwartej wzdłuż C , znowu jest 4-cykl. Jedynym pozostałym przypadkiem jest drabina Möbiusa utworzona przez połączenie każdej pary przeciwległych wierzchołków cięciwą, która ponownie ma 4-cykl. Ponieważ wykres Petersena ma obwód 5, nie może być utworzony w ten sposób i nie ma cyklu Hamiltona.

Kolorowanie

4-kolorowanie krawędzi grafu Petersena

3-kolorowanie wierzchołków wykresu Petersena

Wykres Petersena ma chromatyczny numer 3, co oznacza, że ​​jego wierzchołki mogą być pokolorowane trzema kolorami — ale nie dwoma — tak, że żadna krawędź nie łączy wierzchołków tego samego koloru. Ma kolorowanie listowe z 3 kolorami, według twierdzenia Brooksa dla kolorowania listowego.

Wykres Petersena ma indeks chromatyczny 4; kolorowanie krawędzi wymaga czterech kolorów. Jako połączony bezmostkowy graf sześcienny o indeksie chromatycznym cztery, graf Petersena jest snark . Jest to najmniejszy możliwy snark i był jedynym znanym snarkem od 1898 do 1946 roku. Twierdzenie Snarka , wynik przypuszczony przez WT Tutte i ogłoszony w 2001 przez Robertsona, Sandersa, Seymoura i Thomasa, stwierdza, że ​​każdy snark ma wykres Petersena jako nieletni .

Dodatkowo wykres ma ułamkowy indeks chromatyczny 3, co dowodzi, że różnica między ułamkowym indeksem chromatycznym a ułamkowym indeksem chromatycznym może wynosić nawet 1. Długoletnia hipoteza Goldberga-Seymoura sugeruje, że jest to największa możliwa luka.

Liczba Thue (wariant indeksu chromatycznego) wykresu Petersena wynosi 5.

Wykres Petersena wymaga co najmniej trzech kolorów w dowolnym (prawdopodobnie niewłaściwym) zabarwieniu, które łamie wszystkie jego symetrie; to znaczy, że jego numer wyróżniający to trzy. Poza grafami kompletnymi jest to jedyny graf Knesera, którego liczbą wyróżniającą nie są dwa.

Inne właściwości

Wykres Petersena:

• jest 3-połączony, a zatem 3-krawędziowy i bezmostkowy. Zobacz słowniczek .
• ma niezależność numer 4 i jest trójstronna. Zobacz słowniczek .
• jest sześcienny , ma dominację numer 3 i ma idealne dopasowanie i 2-czynnik .
• ma 6 wyraźnych idealnych dopasowań.
• jest najmniejszym wykresem sześciennym obwodu 5. (Jest to unikalny - klatka . W rzeczywistości, ponieważ ma tylko 10 wierzchołków, jest to unikalny wykres - Moore'a .)${\ Displaystyle (3,5)}$${\ Displaystyle (3,5)}$
• jest najmniejszym grafem sześciennym z niezmiennikiem grafu Colina de Verdière μ = 5.
• jest najmniejszym wykresem policjanta numer 3.
• ma promień 2 i średnicę 2. Jest to największy wykres sześcienny o średnicy 2.
• ma widmo wykresu -2, -2, -2, -2, 1, 1, 1, 1, 1, 3.
• ma 2000 drzew opinających , najwięcej z każdego 10-wierzchołkowego grafu sześciennego.
• ma wielomian chromatyczny .${\ Displaystyle t (t-1) (t-2) \ lewo (t ^ {7} -12t ^ {6} + 67 t ^ {5} -230 t ^ {4} + 529 t ^ {3}-814 t ^ { 2}+775t-352\prawo)}$
• ma charakterystyczny wielomian , co czyni go grafem całkowym — grafem, którego widmo składa się wyłącznie z liczb całkowitych.${\ Displaystyle (t-1) ^ {5} (t + 2) ^ {4} (t-3)}$

Przypuszczenie kolorowania Petersena

Według DeVosa, Nesetrila i Raspauda cykl grafu G jest takim zbiorem , że każdy wierzchołek grafu ( V ( G ), C ) ma równy stopień. Jeśli są wykresami, definiujemy mapę jako ciągłą cyklicznie, jeśli wstępny obraz każdego cyklu jest cyklem . Fascynujące przypuszczenie Jaegera twierdzi, że każdy graf bez mostków ma odwzorowanie ciągłe na grafie Petersena. Jaeger wykazał, że to przypuszczenie implikuje hipotezę o podwójnej osłonie 5 cykli i hipotezę Berge-Fulkersona. ${\displaystyle C\subseteq E(G)}$${\ Displaystyle G, H}$${\ Displaystyle \ phi: E (G) \ do E (H)}$${\ Displaystyle H}$${\ Displaystyle G}$

Powiązane wykresy

Rodzina Petersenów .

Uogólnione wykres Petersen jest utworzony przez połączenie wierzchołków o regularnym n gon do odpowiednich wierzchołkach gwiazdy wielokąta z symbol schläfliego { n / k }. Na przykład w tym zapisie graf Petersena to : można go utworzyć łącząc odpowiednie wierzchołki pięciokąta i gwiazdy pięcioramiennej, a krawędzie gwiazdy łączą co drugi wierzchołek. Uogólniony wykresy Petersen obejmują również ń -prism się wykres Dürer , z wykresu Möbiusa-Kantor , ten dwunastościan , z wykresu Desargues i wykres Nauru . ${\ Displaystyle G (n, k)}$${\ Displaystyle G (5,2)}$${\ Displaystyle G (n, 1)}$ ${\ Displaystyle G (6,2)}$ ${\ Displaystyle G (8,3)}$ ${\ Displaystyle G (10,2)}$ ${\ Displaystyle G (10,3)}$ ${\ Displaystyle G(12,5)}$

Rodzina Petersena składa się z siedmiu grafów, które można utworzyć z grafu Petersena przez zero lub więcej zastosowań przekształceń Δ-Y lub Y-Δ . Zakończeniu wykres K ₆ jest w rodzinie Petersen. Grafy te tworzą zabronione podrzędne dla grafów osadzanych bez linków, grafów , które można osadzić w przestrzeni trójwymiarowej w taki sposób, że żadne dwa cykle w grafie nie są połączone .

Wykres Clebsch zawiera wiele kopii wykresu Petersena indukowanych subgraphs : dla każdego wierzchołka v wykresu Clebsch, dziesięć nie-sąsiadujących z v indukuje kopię wykresu Petersen.

Uwagi

Bibliografia

• Exoo, Geoffrey; Harary, Frank ; Kabell, Jerald (1981), „Liczby przekroczenia niektórych uogólnionych wykresów Petersena”, Mathematica Scandinavica , 48 : 184-188, doi : 10.7146/math.scand.a-11910.
• Coxeter, HSM (1950), „konfiguracje samodzielna i regularne wykresy”, Biuletyn Amerykańskiego Towarzystwa Matematycznego , 56 (5): 413-455, doi : 10.1090/S0002-9904-1950-09407-5.
• Holton, Waszyngton; Sheehan, J. (1993), The Petersen Graph , Cambridge University Press , doi : 10.2277/0521435943 , ISBN 0-521-43594-3.
• Jakobson, Dmitrij; Rivin, Igor (1999), O niektórych ekstremalnych problemach w teorii grafów , arXiv : math.CO/9907050
• Kempe, AB (1886), „Pamiętnik na temat teorii formy matematycznej”, Philosophical Transactions of the Royal Society of London , 177 : 1-70, doi : 10.1098/rstl.1886.0002
• Lovász, László (1993), problemy i ćwiczenia kombinatoryczne (2nd ed.), North-Holland, ISBN 0-444-81504-X.
• Petersen Julius (1898), "Sur le théorème de Tait", L'Intermédiaire des Mathématiciens , 5 : 225-227
• Schwenk, AJ (1989), „Wyliczanie cykli Hamiltona w niektórych uogólnionych wykresach Petersena”, Journal of Combinatorial Theory , Seria B, 47 (1): 53-59, doi : 10.1016/0095-8956 (89) 90064-6
• Valdes, L. (1991), "Ekstremalne właściwości drzew rozpinających w wykresach sześciennych", Congressus Numerantium , 85 : 143-160.
• Watkins, Mark E. (1969), "Twierdzenie o kolorystyce Tait z zastosowaniem do uogólnionych wykresów Petersena", Journal of Combinatorial Theory , 6 (2): 152-164, doi : 10.1016/S0021-9800 (69) 80116 -X

Linki zewnętrzne

• Weisstein, Eric W. "Wykres Petersena" . MatematykaŚwiat .
• Wykres Petersena w internetowej encyklopedii ciągów liczb całkowitych