Faris grafriktningssats

Fareys teorem  är ett grafteoretiskt uttalande om möjligheten att räta ut kanterna på vilken plan graf som helst . Med andra ord, tillåtelsen att rita kanter inte som segment, utan som kurvor, utökar inte klassen av plana grafer.

Uppkallad efter den ungerske matematikern István Fáry [1] , även om det bevisades oberoende av Klaus Wagner 1936 [2] och Stein 1951 [3] .

Påstående: varje enkel plan graf har en plan representation där alla kanter representeras som linjesegment .

Bevis

Ett av sätten att bevisa Fari-satsen är användningen av matematisk induktion [4] . Låt G  vara en enkel plan graf med n hörn. Vi kan betrakta grafen som maximal plan, om nödvändigt kan vi lägga till kanter till den ursprungliga grafen G . Alla ytor av G i detta fall måste vara trianglar, eftersom vi kan lägga till en kant på vilken yta som helst med fler sidor utan att bryta grafens planhet, vilket motsäger grafens maximalitetskonvention. Vi väljer några tre hörn a , b , c , som bildar en triangulär yta på grafen G . Vi kommer att bevisa genom induktion på n att det finns en annan kombinatoriskt isomorf inbäddning med direkta kanter på grafen G där triangeln abc är den yttre ytan av inbäddningen. ( Kombinatorisk isomorfism innebär att hörn, kanter och ytor på den nya ritningen kan göras för att motsvara elementen i den gamla ritningen, samtidigt som alla infallsrelationer mellan kanter, hörn och ytor bevaras, inte bara mellan hörn och kanter. ) Induktionens bas är trivial när a , b och c är de enda hörnen i G ( n =3 ).

Enligt Euler-formeln för plana grafer har grafen G 3n − 6 kanter . På motsvarande sätt, om vi definierar underskottet för en vertex v i G som 6 − grader ( v ) , är summan av underskotten 12 . Varje hörn i G kan ha ett underskott på högst tre, så det finns minst fyra hörn med ett positivt underskott. I synnerhet kan vi välja en vertex v med högst fem grannar som skiljer sig från a , b och c . Låt G' bildas genom att ta bort vertex v från grafen G och triangulera ytan f som erhålls efter att ha tagit bort vertex v . Genom induktion har grafen G' en kombinatoriskt isomorf inbäddning med rak kant i vilken abc är en yttre yta. Eftersom den resulterande inbäddningen G var kombinatoriskt isomorf till G' lämnar man bort från den kanterna som lades till för att erhålla grafen G' en yta f , som nu är en polygon P med högst fem sidor. För att få en ritning G med en kombinatoriskt isomorf inbäddning med raka kanter måste vertex v adderas till polygonen och kopplas med segment till polygonens hörn. Vid bildgallerisatsen finns det en punkt inuti P där en vertex v kan placeras , så att kanterna som förbinder vertex v med spetsarna på polygonen P inte skär andra kanter av polygonen, vilket fullbordar beviset.

Induktionssteget för beviset illustreras till höger.

Relaterade resultat

De Freysix, Pach och Polak visade hur man i linjär tid kan hitta ett mönster med raka kanter på ett gitter med dimensioner linjärt beroende på storleken på grafen, vilket ger en universell uppsättning punkter med kvadratiska dimensioner. En liknande metod användes av Schneider för att bevisa förbättrad karakterisering av gränser och planaritet , där han förlitade sig på en partiell incidensordning. Hans arbete betonar förekomsten av en viss uppdelning av kanterna på en maximal plan graf i tre träd, som är känd som Schneider-skogen .

Tutts "gummipackning" -sats säger att vilken trekopplad plan graf som helst kan ritas på planet utan skärningar så att dess kanter är linjesegment och dess yttre yta är en konvex polygon [5] . Namnet återspeglar det faktum att en sådan inbäddning kan hittas som en jämviktspunkt för ett system av fjädrar som representerar grafens kanter.

Steinitz sats säger att vilken 3-kopplad plan graf som helst kan representeras som kanterna på en konvex polyeder i tredimensionellt rymd. En inbäddning med raka kanter av en graf kan erhållas som en projektion av en sådan polyeder på ett plan.

Cirkelpackningssatsen säger att vilken plan graf som helst kan representeras som skärningsgrafen för en uppsättning osammanhängande cirklar i planet. Om vi ​​placerar varje hörn av grafen i mitten av motsvarande cirkel får vi en representation av grafen med raka kanter.

Olösta problem i matematik : Har någon plan graf en representation med direkta kanter där längden på alla kanter är heltal?

Haiwo Harbort ställde frågan om det för någon plan graf finns en representation med direkta kanter där alla kantlängder är heltal [6] . Stämmer Harborts hypotes?, är fortfarande en öppen fråga (från 2014). Det är dock känt att en inbäddning med heltals direkta kanter finns förkubiska grafer[7].

Sachs [8] ställde frågan om någon graf med en olänkad inbäddning i tredimensionell euklidisk rymd har en olänkad inbäddning där alla kanter representeras av linjesegment, i analogi med Farey-satsen för tvådimensionella inbäddningar.

Se även

Anteckningar

  1. ↑ Fáry, 1948 , sid. 229–233.
  2. ↑ Wagner, 1936 .
  3. ↑ Stein, 1951 .
  4. ↑ Ovanstående bevis finns i boken av V. V. Prasolov. Element av kombinatorisk och differentiell topologi. M.: MTsNMO, 2004.
  5. ↑ Tutte, 1963 , sid. 743–767.
  6. ↑ Harborth, Kemnitz, Möller, Sussenbach, 1987 ; Kemnitz, Harborth, 2001 ; Mohar, Thomassen, 2001 .
  7. ↑ Geelen, Guo, McKinnon, 2008 .
  8. ↑ Sachs, 1983 .

Litteratur