Faris grafretningssætning

Fareys sætning  er et grafteoretisk udsagn om muligheden for at rette kanterne af enhver plan graf . Med andre ord, tilladelsen til at tegne kanter ikke som segmenter, men som kurver, udvider ikke klassen af ​​plane grafer.

Opkaldt efter den ungarske matematiker István Fáry [1] , selvom det blev bevist uafhængigt af Klaus Wagner i 1936 [2] og Stein i 1951 [3] .

Udsagn: enhver simpel plan graf har en plan repræsentation, hvor alle kanter er repræsenteret som linjestykker .

Bevis

En af måderne at bevise Fari-sætningen på er brugen af ​​matematisk induktion [4] . Lad G  være en simpel plan graf med n toppunkter. Vi kan betragte grafen som maksimal plan, om nødvendigt kan vi tilføje kanter til den originale graf G . Alle flader af G skal i dette tilfælde være trekanter, da vi kan tilføje en kant til enhver flade med flere sider uden at bryde grafens planaritet, hvilket er i modstrid med grafens maksimalitetskonvention. Vi vælger nogle tre hjørner a , b , c , der danner en trekantet flade af grafen G . Vi vil bevise ved induktion på n , at der eksisterer en anden kombinatorisk isomorf indlejring med direkte kanter af grafen G , hvor trekanten abc er den ydre flade af indlejringen. ( Kombinatorisk isomorfi betyder, at toppunkterne, kanterne og fladerne på den nye tegning kan fås til at svare til elementerne i den gamle tegning, mens alle indfaldsrelationer mellem kanter, hjørner og flader bevares, ikke kun mellem hjørner og kanter. ) Grundlaget for induktionen er trivielt, når a , b og c er de eneste hjørner i G ( n =3 ).

Ved Euler-formlen for plane grafer har grafen G 3n − 6 kanter . Tilsvarende, hvis vi definerer underskuddet af et toppunkt v i G som 6 − grader ( v ) , er summen af ​​underskuddene 12 . Hvert toppunkt i G kan have et underskud på højst tre, så der er mindst fire hjørner med et positivt underskud. Især kan vi vælge et toppunkt v med højst fem naboer, der er forskelligt fra a , b og c . Lad G' dannes ved at fjerne toppunktet v fra grafen G og triangulere ansigtet f opnået efter at have fjernet toppunktet v . Ved induktion har grafen G' en kombinatorisk isomorf ligekant-indlejring, hvor abc er en ydre flade. Da den resulterende indlejring G var kombinatorisk isomorf til G' , efterlader man en flade f , som nu er en polygon P med højst fem sider , ved at slette de kanter, der blev tilføjet for at opnå grafen G' . For at opnå en tegning G med en kombinatorisk isomorf indlejring med lige kanter, skal toppunktet v tilføjes til polygonen og forbindes med segmenter til polygonens toppunkter. Ved billedgallerisætningen er der et punkt inde i P , hvor et toppunkt v kan placeres , således at de kanter, der forbinder toppunktet v med polygonens P toppunkter , ikke skærer andre kanter af polygonen, hvilket fuldender beviset.

Bevisets induktionstrin er illustreret til højre.

Relaterede resultater

De Freysix, Pach og Polak viste, hvordan man i lineær tid finder et mønster med lige kanter på et gitter med dimensioner lineært afhængige af grafens størrelse, hvilket giver et universelt sæt punkter med kvadratiske dimensioner. En lignende metode blev brugt af Schneider til at bevise forbedrede grænser og planaritetskarakterisering , hvor han stolede på en partiel incidensrækkefølge. Hans arbejde understreger eksistensen af ​​en vis opdeling af kanterne af en maksimal plan graf i tre træer, som er kendt som Schneider-skoven .

Tutts "gummipakning" -sætning siger, at enhver tre-forbundet plan graf kan tegnes på planet uden skæringspunkter, så dens kanter er linjestykker og dens ydre flade er en konveks polygon [5] . Navnet afspejler det faktum, at en sådan indlejring kan findes som et ligevægtspunkt for et system af fjedre, der repræsenterer grafens kanter.

Steinitzs teorem siger, at enhver 3-forbundet plan graf kan repræsenteres som kanterne af et konveks polyeder i tredimensionelt rum. En indlejring med lige kanter af en graf kan opnås som en projektion af et sådant polyeder på et plan.

Cirkelpakningssætningen siger, at enhver plan graf kan repræsenteres som skæringsgrafen for et sæt usammenhængende cirkler i planet. Hvis vi placerer hvert hjørne af grafen i midten af ​​den tilsvarende cirkel, får vi en repræsentation af grafen med lige kanter.

Uløste problemer i matematik : Har nogen plan graf en repræsentation med direkte kanter, hvor længderne af alle kanter er heltal?

Haiwo Harbort rejste spørgsmålet, om der for nogen plan graf eksisterer en repræsentation med direkte kanter, hvor alle kantlængder er heltal [6] . Er Harborts hypotese korrekt?, forbliver et åbent spørgsmål (fra 2014). Det er dog kendt, at der eksisterer en indlejring med heltals direkte kanter forkubiske grafer[7].

Sachs [8] rejste spørgsmålet om, hvorvidt en graf med en ikke-forbundet indlejring i tredimensionelt euklidisk rum har en ikke-forbundet indlejring, hvor alle kanter er repræsenteret af linjestykker, analogt med Farey-sætningen for to-dimensionelle indlejringer.

Se også

Noter

  1. ↑ Fáry, 1948 , s. 229-233.
  2. ↑ Wagner, 1936 .
  3. ↑ Stein, 1951 .
  4. ↑ Ovenstående bevis kan findes i bogen af ​​V. V. Prasolov. Elementer af kombinatorisk og differentiel topologi. M.: MTsNMO, 2004.
  5. ↑ Tutte, 1963 , s. 743-767.
  6. ↑ Harborth, Kemnitz, Møller, Sussenbach, 1987 ; Kemnitz, Harborth, 2001 ; Mohar, Thomassen, 2001 .
  7. ↑ Geelen, Guo, McKinnon, 2008 .
  8. ↑ Sachs, 1983 .

Litteratur