Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
Тороїдальний граф — це граф, який можна вкласти на тор; іншими словами, це — граф, вершини якого можна розмістити на торі так, що ребра не схрещуватимуться.
Приклади
Будь-який граф, який можна вкласти у площину, також можна вкласти у тор. Тороїдальний будь-який граф із числом схрещень 1, наприклад: граф Хівуда, повний граф 
(і як наслідок, 
та 
), граф Петерсена, один зі снарків Блануші та всі драбини Мебіуса. Деякі графи з великим числом схрещень також є тороїдальними, наприклад, граф Мебіуса — Кантора, який має число схрещень 4.
Властивості
Хроматичне число будь-якого тороїдального графа не перевищує 7; прикладом тороїдального графа з хроматичним числом 7 є повний граф . Хроматичне число будь-якого тороїдального графа без трикутників не перевищує 4.
Аналогічно теоремі Фарі, будь-який тороїдальний граф можна побудувати з ребрами у вигляді відрізків у прямокутнику з періодичними межами (тобто протилежні границі квадрата ототожнюються). Крім того, у цьому випадку може бути застосована теорема Татта.
Тороїдальні графи також допускають книжкове вкладення з максимум 7 листами.
Див. також
Примітки
Література
- ; Zhang, Ping (2008), Chromatic graph theory, CRC Press, ISBN .
- Endo, Toshiki (1997), The pagenumber of toroidal graphs is at most seven, Discrete Mathematics, 175 (1–3): 87—96, doi:10.1016/S0012-365X(96)00144-6, MR 1475841.
- Gortler, Steven J.; Gotsman, Craig; Thurston, Dylan (2006), Discrete one-forms on meshes and applications to 3D mesh parameterization, Computer Aided Geometric Design, 23 (2): 83—112, doi:10.1016/j.cagd.2005.05.002, MR 2189438.
- (1890), Map colouring theorems, Quarterly J. Math. Oxford Ser., 24: 322—339.
- Kocay, W.; Neilson, D.; Szypowski, R. (2001), Drawing graphs on the torus (PDF), Ars Combinatoria, 59: 259—277, MR 1832459, архів оригіналу (PDF) за 24 грудня 2004, процитовано 9 травня 2019.
- Kronk, Hudson V.; White, Arthur T. (1972), A 4-color theorem for toroidal graphs, , American Mathematical Society, 34 (1): 83—86, doi:10.2307/2037902, JSTOR 2037902, MR 0291019.
- ; (2000), The remarkable generalized Petersen graph G(8,3), Math. Slovaca, 50: 117—121[недоступне посилання з травня 2019].
- Neufeld, Eugene; Myrvold, Wendy (1997), Practical toroidality testing, Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, с. 574—580.
- Orbanić, Alen; ; ; Servatius, Brigitte (2004), Blanuša double, , 9 (1): 91—103.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Nemaye perevirenih versij ciyeyi storinki jmovirno yiyi she ne pereviryali na vidpovidnist pravilam proektu Toroyidalnij graf ce graf yakij mozhna vklasti na tor inshimi slovami ce graf vershini yakogo mozhna rozmistiti na tori tak sho rebra ne shreshuvatimutsya Kubichnij graf z 14 vershinami vkladenij v tor Zmist 1 Prikladi 2 Vlastivosti 3 Div takozh 4 Primitki 5 LiteraturaPrikladired Bud yakij graf yakij mozhna vklasti u ploshinu takozh mozhna vklasti u tor Toroyidalnij bud yakij graf iz chislom shreshen 1 napriklad graf Hivuda povnij graf K 7 displaystyle K 7 nbsp i yak naslidok K 5 displaystyle K 5 nbsp ta K 6 displaystyle K 6 nbsp graf Petersena odin zi snarkiv Blanushi 1 ta vsi drabini Mebiusa Deyaki grafi z velikim chislom shreshen takozh ye toroyidalnimi napriklad graf Mebiusa Kantora yakij maye chislo shreshen 4 2 Vlastivostired Hromatichne chislo bud yakogo toroyidalnogo grafa ne perevishuye 7 3 prikladom toroyidalnogo grafa z hromatichnim chislom 7 ye povnij graf K 7 displaystyle K 7 nbsp 4 Hromatichne chislo bud yakogo toroyidalnogo grafa bez trikutnikiv ne perevishuye 4 5 Analogichno teoremi Fari bud yakij toroyidalnij graf mozhna pobuduvati z rebrami u viglyadi vidrizkiv u pryamokutniku z periodichnimi mezhami tobto protilezhni granici kvadrata ototozhnyuyutsya 6 Krim togo u comu vipadku mozhe buti zastosovana teorema Tatta 7 Toroyidalni grafi takozh dopuskayut knizhkove vkladennya z maksimum 7 listami 8 Div takozhred Bagatogrannik Chasara en Planarnij graf Topologichna teoriya grafivPrimitkired Orbanic et al 2004 Marusic amp Pisanski 2000 Heawood 1890 Chartrand amp Zhang 2008 Kronk amp White 1972 Kocay Neilson Szypowski 2001 Gortler Gotsman Thurston 2006 Endo 1997 Literaturared Chartrand Gary Zhang Ping 2008 Chromatic graph theory CRC Press ISBN 978 1 58488 800 0 Endo Toshiki 1997 The pagenumber of toroidal graphs is at most seven Discrete Mathematics 175 1 3 87 96 doi 10 1016 S0012 365X 96 00144 6 MR 1475841 Gortler Steven J Gotsman Craig Thurston Dylan 2006 Discrete one forms on meshes and applications to 3D mesh parameterization Computer Aided Geometric Design 23 2 83 112 doi 10 1016 j cagd 2005 05 002 MR 2189438 Heawood P J 1890 Map colouring theorems Quarterly J Math Oxford Ser 24 322 339 Kocay W Neilson D Szypowski R 2001 Drawing graphs on the torus PDF Ars Combinatoria 59 259 277 MR 1832459 arhiv originalu PDF za 24 grudnya 2004 procitovano 9 travnya 2019 Kronk Hudson V White Arthur T 1972 A 4 color theorem for toroidal graphs Proceedings of the American Mathematical Society American Mathematical Society 34 1 83 86 doi 10 2307 2037902 JSTOR 2037902 MR 0291019 Marusic Dragan Pisanski Tomaz 2000 The remarkable generalized Petersen graph G 8 3 Math Slovaca 50 117 121 nedostupne posilannya z travnya 2019 Neufeld Eugene Myrvold Wendy 1997 Practical toroidality testing Proceedings of the Eighth Annual ACM SIAM Symposium on Discrete Algorithms s 574 580 Orbanic Alen Pisanski Tomaz Randic Milan Servatius Brigitte 2004 Blanusa double Math Commun 9 1 91 103 Otrimano z https uk wikipedia org wiki Toroyidalnij graf