Fárysova věta - Fárys theorem - Wikipedia

Pro další použití viz Fary-Milnorova věta.

V matematice Fáryho věta uvádí, že jakýkoli jednoduchý rovinný graf může být tažené bez křížení, aby jeho hrany byly rovné úsečky. To znamená, že schopnost kreslit hrany grafu jako křivky namísto přímých segmentů neumožňuje vykreslení větší třídy grafů. Věta je pojmenována po István Fáry, ačkoli to nezávisle prokázal Klaus Wagner  (1936 ), Fáry  (1948 ), a Sherman K. Stein  (1951 ).

Důkaz

Indukční krok pro důkaz Fáryho věty.

Jedním ze způsobů prokázání Fáryho věty je použití matematická indukce.[1] Nechat G být jednoduchý rovinný graf s n vrcholy; v případě potřeby můžeme přidat hrany G je graf maximálně rovinný. Li n <3, výsledek je triviální. Li n ≥ 3, pak všechny tváře G musí to být trojúhelníky, protože bychom mohli přidat hranu do jakékoli tváře s více stranami při zachování rovinnosti, což je v rozporu s předpokladem maximální rovinnosti. Vyberte několik tří vrcholů A, b, C tvořící trojúhelníkový obličej G. Dokazujeme indukcí dne n že existuje lineární kombinatoricky izomorfní opětovné vložení G ve kterém trojúhelníku abc je vnější plocha vložení. (Kombinatoricky izomorfní znamená, že vrcholy, hrany a plochy v novém výkresu lze přizpůsobit těm ve starém výkresu, takže budou zachovány všechny výskyty mezi hranami, vrcholy a plochami - nejen mezi vrcholy a hranami.) Jako v základním případě je výsledek triviální, když n = 3 a A, b a C jsou jediné vrcholy v G. Můžeme to tedy předpokládat n ≥ 4.

Podle Eulerův vzorec pro rovinné grafy, G má 3n − 6 hrany; ekvivalentně, pokud někdo definuje nedostatek vrcholu proti v G být 6 − deg (proti), součet nedostatků je 12. Od té doby G má alespoň čtyři vrcholy a všechny tváře G jsou trojúhelníky, z toho vyplývá, že každý vrchol v G má titul alespoň tři. Proto každý vrchol v G má nedostatek nejvýše tři, takže existují nejméně čtyři vrcholy s pozitivním nedostatkem. Zejména si můžeme vybrat vrchol proti s nejvýše pěti sousedy, které se liší od A, b a C. Nechat G' být vytvořen odstraněním proti z G a retriangulace obličeje F vytvořen odstraněním proti. Indukcí, G' má kombinatoricky izomorfní lineární opětovné vložení do abc je vnější obličej. Protože opětovné vložení G' byl kombinatoricky izomorfní s G', odstranění hran, které byly přidány k vytvoření G' opouští tvář F, což je nyní mnohoúhelník P s maximálně pěti stranami. Chcete-li dokončit kresbu na přímočarou kombinatoricky izomorfní opětovné vložení G, proti by měly být umístěny v mnohoúhelníku a spojeny přímkami s vrcholy mnohoúhelníku. Podle věta o umělecké galerii, existuje bod uvnitř P na kterém proti lze umístit tak, aby hrany od proti k vrcholům P nepřekračujte žádné další hrany, dokončete důkaz.

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

Související výsledky

De Fraysseix, Pach a Pollack ukázali, jak v lineárním čase najít přímkový výkres v mřížce s kótami lineárními ve velikosti grafu, což dává univerzální bodová sada s kvadratickou velikostí. Podobnou metodu následoval Schnyder, aby dokázal zvýšené hranice a charakterizace rovinnosti na základě výskytu dílčího pořadí. Jeho práce zdůraznila existenci zvláštního rozdělení okrajů maximálního rovinného grafu do tří stromů známých jako a Schnyderovo dřevo.

Tutteova jarní věta uvádí, že každý 3 propojený rovinný graf lze nakreslit na rovinu bez křížení, takže jeho hrany jsou úsečky a vnější plocha je konvexní mnohoúhelník (Tutte 1963). Jmenuje se to proto, že takové zanoření lze nalézt jako rovnovážnou pozici pro systém pružiny představující okraje grafu.

Steinitzova věta uvádí, že každý 3-spojený planární graf může být reprezentován jako okraje konvexního mnohostěnu v trojrozměrném prostoru. Přímé vložení typu popsaného Tuttovou větou, může být vytvořeno promítnutím takové polyhedrální reprezentace na rovinu.

The Věta o kruhovém balení uvádí, že každý rovinný graf může být reprezentován jako průsečíkový graf sbírky nepřekračujících se kruhů v letadle. Umístěním každého vrcholu grafu do středu příslušného kruhu dojde k přímkové reprezentaci.

Question, Web Fundamentals.svgNevyřešený problém v matematice:
Má každý rovinný graf přímou reprezentaci, ve které jsou všechny délky hran celá čísla?
(více nevyřešených úloh z matematiky)

Heiko Harborth nastolila otázku, zda má každý rovinný graf přímkovou reprezentaci, ve které jsou všechny délky hran celá čísla.[2] Pravda Harborthova domněnka zůstává neznámý od roku 2014. Je však známo, že pro vložení přímých čar na celou vzdálenost existují kubické grafy.[3]

Sachs (1983) nastolila otázku, zda každý graf s a vkládání bez odkazů v trojrozměrném Euklidovský prostor má vložení bez odkazů, ve kterém jsou všechny hrany reprezentovány přímými segmenty, analogicky k Fáryho teorému pro dvourozměrné vložení.

Viz také

Poznámky

  1. ^ Důkazy, které následují, najdete v Chartrand, Gary; Lesniak, Linda; Zhang, Ping (2010), Grafy a digrafy (5. vydání), CRC Press, str. 259–260, ISBN  9781439826270.
  2. ^ Harborth a kol. (1987); Kemnitz & Harborth (2001); Mohar & Thomassen (2001); Mohar (2003).
  3. ^ Geelen, Guo a McKinnon (2008).

Reference