Greve av Petersen

Petersen-grafen  är en oriktad graf med 10 hörn och 15 kanter; en ganska enkel graf som används som exempel och motexempel för många problem inom grafteorin.

Uppkallad efter Julius Petersen , som konstruerade den 1898 som den minsta brolösa kubiska grafen som inte har en trefärgad kantfärgning [1] . Samtidigt noteras det första omnämnandet av en sådan graf i en artikel från 1886 av Kempe [2] , där det noteras att dess hörn kan betraktas som tio linjer av Desargues-konfigurationen , och kanterna är par av linjer vars korsning inte tillhör konfigurationen.

Donald Knuth noterar grafen som anmärkningsvärd för att ge motexempel till många "optimistiska" uttalanden om grafer i allmänhet [3] .

Petersen-grafen visas också i tropisk geometri : konen över Petersen-grafen identifieras naturligt av det modulära utrymmet av fempunktsrationella tropiska kurvor.

Byggnad

Petersen-grafen är komplementet till linjediagrammet för . Greven är också en Kneser-greve . Detta innebär att grafen har en vertex för varje 2-elements undermängd av en 5-elementsuppsättning, och två hörn är sammankopplade med en kant om och endast om motsvarande 2-elements undermängder inte skär varandra. Som en Kneser-graf av formen är grafen en udda graf .

Geometriskt är en Petersen-graf en graf som bildas av hörn och kanter av en semi-dodekaeder , det vill säga en dodekaeder med motsatta hörn, kanter och ytor identifierade.

Bilagor

Petersen-grafen är inte plan . Alla icke-planära grafer har antingen en fullständig graf eller en fullständig tvådelad graf som underordnade , men Petersen-grafen har båda graferna som underordnade. Den mindre kan erhållas genom att dra ihop kanterna på en perfekt matchning , till exempel de fem kortkanterna i den första figuren. En minor kan erhållas genom att ta bort en vertex (till exempel den centrala vertexen i ett 3-symmetriskt mönster) och dra ihop kanterna som faller in mot varje granne till den borttagna vertexen.

Den allmänt accepterade mest symmetriska plana ritningen av Petersen-grafen som en femhörning inom en femhörning har fem skärningspunkter. Detta är dock inte det mest optimala mönstret, vilket minimerar antalet korsningar. Det finns ett annat mönster (visas till höger) med bara två korsningar. Således har Petersen-grafen skärningsnummer 2. Varje kant i denna figur korsas högst en gång, så Petersen-grafen är 1-plan . På en torus kan Petersen-grafen ritas utan att korsa kanter. Således har grafen orienterbart genus 1.

Petersen-grafen kan också ritas (med skärningar) på planet på ett sådant sätt att alla kanter har samma längd. Sålunda är grafen en enhetsdistansgraf .

Den enklaste icke-orienterbara ytan i vilken Petersen-grafen kan bäddas in utan skärningspunkter är det projektiva planet . Detta är en inbäddning som ges genom att konstruera Petersen-grafen som en semi-dodekaeder . En inbäddning i det projektiva planet kan också bildas från Petersens pentagonala standardritning genom att placera en film (en skuren Klein-flaska) inuti den femkantiga stjärnan i mitten av ritningen och rikta stjärnans kanter genom denna film. Det resulterande mönstret har sex femkantiga ytor. Denna konstruktion bildar en vanlig karta och visar att Petersen-grafen har icke-orienterbart släkte 1.

Symmetrier

Petersen-grafen är starkt regelbunden (med signatur srg(10,3,0,1)). Grafen är också symmetrisk , vilket betyder att den är kanttransitiv och vertextransitiv . Mer strikt, grafen är 3-bågar-transitiv - vilken riktad väg som helst av de tre banorna i Petersen-grafen kan mappas till vilken annan sådan väg som helst genom grafsymmetri [4] . Grafen är en av 13 kubikavstånd -reguljära grafer . [5]

Automorfismgruppen i Petersen-grafen är den symmetriska gruppen . Handlingen på Petersen-grafen följer av dess konstruktion som en Kneser-graf . Varje homeomorfism av Petersen-grafen på sig själv som inte identifierar intilliggande hörn är en automorfism. Som visas i illustrationerna kan ritningar av Petersen-grafen visa symmetrier i fem riktningar eller i tre riktningar, men det är inte möjligt att rita en Petersen-graf på planet på ett sådant sätt att ritningen visar fullständig symmetri av grafgruppen.

Trots sin höga symmetri är Petersen-grafen inte en Cayley-graf , det är den minsta vertextransitiva grafen som inte är en Cayley-graf. [6]

Hamiltonska stigar och cykler

Petersen-grafen har en Hamiltonsk bana men inte en Hamiltonsk cykel . En graf är den minsta icke-överbryggade kubiska grafen som inte har en Hamiltonsk cykel. Grafen är hypo -Hamiltonsk, vilket betyder att även om den inte har en Hamiltonsk cykel, blir den Hamiltonsk om man tar bort någon vertex, och det är den minsta hypo-Hamiltonska grafen.

Som en finit sammankopplad vertextransitiv graf utan Hamiltonsk cykel är Petersen-grafen ett motexempel på en variant av Lovas-förmodan , men den kanoniska formuleringen av gissningen kräver en Hamiltonsk väg, och för Petersen-grafen gäller denna gissning.

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

För att visa att Petersen-grafen inte har en Hamiltonsk cykel C , överväg kanterna som förbinder den inre 5-vertexcykeln med den yttre cykeln. Om det finns en Hamiltonsk cykel måste ett jämnt antal av dessa kanter väljas. Om endast två kanter väljs, måste deras ändpunkter ligga intill i båda cyklerna med 5 vertex, vilket inte är möjligt. Således måste 4 kanter väljas. Antag att den övre kanten inte är vald (alla andra fall är liknande på grund av symmetri). Av de 5 kanterna på den yttre cykeln måste de två översta kanterna inkluderas i den Hamiltonska cykeln, så de två sidokanterna ska inte inkluderas i cykeln, och då måste den nedre kanten inkluderas i cykeln. De två översta kanterna i den inre cykeln måste väljas, men då stänger de två kanterna en cykel som inte är komplett, så den kan inte ingå i en Hamiltonsk cykel. Alternativt kan vi överväga tio-vertex 3-reguljära grafer som har en Hamilton-cykel, och visa att ingen av dessa grafer är en Petersen-graf 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 med tio vertex C plus fem ackord. Om något ackord förbinder två hörn längs C på ett avstånd av två eller tre från varandra, så har grafen en 3-cykel eller en 4-cykel, och kan därför inte vara en Petersen-graf. Om två ackord förbinder motsatta hörn av en cykel C på ett avstånd av fyra längs C , finns det återigen en 4-cykel. Endast fallet för Möbius-stegen återstår , bildad genom att förena varje par av motsatta sidor med en korda, som återigen har en 4-cykel. Eftersom Petersen-grafens omkrets är fem kan den inte bildas på detta sätt och har därför ingen Hamiltonsk cykel.

Målarbok

Petersen-grafen har kromatiskt nummer 3, vilket betyder att grafens hörn kan färgas med tre färger, men inte med två, så att ingen kant förbinder två hörn av samma färg. Grafen har en föreskriven färgning av 3 färger enligt Brooks sats för föreskrivna färger. Petersen-grafen har kromatiskt index 4, vilket betyder att kantfärgning kräver fyra färger. Grafen är med andra ord inte summan av tre 1-faktorer , vilket Petersen själv visade [9] . För att bevisa detta måste fyra fall kontrolleras för att visa att det inte finns någon 3-färgning av kanter. Som en brolös sammankopplad kubisk graf med kromatiskt index fyra är Petersen-grafen en snark . Denna graf är den minsta möjliga snark. Han var den enda kända snarken under perioden 1898-1946. Snarksatsen , som anges i form av Tutt -förmodan (bevisad 2001 av Robertson, Sanders, Seymour och Thomas [10] ), säger att varje snark har en Petersen-graf som moll .

Dessutom har grafen ett kromatiskt bråkindex på 3, vilket stöder påståendet att skillnaden mellan det kromatiska indexet och det kromatiska bråkindexet kan vara 1. Den långvariga Goldberg-Seymour-förmodan antyder att detta är den största möjliga skillnaden.

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 symmetrier. Det vill säga det karakteristiska färgtalet för grafen är lika med tre. Med undantag för kompletta grafer finns det bara en Kneser-graf vars karakteristiska nummer inte är lika med två [11] .

Andra egenskaper

Greve Petersen:

• är 3-ansluten, och därför 3-kant-ansluten och brygglös. Se kopplad graf .
• har ett självständighetstal på 4 och är 3-delad. Se Independent set problem .
• är en kubikgraf , har ett dominanstal på 3, har en perfekt matchning och en 2-faktor .
• har 6 distinkta perfekta matchningar.
• är den minsta kubiska grafen med omkrets 5. (Det är den enda - en cell . Grafen har bara 10 hörn, så det är den enda - en Moore-graf .) [12] .
• har radie 2 och diameter 2. Detta är den största kubiska grafen med diameter 2 [13]
• har grafspektrumet −2, −2, −2, −2, 1, 1, 1, 1, 1, 3.
• har 2000 spännande träd , mer än någon kubikgraf med 10 hörn [14]
• har ett kromatiskt polynom [15]
• har ett karakteristiskt polynom , vilket gör det till en heltalsgraf  — en graf vars spektrum helt består av heltal.
• Mellan två valfria hörn finns en unik väg med längd högst två.

Petersens färgläggningsgissning

Enligt Devos, Nexetril och Raspo, " Cykeln för en graf G är en uppsättning C E(G) så att varje vertex på grafen (V(G),C) har en jämn grad. Om G, H är grafer, definierar vi en avbildning φ: E(G) -> E(H) som cykelkontinuerlig om förbilden av någon cykel i H är en cykel i G. François Jaeger formulerade en gissning som säger att varje brolös graf har en cykelkontinuerlig karta till Petersen-grafen. Jaguer visade att om gissningen är sann, så är den dubbla täckande gissningen med cykler av längd 5 och Berge-Fulkerson-förmodan också sanna. [16] .

Relaterade grafer

Den generaliserade Petersen-grafen G ( n , k ) bildas genom att förbinda hörnen på en regelbunden n -gon med motsvarande hörn i en stjärnpolygon med Schläfli-symbolen { n / k } [17] [18] . Till exempel, i dessa notationer, betecknas Petersen-grafen som G (5,2) - den kan bildas genom att ansluta motsvarande hörn av en femkant och en femkantig stjärna, medan stjärnans hörn är sammankopplade genom en. Generaliserade Petersen-grafer inkluderar även n -prismor G ( n ,1), Dürer-graf G (6,2), Möbius-Cantor-graf G (8,3), dodekaedergraf G (10,2), Desargues-graf G (10, 3) och greve Nauru G (12,5).

Petersen-familjen av grafer består av sju grafer som kan bildas från en Petersen-graf genom att tillämpa noll eller fler transformationer Δ-Y eller Y-Δ . Den kompletta grafen K 6 tillhör också familjen Petersen. Dessa grafer bildar förbjudna mindreåriga för länkfria 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 [19]

Clebsch-grafen består av kopior av Petersen-grafen som genererade subgrafer  — för varje vertex v i Clebsch-grafen, genererar tio icke-grannehörn v en kopia av Petersen-grafen.

Anteckningar

1. ↑ Petersen-grafen .
2. ↑ Kempe, 1886 .
3. ↑ Knuth, 2011 .
4. ↑ Babai, 1995 , sid. 1447–1540.
5. ↑ Enligt fosterlistan .
6. ↑ Som sagt, detta förutsätter att Cayley-graferna inte nödvändigtvis hänger ihop. Vissa källor kräver att Cayley-grafer kopplas ihop, vilket gör den tomma grafen med två vertex till den minsta vertextransitiva grafen som inte är en Cayley-graf. Enligt definitionen i dessa källor är en Petersen-graf den minsta sammankopplade vertextransitiva grafen som inte är en Cayley-graf.
7. ↑ Royle, G. "Cubic Symmetric Graphs (The Foster Census)." Arkiverad från originalet den 20 juli 2008.
8. ↑ Holton, Sheehan, 1993 , sid. 32.
9. ↑ Harari, 2003 , sid. 113.
10. ↑ Pegg, 2002 , sid. 1084–1086.
11. ↑ Albertson, Boutin, 2007 , sid. 20 kr.
12. ↑ Hoffman, Singleton, 1960 , sid. 497–504.
13. ↑ Detta följer av det faktum att grafen är en Moore-graf, eftersom Moore-grafen är den största möjliga reguljära grafen med den graden av hörn och diameter ( Hoffman, Singleton 1960 ).
14. ↑ Jakobson, Rivin, 1999 ; Valdes, 1991 . Kubikgrafer med 6 och 8 hörn på vilka antalet spännande träd maximeras är Möbius-stegar .
15. ↑ Biggs, 1993 .
16. ↑ DeVos, Nešetřil, Raspaud, 2007 , sid. 109–138.
17. ↑ Coxeter, 1950 .
18. ↑ Watkins, 1969 .
19. ↑ Bailey, 1997 , sid. 187.

Litteratur

• F. Harari. Grafteori. - M .: URSS , 2003. - ISBN 5-354-00301-6 .
• O. Malm . Grafteori. — M .: URSS , 2008. — ISBN 978-5-397-00044-4 .
• Ed Pegg, Jr. Bokrecension: The Colossal Book of Mathematics  //  Notices of the American Mathematical Society. - 2002. - Vol. 49 , iss. 9 . - doi : 10.1109/TED.2002.1003756 . - .
• Rosemary A. Bailey. Undersökningar i kombinatorik. - Cambridge University Press, 1997. - ISBN 978-0-521-59840-8 .
• Matt DeVos, Jaroslav Nešetřil, André Raspaud. På kantkartor vars invers bevarar flöden eller spänningar // Grafteori i Paris. - Basel: Birkhäuser, 2007. - S. 109-138. - (Trender Math.). - doi : 10.1007/978-3-7643-7400-6_10 .
• Norman Biggs. Algebraisk grafteori. — 2:a. - Cambridge: Cambridge University Press, 1993. - ISBN 0-521-45897-8 .
• Laszlo Babai. Automorfismgrupper, isomorfism, rekonstruktion // Handbook of Combinatorics / Ronald L. Graham, Martin Grötschel, László Lovász. - North-Holland, 1995. - T. I. Arkiverad 11 juni 2010 på Wayback Machine
• Alan J. Hoffman, Robert R. Singleton. Moore grafer med diameter 2 och 3  // IBM Journal of Research and Development. - 1960. - V. 5 , nr. 4 . - S. 497-504 . - doi : 10.1147/rd.45.0497 .
• Michael O. Albertson, Debra L. Boutin. Använda bestämningsuppsättningar för att särskilja Kneser-grafer  // Electronic Journal of Combinatorics. - 2007. - T. 14 , nr. 1 .
• Geoffrey Exoo, Frank Harary, Frank Harary. Korsningsnumren för några generaliserade Petersen-grafer // Mathematica Scandinavica. - 1981. - T. 48 . - S. 184-188 .
• HSM Coxeter. Självdubbla konfigurationer och vanliga grafer  // Bulletin of the American Mathematical Society  . - 1950. - Vol. 56 , iss. 5 . - s. 413-455 . - doi : 10.1090/S0002-9904-1950-09407-5 .
• D.A. Holton, J. Sheehan. Petersen-grafen . - Cambridge University Press , 1993. - ISBN 0-521-43594-3 . - doi : 10.2277/0521435943 . Arkiverad 8 februari 2008 på Wayback Machine
• Dmitry Jakobson, Igor Rivin. Om några extrema problem inom grafteorin. - 1999. - arXiv : math.CO/9907050 .
• AB Kempe. En memoar om teorin om matematisk form // Philosophical Transactions of the Royal Society of London. - 1886. - T. 177 . - S. 1-70 . - doi : 10.1098/rstl.1886.0002 .
• Laszlo Lovasz . Kombinatoriska problem och övningar. — 2:a. - North-Holland, 1993. - ISBN 0-444-81504-X .
• Julius Peterson. Sur le théorème de Tait // L'Intermédiaire des Mathematiciens. - 1898. - T. 5 . - S. 225-227 .
• AJ Schwenk. Uppräkning av Hamiltons cykler i vissa generaliserade Petersen-grafer // Journal of Combinatorial Theory . - 1989. - T. 47 , nr. 1 . - S. 53-59 . - doi : 10.1016/0095-8956(89)90064-6 .
• L. Valdes. Extrema egenskaper hos spännande träd i kubiska grafer // Congressus Numerantium. - 1991. - T. 85 . - S. 143-160 .
• Mark E. Watkins. A Theorem on Tait Colorings with a Application to the Generalized Petersen Graphs // Journal of Combinatorial Theory . - 1969. - T. 6 , nr. 2 . - S. 152-164 . - doi : 10.1016/S0021-9800(69)80116-X .
• Donald E. Knuth . Ett utkast till avsnitt 7: Introduktion till kombinatoriskt sökning // The Art of Computer Programming . - V. 4, förfas 0A.
  • Donald E. Knuth . Combinatorial Algorithms, Del 1. - Upper Saddle River, New Jersey: Addison-Wesley, 2011. - ISBN 0-201-03804-8 .
  • Donald E. Knuth . Kapitel 7: Kombinatorisk sökning // Konsten att programmera. — Moskva, St. Petersburg, Kiev: I.D. Williams, 2013. - V. 4, A / Combinatorial Algorithms, Part 1. - ISBN 978-5-8459-1744-7 BBC 32.973.26-18.2.75.

Länkar

• Keller, Mitch. Kneser-grafer Arkiverade 5 maj 2018 på Wayback Machine PlanetMath
• Weisstein, Eric W. Petersen Graph  (engelska) på Wolfram MathWorld- webbplatsen .
• Petersen Graph på Encyclopedia of Integer Sequences