В теорії графів граф Титце — це неорієнтований кубічний граф з 12 вершинами і 18 ребрами. Граф названий ім'ям Генріха Франца Фрідріха Тітце, який показав в 1910 році, що стрічку Мебіуса можна розділити на шість областей, що дотикаються одна одної — три уздовж кордону стрічки і три уздовж центральної лінії — а тому для графів, що допускають вкладення в стрічку Мебіуса, може знадобитися шість кольорів. Граничні сегменти областей Тітце поділу стрічки Мебіуса (включаючи сегменти уздовж кордону самої стрічки) утворюють вкладення графу Тітце.
Граф Тітце | |
---|---|
Названо на честь | Генріха Франца Фрідріха Тітце |
(Вершин) | 12 |
(Ребер) | 18 |
(Радіус) | 3 |
(Діаметр) | 3 |
(Обхват) | 3 |
(Автоморфізм) | 12 (D6) |
Хроматичне число | 3 |
Хроматичний індекс | 4 |
Властивості | Кубічний Снарк |
Зв'язок з графом Петерсена
Граф Тітце можна отримати з графу Петерсена заміною однієї з його вершин трикутником. Подібно графу Тітце граф Петерсена слугує межами шести взаємно дотичних областей, але в проективній площині, а не на стрічці Мебіуса. Якщо вирізати околицю деякої вершини цього розбиття проективної площини, вершина замінюється межами цієї діри, що дає в точності побудову графу Тітце, описану вище.
Гамільтоновість
І граф Тітце, і граф Петерсена максимально негамільтонові — вони не мають гамільтонова циклу, але будь-які дві несуміжні вершини можуть бути з'єднані гамільтоновим шляхом. Граф Тітце і граф Петерсена є 2-вершинно-зв'язними кубічними негамільтоновими графами з 12 або меншою кількістю вершин.
На відміну від графу Петерсена, граф Тітце не є гіпогамільтоновим — видалення однієї з трьох вершин трикутника утворює менший граф, що залишається гамільтоновим.
Розмальовка ребер і досконалі паросполучення
Розфарбовування ребер графу Тітце вимагає чотирьох кольорів, тобто його хроматичний індекс дорівнює 4. Це еквівалентно тому, що ребра графу Тітце можуть бути розділені на чотири паросполучення, але не менше.
Граф Тітце задовольняє частині вимог визначення снарка — він є кубічним графом без мостів і його ребра не можуть бути пофарбовані в 3 кольори. Однак деякі автори обмежують снарків графами без 3-циклів і 4-циклів, а при цих сильніших умовах граф Тітце не є снарком. Граф Тітце ізоморфний графу J3, графу з нескінченного сімейства снарків «Квітка», запропонованих Р. Ісаакксом у 1975 році .
На відміну від графу Петерсена, граф Тітце може бути покритий чотирма досконалими паросполученнями. Це властивість грає ключову роль в доведенні, що перевірка, чи можна покрити граф чотирма паросполученнями, є NP-повною задачею.
Додаткові властивості
Граф Тітце має хроматичне число 3, хроматичний індекс 4, обхват 3 і діаметр 3. Його число незалежності дорівнює 5, а група автоморфізмів має порядок 12 і вона ізоморфна діедральній групі D6, групи симетрій шестикутника, що включає як обертання, так і відбивання. Ця група містить дві орбіти розміру 3 і одну розміру 6 на вершинах, а тому цей граф не вершинно-транзитивний.
Примітки
- Tietze, Heinrich (1910), Einige Bemerkungen zum Problem des Kartenfärbens auf einseitigen Flächen [Some remarks on the problem of map coloring on one-sided surfaces], Annual Report, 19: 155—159[недоступне посилання з квітня 2019].
- Clark, L.; Entringer, R. (1983), Smallest maximally nonhamiltonian graphs, Periodica Mathematica Hungarica, 14 (1): 57—68, doi:10.1007/BF02023582
- Weisstein, Eric W. Tietze's Graph(англ.) на сайті Wolfram MathWorld.
- Punnim, Narong; Saenpholphat, Varaporn; Thaithae, Sermsri (2007), (PDF), International Journal of Computer Science and Network Security, 7 (1): 83—86, архів оригіналу (PDF) за 22 листопада 2010, процитовано 5 червня 2016
- Isaacs, R. (1975), Infinite families of nontrivial trivalent graphs which are not Tait colorable, Amer. Math. Monthly, Mathematical Association of America, 82 (3): 221—239, doi:10.2307/2319844, JSTOR 2319844.
- Esperet, L.; Mazzuoccolo, G. (2014), On cubic bridgeless graphs whose edge-set cannot be covered by four perfect matchings, Journal of Graph Theory, 77 (2): 144—157, arXiv:1301.6926, doi:10.1002/jgt.21778, MR 3246172.
Галерея
- Хроматичне число графу Тітце дорівнює 3.
- Хроматичний індекс графу Тітце дорівнює 4.
- Граф Тітце має число перетинів 2 і він 1-планарний
- Тривимірне вкладення графу Тітце.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
V teoriyi grafiv graf Titce ce neoriyentovanij kubichnij graf z 12 vershinami i 18 rebrami Graf nazvanij im yam Genriha Franca Fridriha Titce yakij pokazav v 1910 roci sho strichku Mebiusa mozhna rozdiliti na shist oblastej sho dotikayutsya odna odnoyi tri uzdovzh kordonu strichki i tri uzdovzh centralnoyi liniyi a tomu dlya grafiv sho dopuskayut vkladennya v strichku Mebiusa mozhe znadobitisya shist koloriv Granichni segmenti oblastej Titce podilu strichki Mebiusa vklyuchayuchi segmenti uzdovzh kordonu samoyi strichki utvoryuyut vkladennya grafu Titce Graf TitceNazvano na chestGenriha Franca Fridriha TitceVershin12Reber18Radius3Diametr3Obhvat3Avtomorfizm12 D6 Hromatichne chislo3Hromatichnij indeks4VlastivostiKubichnij Snark Rozbittya strichki Mebiusa na shist vzayemno dotichnih oblastej Vershini i rebra rozbittya utvoryuyut vkladennya grafu Titce v strichku Zv yazok z grafom PetersenaGraf Titce mozhna otrimati z grafu Petersena zaminoyu odniyeyi z jogo vershin trikutnikom Podibno grafu Titce graf Petersena sluguye mezhami shesti vzayemno dotichnih oblastej ale v proektivnij ploshini a ne na strichci Mebiusa Yaksho virizati okolicyu deyakoyi vershini cogo rozbittya proektivnoyi ploshini vershina zaminyuyetsya mezhami ciyeyi diri sho daye v tochnosti pobudovu grafu Titce opisanu vishe GamiltonovistI graf Titce i graf Petersena maksimalno negamiltonovi voni ne mayut gamiltonova ciklu ale bud yaki dvi nesumizhni vershini mozhut buti z yednani gamiltonovim shlyahom Graf Titce i graf Petersena ye 2 vershinno zv yaznimi kubichnimi negamiltonovimi grafami z 12 abo menshoyu kilkistyu vershin Na vidminu vid grafu Petersena graf Titce ne ye gipogamiltonovim vidalennya odniyeyi z troh vershin trikutnika utvoryuye menshij graf sho zalishayetsya gamiltonovim Rozmalovka reber i doskonali parospoluchennyaRozfarbovuvannya reber grafu Titce vimagaye chotiroh koloriv tobto jogo hromatichnij indeks dorivnyuye 4 Ce ekvivalentno tomu sho rebra grafu Titce mozhut buti rozdileni na chotiri parospoluchennya ale ne menshe Graf Titce zadovolnyaye chastini vimog viznachennya snarka vin ye kubichnim grafom bez mostiv i jogo rebra ne mozhut buti pofarbovani v 3 kolori Odnak deyaki avtori obmezhuyut snarkiv grafami bez 3 cikliv i 4 cikliv a pri cih silnishih umovah graf Titce ne ye snarkom Graf Titce izomorfnij grafu J3 grafu z neskinchennogo simejstva snarkiv Kvitka zaproponovanih R Isaakksom u 1975 roci Na vidminu vid grafu Petersena graf Titce mozhe buti pokritij chotirma doskonalimi parospoluchennyami Ce vlastivist graye klyuchovu rol v dovedenni sho perevirka chi mozhna pokriti graf chotirma parospoluchennyami ye NP povnoyu zadacheyu Dodatkovi vlastivostiGraf Titce maye hromatichne chislo 3 hromatichnij indeks 4 obhvat 3 i diametr 3 Jogo chislo nezalezhnosti dorivnyuye 5 a grupa avtomorfizmiv maye poryadok 12 i vona izomorfna diedralnij grupi D6 grupi simetrij shestikutnika sho vklyuchaye yak obertannya tak i vidbivannya Cya grupa mistit dvi orbiti rozmiru 3 i odnu rozmiru 6 na vershinah a tomu cej graf ne vershinno tranzitivnij PrimitkiTietze Heinrich 1910 Einige Bemerkungen zum Problem des Kartenfarbens auf einseitigen Flachen Some remarks on the problem of map coloring on one sided surfaces Annual Report 19 155 159 nedostupne posilannya z kvitnya 2019 Clark L Entringer R 1983 Smallest maximally nonhamiltonian graphs Periodica Mathematica Hungarica 14 1 57 68 doi 10 1007 BF02023582 Weisstein Eric W Tietze s Graph angl na sajti Wolfram MathWorld Punnim Narong Saenpholphat Varaporn Thaithae Sermsri 2007 PDF International Journal of Computer Science and Network Security 7 1 83 86 arhiv originalu PDF za 22 listopada 2010 procitovano 5 chervnya 2016 Isaacs R 1975 Infinite families of nontrivial trivalent graphs which are not Tait colorable Amer Math Monthly Mathematical Association of America 82 3 221 239 doi 10 2307 2319844 JSTOR 2319844 Esperet L Mazzuoccolo G 2014 On cubic bridgeless graphs whose edge set cannot be covered by four perfect matchings Journal of Graph Theory 77 2 144 157 arXiv 1301 6926 doi 10 1002 jgt 21778 MR 3246172 GalereyaHromatichne chislo grafu Titce dorivnyuye 3 Hromatichnij indeks grafu Titce dorivnyuye 4 Graf Titce maye chislo peretiniv 2 i vin 1 planarnij Trivimirne vkladennya grafu Titce