Loading AI tools
З Вікіпедії, вільної енциклопедії
Тороїдальний граф — це граф, який можна вкласти на тор; іншими словами, це — граф, вершини якого можна розмістити на торі так, що ребра не схрещуватимуться.
Будь-який граф, який можна вкласти у площину, також можна вкласти у тор. Тороїдальний будь-який граф із числом схрещень 1, наприклад: граф Хівуда, повний граф (і як наслідок, та ), граф Петерсена, один зі снарків Блануші[1] та всі драбини Мебіуса. Деякі графи з великим числом схрещень також є тороїдальними, наприклад, граф Мебіуса — Кантора, який має число схрещень 4[2].
Хроматичне число будь-якого тороїдального графа не перевищує 7[3]; прикладом тороїдального графа з хроматичним числом 7 є повний граф [4]. Хроматичне число будь-якого тороїдального графа без трикутників не перевищує 4[5].
Аналогічно теоремі Фарі, будь-який тороїдальний граф можна побудувати з ребрами у вигляді відрізків у прямокутнику з періодичними межами (тобто протилежні границі квадрата ототожнюються)[6]. Крім того, у цьому випадку може бути застосована теорема Татта[7].
Тороїдальні графи також допускають книжкове вкладення з максимум 7 листами[8].
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.