Petersen graf

Petersen-grafen
Petersen-grafen
	Petersen-grafen ritas oftast som en femhörning med ett pentagram inuti, med fem ekrar.
Döpt efter	Julius Petersen
Vertices	10
Kanter	15
Radie	2
Diameter	2
Omkrets	5
Automorfismer	120 (S 5 )
Kromatiskt nummer	3
Kromatiskt index	4
Bråktal kromatiskt index	3
Släkte	1
Egenskaper	; ; ; Kubisk Starkt regelbunden Distanstransitiv Snark
	Tabell över grafer och parametrar

Inom det matematiska området grafteori är Petersen -grafen en oriktad graf med 10 hörn och 15 kanter . Det är en liten graf som fungerar som ett användbart exempel och motexempel på många problem inom grafteorin. Petersen-grafen är uppkallad efter Julius Petersen , som 1898 konstruerade den för att vara den minsta brolösa kubiska grafen utan trekantsfärgning.

Även om grafen i allmänhet krediteras Petersen, hade den faktiskt förekommit 12 år tidigare, i en tidning av AB Kempe ( 1886 ). Kempe observerade att dess hörn kan representera de tio linjerna i Desargues-konfigurationen , och dess kanter representerar par av linjer som inte möts vid en av de tio punkterna i konfigurationen.

Donald Knuth konstaterar att Petersen-grafen är "en anmärkningsvärd konfiguration som fungerar som ett motexempel till många optimistiska förutsägelser om vad som kan vara sant för grafer i allmänhet."

Petersen-grafen gör också ett framträdande i tropisk geometri . Konen över Petersen-grafen identifieras naturligt med modulutrymmet hos femuddiga rationella tropiska kurvor.

Konstruktioner

Petersen graf som Kneser graf

KG_{5,2}

Petersen-grafen är komplementet till linjediagrammet för $K_{5}$ . Det är också Kneser-grafen $KG_{5,2}$ ; detta betyder att den har en vertex för varje 2-elements underuppsättning av en 5-elementsuppsättning, och två hörn är förbundna med en kant om och endast om motsvarande 2-elements underuppsättningar är åtskilda från varandra. Som en Kneser-graf av formen $KG_{2n-1,n-1}$ är det ett exempel på en udda graf .

Geometriskt är Petersen-grafen den graf som bildas av hörn och kanter på hemi-dodekaedern , det vill säga en dodekaeder med motsatta punkter, linjer och ytor identifierade tillsammans.

Inbäddningar

Petersen-grafen är icke-planär . Alla icke-planära grafer har som molor antingen den fullständiga grafen $K_{5}$ , eller den fullständiga tvådelade grafen $K_{3,3}$ , men Petersen-grafen har båda som moll. K $K_{5}$ moll kan bildas genom att dra ihop kanterna på en perfekt matchning till exempel de fem kortkanterna i den första bilden. K $K_{3,3}$ moll kan bildas genom att ta bort en vertex (till exempel den centrala vertexen på den 3-symmetriska ritningen) och dra ihop en kant som faller in på varje granne till den borttagna vertexen

Petersen-grafen har korsning nummer 2 och är 1-plan .

Den vanligaste och symmetriska planritningen av Petersen-grafen, som ett pentagram inom en femhörning, har fem korsningar. Detta är dock inte den bästa ritningen för att minimera korsningar; det finns en annan ritning (visad i figuren) med endast två korsningar. Eftersom den är icke-plan, har den åtminstone en korsning i varje ritning, och om en korsande kant tas bort från någon ritning förblir den icke-plan och har en annan korsning; därför är dess korsningsnummer exakt 2. Varje kant i denna ritning korsas högst en gång, så Petersen-grafen är 1-plan . På en torus kan Petersen-grafen ritas utan kantkorsningar; den har därför orienterbart släkte 1.

Petersen-grafen är en enhetsavståndsgraf : den kan ritas i planet med varje kant med enhetslängd.

Petersen-grafen kan också ritas (med korsningar) i planet på ett sådant sätt att alla kanter har lika långa. Det vill säga, det är en enhetsdistansgraf .

Den enklaste icke-orienterbara ytan på vilken Petersen-grafen kan bäddas in utan korsningar är det projektiva planet . Detta är inbäddningen som ges av hemi-dodekaederkonstruktionen av Petersen-grafen (visas i figuren). Den projektiva planinbäddningen kan också formas från den femkantiga standardritningen av Petersen-grafen genom att placera en korsmössa inom fempunktsstjärnan i mitten av ritningen, och dirigera stjärnkanterna genom denna tvärkåpa; den resulterande teckningen har sex femkantiga ytor. Denna konstruktion bildar en vanlig karta och visar att Petersen-grafen har icke-orienterbart släkte 1.

Petersen-grafen och tillhörande karta inbäddade i det projektiva planet . Motsatta punkter på cirkeln identifieras, vilket ger en sluten yta av icke-orienterbart släkte 1.

Symmetrier

Petersen-grafen är starkt regelbunden (med signatur srg(10,3,0,1)). Den är också symmetrisk , vilket betyder att den är kanttransitiv och vertextransiv . Ännu starkare är den 3-bågstransitiv: varje riktad trekantsbana i Petersen-grafen kan omvandlas till varannan sådan bana genom en symmetri av grafen. Det är en av endast 13 kubikavstånd -reguljära grafer .

Automorfismgruppen i Petersen-grafen är den symmetriska gruppen $S_{5$ } ; verkan av $S_{5}$ på Petersen-grafen följer av dess konstruktion som en Kneser-graf . Petersen-grafen är en kärna : varje homomorfism av Petersen-grafen till sig själv är en automorfism. Som visas i figurerna kan ritningarna av Petersen-grafen uppvisa femvägs- eller trevägssymmetri, men det är inte möjligt att rita Petersen-grafen i planet på ett sådant sätt att ritningen visar hela symmetrigruppen för Graf.

Trots sin höga grad av symmetri är Petersen-grafen inte en Cayley-graf . Det är den minsta vertextransitiva grafen som inte är en Cayley-graf.

Hamiltonska stigar och cyklar

Petersen-grafen är hypo-Hamiltonsk: genom att ta bort valfri hörn, såsom mittpunkten i ritningen, blir den återstående grafen Hamiltonsk. Denna ritning med order-3 symmetri är den som ges av Kempe (1886) .

Petersen-grafen har en Hamiltonsk väg men ingen Hamiltonsk cykel . Det är den minsta brolösa kubiska grafen utan Hamiltonsk cykel. Det är hypohamiltonskt , vilket betyder att även om det inte har någon Hamiltonsk cykel, blir det Hamiltonian om man tar bort någon vertex och är den minsta hypohamiltonska grafen.

Som en finit sammankopplad vertextransitiv graf som inte har en Hamiltonsk cykel, är Petersen-grafen ett motexempel till en variant av Lovász-förmodan, men den kanoniska formuleringen av gissningen frågar efter en Hamiltonsk väg och verifieras av Petersen-grafen.

Endast fem sammankopplade vertextransitiva grafer utan Hamiltonska cykler är kända: den fullständiga grafen K ₂ , Petersen-grafen, Coxeter-grafen och två grafer härledda från Petersen- och Coxeter-graferna genom att ersätta varje vertex med en triangel. Om G är en 2-kopplad, r -regelbunden graf med högst 3 r + 1 hörn, så är G Hamiltonian eller G Petersen-grafen.

För att se att Petersen-grafen inte har någon Hamiltonsk cykel C , betrakta kanterna i snittet som kopplar bort den inre 5-cykeln från den yttre. Om det finns en Hamiltonsk cykel måste ett jämnt antal av dessa kanter väljas. Om endast två av dem väljs, måste deras ändpunkter ligga intill i de två 5-cyklerna, vilket inte är möjligt. Därför är 4 av dem utvalda. Antag att den övre kanten av snittet inte är vald (alla andra fall är desamma genom symmetri). Av de 5 kanterna i den yttre cykeln måste de två övre kanterna väljas, de två sidokanterna får inte väljas, och därför måste den nedre kanten väljas. De två översta kanterna i den inre cykeln måste väljas, men detta fullbordar en icke-spännande cykel, som inte kan ingå i en Hamiltonsk cykel. Alternativt kan vi också beskriva tio-vertex 3-regelbundna grafer som har en Hamilton-cykel och visa att ingen av dem är Petersen-grafen, genom att hitta en cykel i var och en av dem som är kortare än någon cykel i Petersen-grafen. Vilken Hamiltonian 3-regelbunden graf med tio vertex består av en cykel C med tio vertex plus fem ackord. Om något ackord förbinder två hörn på avstånd två eller tre längs C från varandra, har grafen en 3-cykel eller 4-cykel, och kan därför inte vara Petersen-grafen. Om två ackord förbinder motsatta hörn av C till hörn på avstånd fyra längs C , finns det återigen en 4-cykel. Det enda kvarvarande fallet är en Möbius-stege bildad genom att förbinda varje par av motsatta hörn med en korda, som återigen har en 4-cykel. Eftersom Petersen-grafen har omkrets fem kan den inte formas på detta sätt och har ingen Hamiltonsk cykel.

Färg

En 4-färgning av Petersen-grafens kanter

En 3-färgning av Petersen-grafens hörn

Petersen-grafen har kromatisk nummer 3, vilket betyder att dess hörn kan färgas med tre färger - men inte med två - så att ingen kant förbinder hörn av samma färg. Den har en listfärgning med 3 färger, enligt Brooks sats för listfärger.

Petersen-grafen har kromatiskt index 4; färgning av kanterna kräver fyra färger. Som en sammankopplad brolös kubisk graf med kromatiskt index fyra är Petersen-grafen en snark . Det är den minsta möjliga snarken och var den enda kända snarken från 1898 till 1946. Snarksatsen, ett resultat som gissningsvis av WT Tutte och tillkännagav 2001 av Robertson, Sanders, Seymour och Thomas, säger att varje snark har Petersen-grafen som minderårig .

Dessutom har grafen bråkdelskromatiskt index 3, vilket bevisar att skillnaden mellan det kromatiska indexet och bråkdelskromatiskt index kan vara så stor som 1. Den långvariga Goldberg-Seymour-förmodan föreslår att detta är det största möjliga gapet.

Thue -talet (en variant av det kromatiska indexet) på Petersen-grafen är 5.

Petersen-grafen kräver minst tre färger i alla (möjligen felaktiga) färger som bryter alla dess symmetrier; det vill säga dess särskiljande nummer är tre. Förutom de fullständiga graferna är det den enda Kneser-grafen vars särskiljande nummer inte är två.

Övriga fastigheter

Petersen-grafen:

är 3-kopplad och därmed 3-kant-ansluten och brygglös. Se ordlistan .
har självständighetsnummer 4 och är 3-delad. Se ordlistan .
är kubisk , har dominans nummer 3 och har en perfekt matchning och en 2-faktor .
har 6 distinkta perfekta matchningar.
är den minsta kubiska grafen av omkrets 5. (Det är den unika $(3,5)$ - buren . Faktum är att eftersom den bara har 10 hörn, är den den unika $(3,5)$ - Moore-graf .)
är den minsta kubiska grafen med Colin de Verdières graf invariant μ = 5.
är den minsta grafen för polis nummer 3.
har radie 2 och diameter 2. Det är den största kubiska grafen med diameter 2.
har 2000 spännande träd , det mesta av någon kubikgraf med 10 vertex.
har kromatiskt polynom ${\-display 1)(t-2)\left(t^{7}-12t^{6}+67t^{5}-230t^{4}+529t^{3}-814t^{2}+775t-352\ höger)}$ .
har karakteristiskt polynom ${\displaystyle (t-1)^{5}(t+2)^{4}(t-3)} , vilket$ gör det en integralgraf — en graf vars spektrum helt består av heltal.

Petersen färgläggning gissningar

En Eulerisk subgraf av en graf $G$ är en subgraf som består av en delmängd av kanterna på ${\displaystyle G} ,$ som vidrör varje vertex av $G$ ett jämnt antal gånger. Dessa subgrafer är elementen i cykelrymden för $G$ och kallas ibland för cykler. Om $G$ och ${\displaystyle H} är två grafer,$ definieras en funktion från kanterna på $G$ till kanterna på ${\displaystyle H} att vara$ cykelkontinuerlig om pre-image av varje cykel av $H$ är en cykel av $G$ . En gissning av Jaeger hävdar att varje brolös graf har en cykelkontinuerlig mappning till Petersen-grafen. Jaeger visade att denna gissning antyder 5- cykel-dubbeltäckningsförmodan och Berge-Fulkerson-förmodan."

Relaterade grafer

Familjen Petersen .

Den generaliserade Petersen-grafen $G(n,k)$ bildas genom att koppla hörnen på en vanlig n -gon till motsvarande hörn i en stjärnpolygon med Schläfli-symbolen { n / k }. Till exempel, i denna notation är Petersen-grafen $G(5,2)$ : den kan bildas genom att koppla samman motsvarande hörn av en femkant och fempunktsstjärna, och kanterna i stjärnanslutning varannan vertex. De generaliserade Petersen-graferna inkluderar också n -prismat $G(n,1)$ Dürer -grafen $G(6,2)$ , Möbius-Kantor graf $G(8,3)$ , dodekaedern $G(10,2)$ , Desargues-grafen $G (10,3)$ och Nauru-grafen $G(12,5)$ .

Petersen -familjen består av de sju graferna som kan bildas från Petersen-grafen genom noll eller fler tillämpningar av Δ-Y- eller Y-Δ-transformer . Den kompletta grafen K ₆ finns också i Petersen-familjen. Dessa grafer bildar de förbjudna minorerna för länklöst inbäddningsbara grafer , grafer som kan bäddas in i tredimensionellt utrymme på ett sådant sätt att inga två cykler i grafen är länkade .

Clebsch -grafen innehåller många kopior av Petersen-grafen som inducerade subgrafer : för varje vertex v i Clebsch-grafen, inducerar de tio icke-grannarna till v en kopia av Petersen-grafen.

Anteckningar

Vidare läsning

Exoo, Geoffrey; Harary, Frank ; Kabell, Jerald (1981), "The crossing numbers of some generalized Petersen graphs", Mathematica Scandinavica , 48 : 184–188, doi : 10.7146/math.scand.a-11910 .
Lovász, László (1993), Combinatorial Problems and Exercises (2nd ed.), North-Holland, ISBN 0-444-81504-X .
Schwenk, AJ (1989), "Enumeration of Hamiltonian cycles in certain generalized Petersen graphs", Journal of Combinatorial Theory , Series B, 47 (1): 53–59, doi : 10.1016/0095-8956(89)90064-6

externa länkar