Fariho věta o narovnání grafu

Fareyův teorém  je graf-teoretické tvrzení o možnosti narovnání hran libovolného rovinného grafu . Jinými slovy, povolení kreslit hrany ne jako segmenty, ale jako křivky, nerozšiřuje třídu rovinných grafů.

Pojmenováno po maďarském matematikovi Istvánu Fárym [1] , i když to nezávisle na sobě dokázali Klaus Wagner v roce 1936 [2] a Stein v roce 1951 [3] .

Prohlášení: každý jednoduchý rovinný graf má rovinnou reprezentaci, ve které jsou všechny hrany reprezentovány jako úsečky .

Důkaz

Jedním ze způsobů, jak dokázat Fariho větu, je použití matematické indukce [4] . Nechť G  je jednoduchý rovinný graf s n vrcholy. Graf můžeme považovat za maximálně rovinný, v případě potřeby můžeme do původního grafu G přidat hrany . Všechny plochy G v tomto případě musí být trojúhelníky, protože ke každé ploše s více stranami můžeme přidat hranu, aniž bychom narušili rovinnost grafu, což je v rozporu s konvencí maximalizace grafu. Vybereme nějaké tři vrcholy a , b , c , tvořící trojúhelníkovou plochu grafu G . Indukcí na n dokážeme , že existuje další kombinatoricky izomorfní vložení s přímými hranami grafu G , ve kterém trojúhelník abc je vnější strana vložení. ( Kombinatorický izomorfismus znamená, že vrcholy, hrany a plochy nového výkresu mohou být vytvořeny tak, aby odpovídaly prvkům starého výkresu, přičemž jsou zachovány všechny vztahy výskytu mezi hranami, vrcholy a plochami, nejen mezi vrcholy a hranami. ) Báze indukce je triviální, když a , b a c jsou jediné vrcholy v G ( n =3 ).

Podle Eulerova vzorce pro rovinné grafy má graf G 3n − 6 hran . Ekvivalentně, definujeme- li deficit vrcholu v v G jako 6 − stupňů ( v ) , součet deficitů je 12 . Každý vrchol v G může mít deficit maximálně tři, takže existují alespoň čtyři vrcholy s kladným deficitem. Konkrétně můžeme zvolit vrchol v s nejvýše pěti sousedy, který je odlišný od a , b a c . Nechť G' vznikne odstraněním vrcholu v z grafu G a triangulací plochy f získané po odstranění vrcholu v . Indukcí má graf G' kombinatoricky izomorfní vložení rovné hrany, ve které abc je vnější plocha. Protože výsledné vložení G bylo kombinatoricky izomorfní s G' , odstraněním hran, které byly přidány k získání grafu G', zůstane plocha f , která je nyní polygonem P s nejvýše pěti stranami. Pro získání výkresu G s kombinatoricky izomorfním vnořením s rovnými hranami je třeba k mnohoúhelníku přidat vrchol v a spojit jej segmenty s vrcholy mnohoúhelníku. Podle věty o galerii obrázků je uvnitř P bod, kam lze umístit vrchol v , takže hrany spojující vrchol v s vrcholy mnohoúhelníku P neprotínají další hrany mnohoúhelníku, čímž je důkaz dokončen.

Indukční krok důkazu je znázorněn vpravo.

Související výsledky

De Freysix, Pach a Polak ukázali, jak najít v lineárním čase vzor s rovnými hranami na mřížce s rozměry lineárně závislými na velikosti grafu, což dává univerzální množinu bodů s kvadratickými rozměry. Podobnou metodu použil Schneider k prokázání zlepšených hranic a charakterizace rovinnosti , kde se spoléhal na částečné pořadí výskytu. Jeho práce zdůrazňuje existenci určitého rozdělení hran maximálního rovinného grafu do tří stromů, které je známé jako Schneiderův les .

Tuttův teorém o „gumovém balení“ říká, že jakýkoli trojsouvislý rovinný graf lze nakreslit na rovinu bez průniků tak, že jeho hrany jsou úsečky a jeho vnější plocha je konvexní mnohoúhelník [5] . Název odráží skutečnost, že takové vnoření lze nalézt jako rovnovážný bod pro systém pružin reprezentujících okraje grafu.

Steinitzova věta říká, že jakýkoli 3-souvislý rovinný graf může být reprezentován jako hrany konvexního mnohostěnu v trojrozměrném prostoru. Vložení s rovnými hranami grafu lze získat jako projekci takového mnohostěnu do roviny.

Věta o balení kruhu říká, že jakýkoli rovinný graf může být reprezentován jako graf průsečíku množiny disjunktních kružnic v rovině. Umístíme-li každý vrchol grafu do středu odpovídajícího kruhu, dostaneme znázornění grafu s rovnými hranami.

Nevyřešené problémy v matematice : Má nějaký rovinný graf zobrazení s přímými hranami, ve kterých jsou délky všech hran celá čísla?

Haiwo Harbort položil otázku, zda pro jakýkoli rovinný graf existuje zobrazení s přímými hranami, ve kterých jsou všechny délky hran celá čísla [6] . Je Harbortova hypotéza správná?, zůstává otevřenou otázkou (k roku 2014). Je však známo, že pro kubické grafyexistuje vložení s celočíselnými přímými hranami[7].

Sachs [8] položil otázku, zda jakýkoli graf s nepropojeným vnořením do trojrozměrného euklidovského prostoru má nepropojené vnoření, ve kterém jsou všechny hrany reprezentovány úsečkami, analogicky s Fareyho teorémem pro dvourozměrná vložení.

Viz také

Poznámky

  1. ↑ Fáry, 1948 , s. 229–233.
  2. ↑ Wagner, 1936 .
  3. ↑ Stein, 1951 .
  4. ↑ Výše ​​uvedený důkaz lze nalézt v knize V. V. Prasolova. Základy kombinatorické a diferenciální topologie. M.: MTsNMO, 2004.
  5. ↑ Tutte, 1963 , str. 743–767.
  6. ↑ Harborth, Kemnitz, Moller, Sussenbach, 1987 ; Kemnitz, Harborth, 2001 ; Mohar, Thomassen, 2001 .
  7. ↑ Geelen, Guo, McKinnon, 2008 .
  8. ↑ Sachs, 1983 .

Literatura