Вкладення Татта (барицентричне вкладення) простого 3-вершинно-зв'язного планарного графа — вкладення без перетинів із ребрами у вигляді відрізків з додатковими властивостями, що межею зовнішньої грані є опуклий многокутник і кожна внутрішня вершина є геометричним центром сусідів. Якщо зовнішній многокутник фіксований, ця умова на внутрішні вершини визначає їх положення однозначно як розв'язок системи лінійних рівнянь. Розв'язування рівнянь дає планарне вкладення. Теорема Татта «про гумове вкладення» стверджує, що в єдиному розв'язку ніколи немає перетинів ребер і, строгіше, що будь-яка грань отриманого планарного вкладення опукла. Вкладення називають «гумовим», оскільки таке вкладення можна знайти як рівноважне положення системи пружин або гумових ременів, що представляють ребра графа.
Приклад
![image](https://www.wikidata.uk-ua.nina.az/image/aHR0cHM6Ly93d3cud2lraWRhdGEudWstdWEubmluYS5hei9pbWFnZS9hSFIwY0hNNkx5OTFjR3h2WVdRdWQybHJhVzFsWkdsaExtOXlaeTkzYVd0cGNHVmthV0V2WTI5dGJXOXVjeTkwYUhWdFlpOHpMek0zTDFSMWRIUmxYMk4xWW1VdWMzWm5Mekl5TUhCNExWUjFkSFJsWDJOMVltVXVjM1puTG5CdVp3PT0ucG5n.png)
Нехай — граф куба. Зафіксуємо (вибравши одну з чотирикутних граней як зовнішню грань) чотири вершини зовнішньої грані в кутах одиничного квадрата, координати x і y якого є комбінаціями нулів і одиниць. Чотири інші вершини тоді розташовуються в чотирьох точках, координати x і y яких є комбінаціями 1/3 і 2/3, як показано на малюнку. Результат — вкладення Татта. Для кожної внутрішньої вершини
цього вкладення сусідні три вершини мають три значення координат (як x, так і y), одне з яких дорівнює координаті
, одне менше, а інше більше на 1/3. У середньому отримуємо значення координати самої точки
.
Система лінійних рівнянь
Умова, що вершина v має середнє значення координат сусідів, можна виразити у вигляді двох лінійних рівнянь: одне — для координати точки x, інше — для координати y. Для графа з n вершинами, h із яких зафіксовано у вершинах зовнішньої грані, є два рівняння та два невідомих (координати) для кожної внутрішньої вершини. Таким чином, отримуємо систему лінійних рівнянь з 2(n − h) рівняннями з 2(n − h) невідомими, розв'язком якої буде вкладення Татта. Як показав Татт, для 3-вершинно-зв'язних планарних графів ця система не вироджена. Тому система матиме єдиний розв'язок і (з фіксованою зовнішньою гранню) граф буде єдиним вкладенням Татта. Це вкладення можна знайти за поліноміальний час, розв'язавши систему рівнянь, наприклад, за допомогою послідовного виключення змінних.
Подання многогранників
За теоремою Штайніца 3-зв'язні планарні графи, для яких застосовується теорема Татта «про гумове вкладення», збігаються з поліедральними графами, — графами, утвореними вершинами та ребрами опуклого многогранника. За методом Максвелла — Кремони двовимірне вкладення планарного графа утворює проєкцію тривимірного опуклого многогранника тоді й лише тоді, коли вкладення має рівноважну напругу, розподіл сил для кожного ребра (в обох кінцях ребер у протилежних напрямках, паралельних ребрам), так що сили в кожній вершині зрівноважуються. Для вкладення Татта розподіл сил кожного ребра пропорційно довжині ребра (подібно до гумки) врівноважує сили в усіх внутрішніх точках, але не у вершинах зовнішнього многокутника. Якщо зовнішній многокутник є трикутником, можна на трьох зовнішніх ребрах призначити відштовхувальні сили, які зрівноважать сили у вершинах зовнішнього трикутника. Таким чином, вкладення Татта можна використати для пошуку діаграм Шлегеля будь-якого опуклого многогранника. Для будь-якого 3-зв'язного планарного графа G або сам граф G, або його двоїстий має трикутник, так що отримуємо многогранне подання графа G або його двоїстого. Якщо двоїстий граф має трикутну грань, полярне спряження дає многогранне подання самого графа G.
Узагальнення
Гортлер, Готсман і Терстон довели результати, аналогічні теоремі Татта «про гумове вкладення», для вкладень графів у тор.
Чилакамаррі, Дін і Літман досліджували тривимірне вкладення графів чотиривимірних многогранників, утворене тим самим методом, що й у методі вкладення Татта — вибираємо одну зовнішню фасету многогранника як зовнішню грань тривимірного вкладення і фіксуємо положення вершин у тривимірному просторі. Інші вершини многогранника можна рухати, а ребра замінимо пружинами (або гумовими шнурами). Тепер знайдемо конфігурацію системи пружин із найменшою енергією. Як вони показали, система рівнянь, отримана в такий спосіб, також буде невиродженою, але залишається незрозумілим, за яких умов цей метод дасть вкладення, в якому всі грані многогранника будуть опуклими.
Пов'язані результати
Факт, що будь-який простий планарний граф можна намалювати з прямолінійними ребрами, називають теоремою Фарі. Теорема Татта «про гумове вкладення» доводить це для 3-зв'язних планарних графів, але теорема Фарі правильна для будь-яких планарних графів незалежно від зв'язності. Застосування теореми Татта для графів, які не є 3-зв'язними, може призвести до виродження, за якого підграфи даного графа зливаються в точку або відрізок. Тим не менш, будь-який планарний граф можна намалювати за допомогою вкладення Татта, додавши ребра, щоб зробити його 3-зв'язним, потім малюється 3-зв'язний граф і з нього видаляються зайві ребра.
Граф k-вершинно-зв'язний (але не обов'язково планарний) тоді й лише тоді, коли він має вкладення в (k−1)-вимірний простір, у якому будь-який набір з k вершин розташовується у вершинах симплекса, а для будь-якої з решти вершин v опукла оболонка її сусідів має повну розмірність і v розташовується всередині цієї оболонки. Якщо таке вкладення існує, його можна знайти, зафіксувавши положення k вершин і розв'язавши систему рівнянь. Розв'язок розміщує кожну вершину в місце, що є середнім положень сусідів, так само, як за планарного вкладення Татта.
У методі скінченних елементів при побудові загальним методом постобробки отриманої сітки для покращення якості є [en], що особливо популярно для чотирикутних сіток, для яких інші методи, такі як алгоритм Ллойда для згладжування трикутних сіток, менш застосовні. У цьому методі кожна вершина рухається в напрямку середнього значення положень сусідів, але цей рух здійснюється за малу кількість ітерацій, щоб уникнути значного спотворення розмірів елементів, або (в разі неопуклої ділянки сітки) отримання сплутаних непланарних сіток.
Силові методи вкладання графів залишаються популярними методами візуалізації графів, але в них зазвичай використовують складніші системи сил, комбінуючи сили притягання ребер графа (як у вкладенні Татта) зі силами відштовхування між довільними парами вершин. Ці додаткові сили можуть дати системі багато локальних стійких конфігурацій, а не одну глобальну, як у вкладенні Татта.
Примітки
- Tutte, 1963, с. 743–767.
- Tutte, 1963.
- Rote, 2012, с. 238–241.
- Gortler, Gotsman, Thurston, 2006.
- Gortler, Gotsman, Thurston, 2006, с. 83–112.
- Chilakamarri, Dean, Littman, 1995.
- Chilakamarri, Dean, Littman, 1995, с. 129–140.
- Про зв'язок між теоремами Татта і Фарі та історію перевідкриття теореми Фарі див. книгу Фелснера (Felsner, 2012).
- Linial, Lovász, Wigderson, 1988, с. 91–102.
- Herrmann, 1976, с. 749–907.
- Kobourov, 2012.
Література
- Steven J. Gortler, Craig Gotsman, Dylan Thurston. Discrete one-forms on meshes and applications to 3D mesh parameterization // Computer Aided Geometric Design. — 2006. — Т. 23, вип. 2. — С. 83–112. — DOI: .
- Günter Rote. Graph Drawing: 19th International Symposium, GD 2011, Eindhoven, The Netherlands, September 21–23, 2011, Revised Selected Papers. — Springer, 2012. — Т. 7034. — С. 238–241. — (Lecture Notes in Computer Science) — DOI:
- Kiran Chilakamarri, Nathaniel Dean, Michael Littman. Three-dimensional Tutte embedding // Congressus Numerantium, Proceedings of the Twenty-sixth Southeastern International Conference on Combinatorics, Graph Theory and Computing (Boca Raton, FL, 1995). — 1995. — Т. 107. — С. 129–140.
- Stefan Felsner. Geometric Graphs and Arrangements: Some Chapters from Combinatorial Geometry. — Springer, 2012. — С. 37. — (Advanced Lectures in Mathematics) — .
- N. Linial, L. Lovász, A. Wigderson. Rubber bands, convex embeddings and graph connectivity // . — 1988. — Т. 8, вип. 1. — С. 91–102. — DOI: .
- Leonard R. Herrmann. Laplacian-isoparametric grid generation scheme // Journal of the Engineering Mechanics Division. — 1976. — Т. 102, вип. 5. — С. 749–907.
- W. T. Tutte. How to draw a graph // Proceedings of the London Mathematical Society. — 1963. — Т. 13. — С. 743–767. — DOI: .
- Stephen G. Kobourov. Spring Embedders and Force-Directed Graph Drawing Algorithms. — 2012. — arXiv:1201.3011.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Vkladennya Tatta baricentrichne vkladennya prostogo 3 vershinno zv yaznogo planarnogo grafa vkladennya bez peretiniv iz rebrami u viglyadi vidrizkiv z dodatkovimi vlastivostyami sho mezheyu zovnishnoyi grani ye opuklij mnogokutnik i kozhna vnutrishnya vershina ye geometrichnim centrom susidiv Yaksho zovnishnij mnogokutnik fiksovanij cya umova na vnutrishni vershini viznachaye yih polozhennya odnoznachno yak rozv yazok sistemi linijnih rivnyan Rozv yazuvannya rivnyan daye planarne vkladennya Teorema Tatta pro gumove vkladennya stverdzhuye sho v yedinomu rozv yazku nikoli nemaye peretiniv reber i strogishe sho bud yaka gran otrimanogo planarnogo vkladennya opukla Vkladennya nazivayut gumovim oskilki take vkladennya mozhna znajti yak rivnovazhne polozhennya sistemi pruzhin abo gumovih remeniv sho predstavlyayut rebra grafa PrikladVkladennya Tatta grafa kuba Zovnishni chotiri vershini fiksovani v kutah odinichnogo kvadrata a reshta vershin ye geometrichnimi centrami susidnih vershin Nehaj G displaystyle G graf kuba Zafiksuyemo vibravshi odnu z chotirikutnih granej yak zovnishnyu gran chotiri vershini zovnishnoyi grani v kutah odinichnogo kvadrata koordinati x i y yakogo ye kombinaciyami nuliv i odinic Chotiri inshi vershini todi roztashovuyutsya v chotiroh tochkah koordinati x i y yakih ye kombinaciyami 1 3 i 2 3 yak pokazano na malyunku Rezultat vkladennya Tatta Dlya kozhnoyi vnutrishnoyi vershini v displaystyle v cogo vkladennya susidni tri vershini mayut tri znachennya koordinat yak x tak i y odne z yakih dorivnyuye koordinati v displaystyle v odne menshe a inshe bilshe na 1 3 U serednomu otrimuyemo znachennya koordinati samoyi tochki v displaystyle v Sistema linijnih rivnyanUmova sho vershina v maye serednye znachennya koordinat susidiv mozhna viraziti u viglyadi dvoh linijnih rivnyan odne dlya koordinati tochki x inshe dlya koordinati y Dlya grafa z n vershinami h iz yakih zafiksovano u vershinah zovnishnoyi grani ye dva rivnyannya ta dva nevidomih koordinati dlya kozhnoyi vnutrishnoyi vershini Takim chinom otrimuyemo sistemu linijnih rivnyan z 2 n h rivnyannyami z 2 n h nevidomimi rozv yazkom yakoyi bude vkladennya Tatta Yak pokazav Tatt dlya 3 vershinno zv yaznih planarnih grafiv cya sistema ne virodzhena Tomu sistema matime yedinij rozv yazok i z fiksovanoyu zovnishnoyu grannyu graf bude yedinim vkladennyam Tatta Ce vkladennya mozhna znajti za polinomialnij chas rozv yazavshi sistemu rivnyan napriklad za dopomogoyu poslidovnogo viklyuchennya zminnih Podannya mnogogrannikivZa teoremoyu Shtajnica 3 zv yazni planarni grafi dlya yakih zastosovuyetsya teorema Tatta pro gumove vkladennya zbigayutsya z poliedralnimi grafami grafami utvorenimi vershinami ta rebrami opuklogo mnogogrannika Za metodom Maksvella Kremoni dvovimirne vkladennya planarnogo grafa utvoryuye proyekciyu trivimirnogo opuklogo mnogogrannika todi j lishe todi koli vkladennya maye rivnovazhnu naprugu rozpodil sil dlya kozhnogo rebra v oboh kincyah reber u protilezhnih napryamkah paralelnih rebram tak sho sili v kozhnij vershini zrivnovazhuyutsya Dlya vkladennya Tatta rozpodil sil kozhnogo rebra proporcijno dovzhini rebra podibno do gumki vrivnovazhuye sili v usih vnutrishnih tochkah ale ne u vershinah zovnishnogo mnogokutnika Yaksho zovnishnij mnogokutnik ye trikutnikom mozhna na troh zovnishnih rebrah priznachiti vidshtovhuvalni sili yaki zrivnovazhat sili u vershinah zovnishnogo trikutnika Takim chinom vkladennya Tatta mozhna vikoristati dlya poshuku diagram Shlegelya bud yakogo opuklogo mnogogrannika Dlya bud yakogo 3 zv yaznogo planarnogo grafa G abo sam graf G abo jogo dvoyistij maye trikutnik tak sho otrimuyemo mnogogranne podannya grafa G abo jogo dvoyistogo Yaksho dvoyistij graf maye trikutnu gran polyarne spryazhennya daye mnogogranne podannya samogo grafa G UzagalnennyaGortler Gotsman i Terston doveli rezultati analogichni teoremi Tatta pro gumove vkladennya dlya vkladen grafiv u tor Chilakamarri Din i Litman doslidzhuvali trivimirne vkladennya grafiv chotirivimirnih mnogogrannikiv utvorene tim samim metodom sho j u metodi vkladennya Tatta vibirayemo odnu zovnishnyu fasetu mnogogrannika yak zovnishnyu gran trivimirnogo vkladennya i fiksuyemo polozhennya vershin u trivimirnomu prostori Inshi vershini mnogogrannika mozhna ruhati a rebra zaminimo pruzhinami abo gumovimi shnurami Teper znajdemo konfiguraciyu sistemi pruzhin iz najmenshoyu energiyeyu Yak voni pokazali sistema rivnyan otrimana v takij sposib takozh bude nevirodzhenoyu ale zalishayetsya nezrozumilim za yakih umov cej metod dast vkladennya v yakomu vsi grani mnogogrannika budut opuklimi Pov yazani rezultatiFakt sho bud yakij prostij planarnij graf mozhna namalyuvati z pryamolinijnimi rebrami nazivayut teoremoyu Fari Teorema Tatta pro gumove vkladennya dovodit ce dlya 3 zv yaznih planarnih grafiv ale teorema Fari pravilna dlya bud yakih planarnih grafiv nezalezhno vid zv yaznosti Zastosuvannya teoremi Tatta dlya grafiv yaki ne ye 3 zv yaznimi mozhe prizvesti do virodzhennya za yakogo pidgrafi danogo grafa zlivayutsya v tochku abo vidrizok Tim ne mensh bud yakij planarnij graf mozhna namalyuvati za dopomogoyu vkladennya Tatta dodavshi rebra shob zrobiti jogo 3 zv yaznim potim malyuyetsya 3 zv yaznij graf i z nogo vidalyayutsya zajvi rebra Graf k vershinno zv yaznij ale ne obov yazkovo planarnij todi j lishe todi koli vin maye vkladennya v k 1 vimirnij prostir u yakomu bud yakij nabir z k vershin roztashovuyetsya u vershinah simpleksa a dlya bud yakoyi z reshti vershin v opukla obolonka yiyi susidiv maye povnu rozmirnist i v roztashovuyetsya vseredini ciyeyi obolonki Yaksho take vkladennya isnuye jogo mozhna znajti zafiksuvavshi polozhennya k vershin i rozv yazavshi sistemu rivnyan Rozv yazok rozmishuye kozhnu vershinu v misce sho ye serednim polozhen susidiv tak samo yak za planarnogo vkladennya Tatta U metodi skinchennih elementiv pri pobudovi zagalnim metodom postobrobki otrimanoyi sitki dlya pokrashennya yakosti ye en sho osoblivo populyarno dlya chotirikutnih sitok dlya yakih inshi metodi taki yak algoritm Llojda dlya zgladzhuvannya trikutnih sitok mensh zastosovni U comu metodi kozhna vershina ruhayetsya v napryamku serednogo znachennya polozhen susidiv ale cej ruh zdijsnyuyetsya za malu kilkist iteracij shob uniknuti znachnogo spotvorennya rozmiriv elementiv abo v razi neopukloyi dilyanki sitki otrimannya splutanih neplanarnih sitok Silovi metodi vkladannya grafiv zalishayutsya populyarnimi metodami vizualizaciyi grafiv ale v nih zazvichaj vikoristovuyut skladnishi sistemi sil kombinuyuchi sili prityagannya reber grafa yak u vkladenni Tatta zi silami vidshtovhuvannya mizh dovilnimi parami vershin Ci dodatkovi sili mozhut dati sistemi bagato lokalnih stijkih konfiguracij a ne odnu globalnu yak u vkladenni Tatta PrimitkiTutte 1963 s 743 767 Tutte 1963 Rote 2012 s 238 241 Gortler Gotsman Thurston 2006 Gortler Gotsman Thurston 2006 s 83 112 Chilakamarri Dean Littman 1995 Chilakamarri Dean Littman 1995 s 129 140 Pro zv yazok mizh teoremami Tatta i Fari ta istoriyu perevidkrittya teoremi Fari div knigu Felsnera Felsner 2012 Linial Lovasz Wigderson 1988 s 91 102 Herrmann 1976 s 749 907 Kobourov 2012 LiteraturaSteven J Gortler Craig Gotsman Dylan Thurston Discrete one forms on meshes and applications to 3D mesh parameterization Computer Aided Geometric Design 2006 T 23 vip 2 S 83 112 DOI 10 1016 j cagd 2005 05 002 Gunter Rote Graph Drawing 19th International Symposium GD 2011 Eindhoven The Netherlands September 21 23 2011 Revised Selected Papers Springer 2012 T 7034 S 238 241 Lecture Notes in Computer Science DOI 10 1007 978 3 642 25878 7 23 Kiran Chilakamarri Nathaniel Dean Michael Littman Three dimensional Tutte embedding Congressus Numerantium Proceedings of the Twenty sixth Southeastern International Conference on Combinatorics Graph Theory and Computing Boca Raton FL 1995 1995 T 107 S 129 140 Stefan Felsner Geometric Graphs and Arrangements Some Chapters from Combinatorial Geometry Springer 2012 S 37 Advanced Lectures in Mathematics ISBN 9783322803030 N Linial L Lovasz A Wigderson Rubber bands convex embeddings and graph connectivity 1988 T 8 vip 1 S 91 102 DOI 10 1007 BF02122557 Leonard R Herrmann Laplacian isoparametric grid generation scheme Journal of the Engineering Mechanics Division 1976 T 102 vip 5 S 749 907 W T Tutte 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 Stephen G Kobourov Spring Embedders and Force Directed Graph Drawing Algorithms 2012 arXiv 1201 3011