Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
Теоре́ма Фа́рі — теоретико-графове твердження про можливість випрямити ребра будь-якого планарного графа. Іншими словами, дозвіл малювати ребра не у вигляді відрізків, а у вигляді кривих, не розширює класу планарних графів.
Названа на честь угорського математика [de], хоча довели її незалежно [ru] 1936 і Штайн 1951 року.
Формулювання:
- будь-який простий планарний граф має плоске подання, в якому всі ребра зображено відрізками прямих.
Доведення
Один з способів доведення теореми Фарі — застосування математичної індукції. Нехай G — простий планарний граф із n вершинами. Ми можемо вважати граф максимальним планарним, за необхідності можна додати ребра в початковий граф G. Всі грані графа G в цьому випадку мають бути трикутниками, оскільки в будь-яку грань з більшим числом сторін можна додати ребро, не порушуючи планарності графа, що суперечить домовленості про максимальність графа. Виберемо деякі три вершини a, b, c, що утворюють трикутну грань графа G. Доведемо за індукцією за n, що існує комбінаторно ізоморфне інше вкладення з прямими ребрами графа G, в якому трикутник abc є зовнішньою гранню вкладення. (Комбінаторна ізоморфність означає, що вершини, ребра і грані нового малюнка можна зробити відповідними елементами старого малюнка і при цьому зберігаються всі відношення інцидентності між ребрами, вершинами і гранями, а не тільки між вершинами і ребрами.) База індукції тривіальна, коли a, b і c є єдиними вершинами в G (n=3).
За (формулою Ейлера) для планарних графів граф G має 3n − 6 ребер. Еквівалентно, якщо визначити дефіцит вершини v у графі G як 6 − deg(v), сума дефіцитів дорівнює12. Кожна вершина у графі G може мати дефіцит не більший від трьох, так що є щонайменше чотири вершини з додатним дефіцитом. Зокрема, ми можемо вибрати вершину v з не більше ніж п'ятьма сусідами, відмінну від a, b і c. Нехай G утворюється видаленням вершини v з графа G і тріангуляцією грані f, отриманої після видалення вершини v. За індукцією, граф G' має комбінаторно-ізоморфне вкладення з прямолінійними ребрами, в якому abc є зовнішньою гранню. Оскільки отримане вкладення G було комбінаторно ізоморфним G', видалення з нього ребер, доданих для отримання графа G', залишає грань f, яка тепер є многокутником P з не більше ніж п'ятьма сторонами. Для отримання малюнка G з комбінаторно-ізоморфним вкладенням із прямими ребрами, вершину v слід додати до многокутника і з'єднати відрізками з його вершинами. За теоремою галереї мистецтв всередині P існує точка, куди можна помістити вершину v, так що ребра, які з'єднують вершину v з вершинами многокутника P, не перетнуть інших ребер многокутника, що завершує доведення.
Крок індукції доведення проілюстровано праворуч.
Пов'язані результати
Де Фрейсікс, Пах і Полак показали, як знайти за лінійний час малюнок із прямолінійними ребрами на ґратці з розмірами, що лінійно залежать від розміру графа, даючи універсальну множину точок із квадратичними розмірами. Схожий метод використав Шнайдер для доведення покращених меж та характеристики планарності, де він ґрунтувався на частковому порядку інцидентності. Його робота наголошує на існуванні певного розбиття ребер максимального планарного графа на три дерева, які відомі як ліс Шнайдера.
Теорема Татта «про гумове укладання» стверджує, що будь-який тризв'язний планарний граф можна намалювати на площині без перетинів так, що його ребра будуть відрізками прямих і зовнішня грань буде опуклим многокутником. Назва відбиває той факт, що таке вкладення можна знайти як точку рівноваги системи пружин, які подають ребра графа.
Теорема Штайніца стверджує, що будь-який 3-зв'язний планарний граф можна подати як ребра опуклого многогранника в тривимірному просторі. Вкладення з прямими ребрами графа 
можна отримати як проєкцію такого многогранника на площину.
стверджує, що будь-який планарний граф можна подати як граф перетинів набору кіл, що не перетинаються, на площині. Якщо розмістити кожну вершину графа в центрі відповідного кола, отримаємо подання графа з прямолінійними ребрами.
Чи існує для будь-якого планарного графа подання з прямими ребрами, в якому довжини всіх ребер є цілими числами?
[en] порушив питання, чи існує для будь-якого планарного графа подання з прямими ребрами, в якому всі довжини ребер є цілими числами. Питання, чи істинна [en], залишається відкритим (Станом на 2014). Однак відомо, що вкладення з цілими прямими ребрами існує для кубічних графів.
Сакс порушив питання, чи має будь-який граф із незачепленим вкладенням у тривимірному евклідовому просторі незачеплене вкладення, в якому всі ребра подано відрізками за аналогією з теоремою Фарі для двовимірних вкладень.
Див. також
Примітки
- Fáry, 1948, с. 229–233.
- Wagner, 1936.
- Stein, 1951.
- Приведённое доказательство можно найти в книге В. В. Прасолов. Элементы комбинаторной и дифференциальной топологии. М.: МЦНМО, 2004.
- Tutte, 1963, с. 743–767.
- Harborth, Kemnitz, Moller, Sussenbach, 1987; Kemnitz, Harborth, 2001; Mohar, Thomassen, 2001.
- Geelen, Guo, McKinnon, 2008.
- Sachs, 1983.
Література
- István Fáry. On straight-line representation of planar graphs // Acta Sci. Math. (Szeged). — 1948. — Т. 11. — С. 229–233. — MR0026311.
- Gary Chartrand, Linda Lesniak, Ping Zhang. Graphs & Digraphs. — 5th. — CRC Press, 2010. — С. 259–260. — .
- Hubert de Fraysseix, János Pach, Richard Pollack. Small sets supporting Fary embeddings of planar graphs // Twentieth Annual ACM Symposium on Theory of Computing. — 1988. — С. 426–433. — . — DOI:
- Hubert de Fraysseix, János Pach, Richard Pollack. How to draw a planar graph on a grid // Combinatorica. — 1990. — Т. 10. — С. 41–51. — DOI:.
- Jim Geelen, Anjie Guo, David McKinnon. Straight line embeddings of cubic planar graphs with integer edge lengths // J. Graph Theory. — 2008. — Т. 58, вип. 3. — С. 270–274. — DOI:.
- Harborth H., Kemnitz A., Moller M., Sussenbach A. Ganzzahlige planare Darstellungen der platonischen Korper // Elem. Math.. — 1987. — Т. 42. — С. 118–122.
- Kemnitz A., Harborth H. Plane integral drawings of planar graphs // Discrete Math.. — 2001. — Т. 236. — С. 191–195. — DOI:.
- Bojan Mohar, Carsten Thomassen. Graphs on Surfaces. — Johns Hopkins University Press, 2001. — С. roblem 2.8.15. — .
- Horst Sachs. On a spatial analogue of Kuratowski's theorem on planar graphs — An open problem // Graph Theory: Proceedings of a Conference held in Łagów, Poland, February 10–13, 1981. — Springer-Verlag, 1983. — Т. 1018. — С. 230–241. — (Lecture Notes in Mathematics) — . — DOI:
- Walter Schnyder. Proc. 1st ACM/SIAM Symposium on Discrete Algorithms (SODA). — 1990. — С. 138–148.
- Stein S. K. Convex maps // . — 1951. — Т. 2, вип. 3. — С. 464–466. — DOI:.
- Tutte W. T. How to draw a graph // Proceedings of the London Mathematical Society. — 1963. — Т. 13. — С. 743–767. — DOI:.
- Klaus Wagner. Bemerkungen zum Vierfarbenproblem // Jahresbericht der Deutschen Mathematiker-Vereinigung. — 1936. — Т. 46. — С. 26–32.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Teore ma Fa ri teoretiko grafove tverdzhennya pro mozhlivist vipryamiti rebra bud yakogo planarnogo grafa Inshimi slovami dozvil malyuvati rebra ne u viglyadi vidrizkiv a u viglyadi krivih ne rozshiryuye klasu planarnih grafiv Nazvana na chest ugorskogo matematika de hocha doveli yiyi nezalezhno ru 1936 i Shtajn 1951 roku Formulyuvannya bud yakij prostij planarnij graf maye ploske podannya v yakomu vsi rebra zobrazheno vidrizkami pryamih DovedennyaKrok indukciyi Odin z sposobiv dovedennya teoremi Fari zastosuvannya matematichnoyi indukciyi Nehaj G prostij planarnij graf iz n vershinami Mi mozhemo vvazhati graf maksimalnim planarnim za neobhidnosti mozhna dodati rebra v pochatkovij graf G Vsi grani grafa G v comu vipadku mayut buti trikutnikami oskilki v bud yaku gran z bilshim chislom storin mozhna dodati rebro ne porushuyuchi planarnosti grafa sho superechit domovlenosti pro maksimalnist grafa Viberemo deyaki tri vershini a b c sho utvoryuyut trikutnu gran grafa G Dovedemo za indukciyeyu za n sho isnuye kombinatorno izomorfne inshe vkladennya z pryamimi rebrami grafa G v yakomu trikutnik abc ye zovnishnoyu grannyu vkladennya Kombinatorna izomorfnist oznachaye sho vershini rebra i grani novogo malyunka mozhna zrobiti vidpovidnimi elementami starogo malyunka i pri comu zberigayutsya vsi vidnoshennya incidentnosti mizh rebrami vershinami i granyami a ne tilki mizh vershinami i rebrami Baza indukciyi trivialna koli a b i c ye yedinimi vershinami v G n 3 Za formuloyu Ejlera dlya planarnih grafiv graf G maye 3n 6 reber Ekvivalentno yaksho viznachiti deficit vershini v u grafi G yak 6 deg v suma deficitiv dorivnyuye12 Kozhna vershina u grafi G mozhe mati deficit ne bilshij vid troh tak sho ye shonajmenshe chotiri vershini z dodatnim deficitom Zokrema mi mozhemo vibrati vershinu v z ne bilshe nizh p yatma susidami vidminnu vid a b i c Nehaj G utvoryuyetsya vidalennyam vershini v z grafa G i triangulyaciyeyu grani f otrimanoyi pislya vidalennya vershini v Za indukciyeyu graf G maye kombinatorno izomorfne vkladennya z pryamolinijnimi rebrami v yakomu abc ye zovnishnoyu grannyu Oskilki otrimane vkladennya G bulo kombinatorno izomorfnim G vidalennya z nogo reber dodanih dlya otrimannya grafa G zalishaye gran f yaka teper ye mnogokutnikom P z ne bilshe nizh p yatma storonami Dlya otrimannya malyunka G z kombinatorno izomorfnim vkladennyam iz pryamimi rebrami vershinu v slid dodati do mnogokutnika i z yednati vidrizkami z jogo vershinami Za teoremoyu galereyi mistectv vseredini P isnuye tochka kudi mozhna pomistiti vershinu v tak sho rebra yaki z yednuyut vershinu v z vershinami mnogokutnika P ne peretnut inshih reber mnogokutnika sho zavershuye dovedennya Krok indukciyi dovedennya proilyustrovano pravoruch Pov yazani rezultatiDe Frejsiks Pah i Polak pokazali yak znajti za linijnij chas malyunok iz pryamolinijnimi rebrami na gratci z rozmirami sho linijno zalezhat vid rozmiru grafa dayuchi universalnu mnozhinu tochok iz kvadratichnimi rozmirami Shozhij metod vikoristav Shnajder dlya dovedennya pokrashenih mezh ta harakteristiki planarnosti de vin gruntuvavsya na chastkovomu poryadku incidentnosti Jogo robota nagoloshuye na isnuvanni pevnogo rozbittya reber maksimalnogo planarnogo grafa na tri dereva yaki vidomi yak lis Shnajdera Teorema Tatta pro gumove ukladannya stverdzhuye sho bud yakij trizv yaznij planarnij graf mozhna namalyuvati na ploshini bez peretiniv tak sho jogo rebra budut vidrizkami pryamih i zovnishnya gran bude opuklim mnogokutnikom Nazva vidbivaye toj fakt sho take vkladennya mozhna znajti yak tochku rivnovagi sistemi pruzhin yaki podayut rebra grafa Teorema Shtajnica stverdzhuye sho bud yakij 3 zv yaznij planarnij graf mozhna podati yak rebra opuklogo mnogogrannika v trivimirnomu prostori Vkladennya z pryamimi rebrami grafa G displaystyle G mozhna otrimati yak proyekciyu takogo mnogogrannika na ploshinu stverdzhuye sho bud yakij planarnij graf mozhna podati yak graf peretiniv naboru kil sho ne peretinayutsya na ploshini Yaksho rozmistiti kozhnu vershinu grafa v centri vidpovidnogo kola otrimayemo podannya grafa z pryamolinijnimi rebrami Nerozv yazana problema matematiki Chi isnuye dlya bud yakogo planarnogo grafa podannya z pryamimi rebrami v yakomu dovzhini vsih reber ye cilimi chislami en porushiv pitannya chi isnuye dlya bud yakogo planarnogo grafa podannya z pryamimi rebrami v yakomu vsi dovzhini reber ye cilimi chislami Pitannya chi istinna en zalishayetsya vidkritim Stanom na 2014 Odnak vidomo sho vkladennya z cilimi pryamimi rebrami isnuye dlya kubichnih grafiv Saks porushiv pitannya chi maye bud yakij graf iz nezacheplenim vkladennyam u trivimirnomu evklidovomu prostori nezacheplene vkladennya v yakomu vsi rebra podano vidrizkami za analogiyeyu z teoremoyu Fari dlya dvovimirnih vkladen Div takozhPrimitkiFary 1948 s 229 233 Wagner 1936 Stein 1951 Privedyonnoe dokazatelstvo mozhno najti v knige V V Prasolov Elementy kombinatornoj i differencialnoj topologii M MCNMO 2004 Tutte 1963 s 743 767 Harborth Kemnitz Moller Sussenbach 1987 Kemnitz Harborth 2001 Mohar Thomassen 2001 Geelen Guo McKinnon 2008 Sachs 1983 LiteraturaIstvan Fary On straight line representation of planar graphs Acta Sci Math Szeged 1948 T 11 S 229 233 MR0026311 Gary Chartrand Linda Lesniak Ping Zhang Graphs amp Digraphs 5th CRC Press 2010 S 259 260 ISBN 9781439826270 Hubert de Fraysseix Janos Pach Richard Pollack Small sets supporting Fary embeddings of planar graphs Twentieth Annual ACM Symposium on Theory of Computing 1988 S 426 433 ISBN 0 89791 264 0 DOI 10 1145 62212 62254 Hubert de Fraysseix Janos Pach Richard Pollack How to draw a planar graph on a grid Combinatorica 1990 T 10 S 41 51 DOI 10 1007 BF02122694 Jim Geelen Anjie Guo David McKinnon Straight line embeddings of cubic planar graphs with integer edge lengths J Graph Theory 2008 T 58 vip 3 S 270 274 DOI 10 1002 jgt 20304 Harborth H Kemnitz A Moller M Sussenbach A Ganzzahlige planare Darstellungen der platonischen Korper Elem Math 1987 T 42 S 118 122 Kemnitz A Harborth H Plane integral drawings of planar graphs Discrete Math 2001 T 236 S 191 195 DOI 10 1016 S0012 365X 00 00442 8 Bojan Mohar Carsten Thomassen Graphs on Surfaces Johns Hopkins University Press 2001 S roblem 2 8 15 ISBN 0 8018 6689 8 Horst Sachs On a spatial analogue of Kuratowski s theorem on planar graphs An open problem Graph Theory Proceedings of a Conference held in Lagow Poland February 10 13 1981 Springer Verlag 1983 T 1018 S 230 241 Lecture Notes in Mathematics ISBN 978 3 540 12687 4 DOI 10 1007 BFb0071633 Walter Schnyder Proc 1st ACM SIAM Symposium on Discrete Algorithms SODA 1990 S 138 148 Stein S K Convex maps 1951 T 2 vip 3 S 464 466 DOI 10 2307 2031777 Tutte W T How to draw a graph Proceedings of the London Mathematical Society 1963 T 13 S 743 767 DOI 10 1112 plms s3 13 1 743 Klaus Wagner Bemerkungen zum Vierfarbenproblem Jahresbericht der Deutschen Mathematiker Vereinigung 1936 T 46 S 26 32