Greve af Petersen

Greve af Petersen
Opkaldt efter Julius Petersen
Toppe ti
ribben femten
Radius 2
Diameter 2
Omkreds 5
Automorfismer 120 ( S5 )
Kromatisk tal 3
Kromatisk indeks fire
Slægt en
Ejendomme Cubic
Strongly Regular
Distance-Transitive
Snark
 Mediefiler på Wikimedia Commons

Petersen-grafen  er en urettet graf med 10 hjørner og 15 kanter; en ret simpel graf brugt som eksempel og modeksempel på mange problemer i grafteori.

Opkaldt efter Julius Petersen , der konstruerede den i 1898 som den mindste broløse kubiske graf , der ikke har en trefarvet kantfarvning [1] . Samtidig er den første omtale af en sådan graf noteret i en artikel fra 1886 af Kempe [2] , hvori det bemærkes, at dens toppunkter kan betragtes som ti linjer af Desargues-konfigurationen , og kanterne er par af linjer hvis kryds ikke hører til konfigurationen.

Donald Knuth bemærker grafen som bemærkelsesværdig for at give modeksempler til mange "optimistiske" udsagn om grafer generelt [3] .

Petersen-grafen optræder også i tropisk geometri : keglen over Petersen-grafen er naturligt identificeret af det modulære rum af fempunkts rationelle tropiske kurver.

Bygning

Petersen-grafen er komplementet til linjegrafen for . Greven er også en Kneser-tælling . Det betyder, at grafen har et toppunkt for hver 2-element-delmængde af et 5-element-sæt, og to spidser er forbundet med en kant, hvis og kun hvis de tilsvarende 2-element-delmængder ikke skærer hinanden. Som en Kneser-graf af formen er grafen en ulige graf .

Geometrisk er en Petersen-graf en graf, der er dannet af hjørnerne og kanterne af et semi-dodekaeder , det vil sige et dodekaeder med modsatte spidser, kanter og flader identificeret.

Vedhæftede filer

Petersen-grafen er ikke plan . Enhver ikke-plan graf har enten en komplet graf eller en komplet todelt graf som mindre , men Petersen-grafen har begge grafer som mindre. Den mindre kan fås ved at trække kanterne sammen på en perfekt matchende , for eksempel de fem korte kanter i den første figur. En minor kan opnås ved at slette et toppunkt (for eksempel det centrale toppunkt i et 3-symmetrisk mønster) og trække kanterne sammen, der falder ind til hver nabo af det fjernede toppunkt.

Den generelt accepterede mest symmetriske plane tegning af Petersen-grafen som en femkant i en femkant har fem skæringspunkter. Dette er dog ikke det mest optimale mønster, hvilket minimerer antallet af kryds. Der er et andet mønster (vist til højre) med kun to kryds. Petersen-grafen har således skæringsnummer 2. Hver kant i denne figur krydses højst én gang, så Petersen-grafen er 1-plan . På en torus kan Petersen-grafen tegnes uden krydsende kanter. Grafen har således orienterbar slægt 1.

Petersen-grafen kan også tegnes (med skæringer) på planet på en sådan måde, at alle kanter har samme længde. Grafen er således en enhedsafstandsgraf .

Den enkleste ikke-orienterbare overflade , hvori Petersen-grafen kan indlejres uden skæringspunkter, er det projektive plan . Dette er en indlejring, der er givet ved at konstruere Petersen-grafen som et semi-dodekaeder . En indlejring i det projektive plan kan også dannes ud fra standard Petersen femkantet tegning ved at placere en film (en skåret Klein flaske) inde i den femkantede stjerne i midten af ​​tegningen og lede stjernens kanter gennem denne film. Det resulterende mønster har seks femkantede flader. Denne konstruktion danner et regulært kort og viser, at Petersen-grafen har ikke-orienterbar slægt 1.

Symmetrier

Petersen-grafen er stærkt regelmæssig (med signatur srg(10,3,0,1)). Grafen er også symmetrisk , hvilket betyder, at den er kanttransitiv og toppunkttransitiv . Mere strengt er grafen 3-bue-transitiv - enhver rettet sti af de tre stier i Petersen-grafen kan afbildes til enhver anden sådan sti ved grafsymmetri [4] . Grafen er en af ​​13 kubiske afstand-regulære grafer . [5]

Automorfigruppen i Petersen-grafen er den symmetriske gruppe . Handlingen på Petersen-grafen følger af dens konstruktion som en Kneser-graf . Enhver homeomorfi af Petersen-grafen på sig selv, der ikke identificerer tilstødende hjørner, er en automorfi. Som vist på illustrationerne kan tegninger af Petersen-grafen vise symmetrier i fem retninger eller i tre retninger, men det er ikke muligt at tegne en Petersen-graf på planet på en sådan måde, at tegningen viser fuldstændig symmetri af grafgruppen.

På trods af sin høje symmetri er Petersen-grafen ikke en Cayley-graf , det er den mindste toppunkt-transitive graf, der ikke er en Cayley-graf. [6]

Hamiltonske stier og cykler

Petersen-grafen har en Hamiltonsk sti, men ikke en Hamiltonsk cyklus . En graf er den mindste ikke-brokoblede kubiske graf, der ikke har en Hamiltonsk cyklus. Grafen er hypo -Hamiltonsk, hvilket betyder, at selvom den ikke har en Hamiltonsk cyklus, bliver den Hamiltonsk, hvis man fjerner ethvert toppunkt, og det er den mindste hypo-Hamiltonske graf.

Som en endelig forbundet vertex-transitiv graf uden Hamilton-cyklus er Petersen-grafen et modeksempel på en variant af Lovas-formodningen , men den kanoniske formulering af formodningen beder om en Hamilton-sti, og for Petersen-grafen gælder denne formodning.

Kun fem forbundne vertex-transitive grafer uden Hamiltonske cyklusser kendes - den komplette K 2 - graf, Petersen - grafen, Coxeter - grafen og to grafer opnået fra Petersen- og Coxeter-graferne ved at erstatte hvert toppunkt med en trekant [7] . Hvis G er en 2-forbundet, r - regulær graf med højst 3r  + 1 hjørner, så er G Hamiltonsk eller G er en Petersen-graf [8] .

For at vise, at Petersen-grafen ikke har en Hamiltonsk cyklus C , skal du overveje kanterne, der forbinder den indre 5-vertex-cyklus med den ydre cyklus. Hvis der er en Hamilton-cyklus, skal der vælges et lige antal af disse kanter. Hvis der kun vælges to kanter, skal deres endespidser støde op til hinanden i begge 5-vertex-cyklusser, hvilket ikke er muligt. Der skal således vælges 4 kanter. Antag, at den øverste kant ikke er valgt (alle andre tilfælde ligner hinanden på grund af symmetri). Af de 5 kanter af den ydre cyklus skal de to øverste kanter indgå i Hamiltons cyklus, så de to sidekanter skal ikke indgå i cyklussen, og så skal den nederste kant med i cyklussen. De to øverste kanter i den indre cyklus skal vælges, men så lukker de to kanter en cyklus, der ikke er færdig, så den kan ikke indgå i en Hamilton-cyklus. Alternativt kan vi betragte ti-vertex 3-regulære grafer , der har en Hamilton-cyklus, og vise, at ingen af ​​disse grafer er en Petersen-graf ved at finde en cyklus i hver af dem, der er kortere end nogen cyklus af Petersen-grafen. Enhver ti-vertex Hamiltonian 3-regulær graf består af en ti-vertex cyklus C plus fem akkorder. Hvis en akkord forbinder to hjørner langs C i en afstand af to eller tre fra hinanden, så har grafen en 3-cyklus eller en 4-cyklus, og kan derfor ikke være en Petersen-graf. Hvis to akkorder forbinder modsatte hjørner af en cyklus C i en afstand af fire langs C , er der igen en 4-cyklus. Kun tilfældet af Möbius-stigen er tilbage , dannet ved at forbinde hvert par af modsatte sider med en korde, som igen har en 4-cyklus. Da Petersen-grafens omkreds er fem, kan den ikke dannes på denne måde, og har derfor ikke en Hamiltonsk cyklus.

Farvelægningsside

Petersen-grafen har kromatisk nummer 3, hvilket betyder, at grafens spidser kan farves med tre farver, men ikke med to, så ingen kant forbinder to spidser af samme farve. Grafen har en foreskrevet farvning af 3 farver ifølge Brooks' sætning for foreskrevne farvninger. Petersen-grafen har kromatisk indeks 4, hvilket betyder, at kantfarvning kræver fire farver. Grafen er med andre ord ikke summen af ​​tre 1-faktorer , som blev vist af Petersen selv [9] . For at bevise dette skal fire tilfælde kontrolleres for at vise, at der ikke er 3-farvning af kanter. Som en broløs forbundet kubisk graf med kromatisk indeks fire er Petersen-grafen en snark . Denne graf er den mindst mulige snark. Han var den eneste kendte snert i perioden 1898-1946. Snark - sætningen , angivet i form af Tutt- formodningen (bevist i 2001 af Robertson, Sanders, Seymour og Thomas [10] ), siger, at enhver snark har en Petersen-graf som en mol .

Derudover har grafen et brøkkromatisk indeks på 3, hvilket understøtter påstanden om, at forskellen mellem det kromatiske indeks og det brøkkromatiske indeks kan være 1. Den langvarige Goldberg-Seymour-formodning antyder, at dette er den størst mulige forskel.

Thue-tallet (en variant af det kromatiske indeks) af Petersen-grafen er 5.

Petersen-grafen kræver mindst tre farver i enhver (muligvis ukorrekt) farve, der bryder alle symmetrier. Det vil sige, at det karakteristiske farvetal på grafen er lig med tre. Med undtagelse af komplette grafer er der kun en Kneser-graf, hvis karakteristiske tal ikke er lig med to [11] .

Andre egenskaber

Grev Petersen:

Petersens farvelægningsformodning

Ifølge Devos, Nexetril og Raspo, " Cyklusen af ​​en graf G er et sæt C E(G), således at ethvert toppunkt på grafen (V(G),C) har en lige grad. Hvis G, H er grafer, definerer vi en afbildning φ: E(G) -> E(H) som cykluskontinuerlig, hvis forbilledet af enhver cyklus i H er en cyklus i G. François Jaeger formulerede en formodning, der siger at enhver broløs graf har et cykluskontinuerligt kort til Petersen-grafen. Jaguer viste, at hvis formodningen er sand, så er den dobbeltdækkende formodning med cyklusser af længde 5 og Berge-Fulkerson formodningen også sande. [16] .

Relaterede grafer

Den generaliserede Petersen-graf G ( n , k ) dannes ved at forbinde hjørnerne af en regulær n - gon med de tilsvarende hjørner af en stjernepolygon med Schläfli-symbolet { n / k } [17] [18] . For eksempel er Petersen-grafen i disse notationer betegnet som G (5,2) - den kan dannes ved at forbinde de tilsvarende toppunkter af en femkant og en femkantet stjerne, mens stjernens toppunkter er forbundet gennem en. Generaliserede Petersen-grafer omfatter også n -prismer G ( n ,1), Dürer-graf G (6,2), Möbius-Cantor-graf G (8,3), dodecahedron -graf G (10,2), Desargues-graf G (10, 3) og grev Nauru G (12,5).

Petersen-familien af ​​grafer består af syv grafer, der kan dannes ud fra en Petersen-graf ved at anvende nul eller flere transformationer Δ-Y eller Y-Δ . Den komplette graf K 6 tilhører også familien Petersen. Disse grafer danner forbudte mindreårige for link-fri indlejrbare grafer , grafer, der kan indlejres i tredimensionelt rum på en sådan måde, at ikke to cyklusser i grafen er forbundet [19]

Clebsch-grafen består af kopier af Petersen-grafen som genererede undergrafer  — for hvert toppunkt v på Clebsch-grafen genererer ti ikke-nabo-vertices v en kopi af Petersen-grafen.

Noter

  1. ↑ Petersen-grafen .
  2. ↑ Kempe, 1886 .
  3. ↑ Knuth, 2011 .
  4. ↑ Babai, 1995 , s. 1447-1540.
  5. ↑ Ifølge Fosterlisten .
  6. ↑ Som nævnt forudsætter dette, at Cayley-graferne ikke nødvendigvis hænger sammen. Nogle kilder kræver, at Cayley-grafer forbindes, hvilket gør den tomme to-vertex-graf til den mindste vertex-transitive graf, der ikke er en Cayley-graf. Per definition givet i disse kilder er en Petersen-graf den mindste forbundne vertex-transitive graf, der ikke er en Cayley-graf.
  7. ↑ Royle, G. "Cubic Symmetric Graphs (The Foster Census)." Arkiveret fra originalen den 20. juli 2008.
  8. ↑ Holton, Sheehan, 1993 , s. 32.
  9. ↑ Harari, 2003 , s. 113.
  10. ↑ Pegg, 2002 , s. 1084-1086.
  11. ↑ Albertson, Boutin, 2007 , s. 20 kr.
  12. ↑ Hoffman, Singleton, 1960 , s. 497-504.
  13. ↑ Dette følger af, at grafen er en Moore-graf, da Moore-grafen er den størst mulige regulære graf med den grad af hjørner og diameter ( Hoffman, Singleton 1960 ).
  14. ↑ Jakobson, Rivin, 1999 ; Valdes, 1991 . Kubiske grafer med 6 og 8 toppunkter, hvor antallet af spændende træer er maksimeret, er Möbius-stiger .
  15. ↑ Biggs, 1993 .
  16. ↑ DeVos, Nešetřil, Raspaud, 2007 , s. 109-138.
  17. ↑ Coxeter, 1950 .
  18. ↑ Watkins, 1969 .
  19. ↑ Bailey, 1997 , s. 187.

Litteratur

Links