Azərbaycanca AzərbaycancaБеларускі БеларускіDansk DanskDeutsch DeutschEspañola EspañolaFrançais FrançaisIndonesia IndonesiaItaliana Italiana日本語 日本語Қазақ ҚазақLietuvos LietuvosNederlands NederlandsPortuguês PortuguêsРусский Русскийසිංහල සිංහලแบบไทย แบบไทยTürkçe TürkçeУкраїнська Українська中國人 中國人United State United StateAfrikaans Afrikaans
Підтримка
www.wikidata.uk-ua.nina.az

Тороїдальний граф це граф який можна вкласти на тор іншими словами це граф вершини якого можна розмістити на торі так що

Тороїдальний граф

Тороїдальний граф

Тороїдальний граф — це граф, який можна вкласти на тор; іншими словами, це — граф, вершини якого можна розмістити на торі так, що ребра не схрещуватимуться.

image
Кубічний граф з 14 вершинами, вкладений в тор

Приклади

Будь-який граф, який можна вкласти у площину, також можна вкласти у тор. Тороїдальний будь-який граф із числом схрещень 1, наприклад: граф Хівуда, повний граф image (і як наслідок, image та image), граф Петерсена, один зі снарків Блануші та всі драбини Мебіуса. Деякі графи з великим числом схрещень також є тороїдальними, наприклад, граф Мебіуса — Кантора, який має число схрещень 4.

Властивості

Хроматичне число будь-якого тороїдального графа не перевищує 7; прикладом тороїдального графа з хроматичним числом 7 є повний граф image. Хроматичне число будь-якого тороїдального графа без трикутників не перевищує 4.

Аналогічно теоремі Фарі, будь-який тороїдальний граф можна побудувати з ребрами у вигляді відрізків у прямокутнику з періодичними межами (тобто протилежні границі квадрата ототожнюються). Крім того, у цьому випадку може бути застосована теорема Татта.

Тороїдальні графи також допускають книжкове вкладення з максимум 7 листами.

Див. також

Примітки

  1. Orbanić et al., 2004.
  2. Marušič & Pisanski, 2000.
  3. Heawood, 1890.
  4. Chartrand & Zhang, 2008.
  5. Kronk & White, 1972.
  6. Kocay, Neilson, Szypowski, 2001.
  7. Gortler, Gotsman, Thurston, 2006.
  8. Endo, 1997.

Література

  • ; 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), (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, Інтернет

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 torPrikladiBud 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 K7 displaystyle K 7 i yak naslidok K5 displaystyle K 5 ta K6 displaystyle K 6 graf Petersena odin zi snarkiv Blanushi ta vsi drabini Mebiusa Deyaki grafi z velikim chislom shreshen takozh ye toroyidalnimi napriklad graf Mebiusa Kantora yakij maye chislo shreshen 4 VlastivostiHromatichne chislo bud yakogo toroyidalnogo grafa ne perevishuye 7 prikladom toroyidalnogo grafa z hromatichnim chislom 7 ye povnij graf K7 displaystyle K 7 Hromatichne chislo bud yakogo toroyidalnogo grafa bez trikutnikiv ne perevishuye 4 Analogichno teoremi Fari bud yakij toroyidalnij graf mozhna pobuduvati z rebrami u viglyadi vidrizkiv u pryamokutniku z periodichnimi mezhami tobto protilezhni granici kvadrata ototozhnyuyutsya Krim togo u comu vipadku mozhe buti zastosovana teorema Tatta Toroyidalni grafi takozh dopuskayut knizhkove vkladennya z maksimum 7 listami Div takozh en Planarnij graf Topologichna teoriya grafivPrimitkiOrbanic 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 Literatura 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 1890 Map colouring theorems Quarterly J Math Oxford Ser 24 322 339 Kocay W Neilson D Szypowski R 2001 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 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 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 Servatius Brigitte 2004 Blanusa double 9 1 91 103

Дата публікації:
Топ