Граф Титце: различия между версиями

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
Интерактивная навигация по истории
(Показать все непатрулированные изменения)
[отпатрулированная версия][отпатрулированная версия]
← Предыдущая правкаСледующая правка →
Содержимое удалено Содержимое добавлено
ВизуальныйВики-текст
Строка 28: Строка 28:


==Рёберная раскраска и совершенные паросочетания ==
==Рёберная раскраска и совершенные паросочетания ==
[[Рёберная раскраска]] графа Титце требует четыре цвета. То есть, его хроматический индекс равен 4. Это эквивалентно тому, что рёбра графа Титца могут быть разделены на четыре [[Паросочетание|паросочетания]], но не меньше.
[[Рёберная раскраска]] графа Титце требует четыре цвета. То есть его хроматический индекс равен 4. Это эквивалентно тому, что рёбра графа Титца могут быть разделены на четыре [[Паросочетание|паросочетания]], но не меньше.


Граф Титце удовлетворяет части требований определения [[Снарк (теория графов)|снарка]] – он является кубическим графом [[Мост (теория графов)|без мостов]] и его рёбра не могут быть выкрашены в 3 цвета. Однако, некоторые авторы ограничивают снарки графами без 3-циклов и 4-циклов, а при этих более сильных условиях граф Титце не является снарком. Граф Титце изоморфен графу J<sub>3</sub>, графу из бесконечного семейства [[Снарк «Цветок»|снарков «Цветок»]], предложенных Р. Исаакксом в 1975 {{sfn|Isaacs|1975|с=221–239}}.
Граф Титце удовлетворяет части требований определения [[Снарк (теория графов)|снарка]] – он является кубическим графом [[Мост (теория графов)|без мостов]] и его рёбра не могут быть выкрашены в 3 цвета. Однако некоторые авторы ограничивают снарки графами без 3-циклов и 4-циклов, а при этих более сильных условиях граф Титце не является снарком. Граф Титце изоморфен графу J<sub>3</sub>, графу из бесконечного семейства [[Снарк «Цветок»|снарков «Цветок»]], предложенных Р. Исаакксом в 1975 {{sfn|Isaacs|1975|с=221–239}}.


В отличие от графа Петерсена, граф Титце может быть покрыт четырьмя [[Паросочетание|совершенными паросочетаниями]]. Это свойство играет ключевую роль в доказательстве, что проверка, можно ли покрыть граф четырьмя паросочетаниями, является [[NP-полная задача|NP-полной задачей]] {{sfn|Esperet, Mazzuoccolo|2014|с= 144–157}}.
В отличие от графа Петерсена, граф Титце может быть покрыт четырьмя [[Паросочетание|совершенными паросочетаниями]]. Это свойство играет ключевую роль в доказательстве, что проверка, можно ли покрыть граф четырьмя паросочетаниями, является [[NP-полная задача|NP-полной задачей]] {{sfn|Esperet, Mazzuoccolo|2014|с= 144–157}}.

Версия от 16:17, 19 марта 2016

Разбиение ленты Мёбиуса на шесть взаимно соприкасающихся областей. Вершины и рёбра разбиения образуют вложение графа Титце в ленту.
Граф Титце
Назван в честь Генрих Франц Фридрих Титце[англ.]*
Вершин 12
Рёбер 18
Радиус 3
Диаметр 3
Обхват 3
Автоморфизмы 12 (D6)
Хроматическое число 3
Хроматический индекс 4
Свойства Кубический
Снарк
Логотип Викисклада Медиафайлы на Викискладе

В теории графов граф Титце – это неориентированный кубический граф с 12 вершинами и 18 рёбрами. Граф назван именем Генриха Франца Фридриха Титце[англ.]*, показавшего в 1910, что ленту Мёбиуса можно разделить на шесть областей, касающихся друг друга – три вдоль границы ленты и три вдоль центральной линии – а потому для графов, допускающих вложение?! в ленту Мёбиуса может потребоваться шесть цветов [1]. Граничные сегменты областей Титца разделения ленты Мёбиуса (включая сегменты вдоль границы самой ленты) образуют вложение графа Титце.

Связь с графом Петерсена

Граф Титце можно получить из графа Петерсена заменой одной из его вершин Треугольником [2]. Подобно графу Титце граф Петерсена служит границами шести взаимно соприкасающихся шести областей, но в проективной плоскости, а не на ленте Мёбиуса. Если вырезать окрестность некоторой вершины этого разбиения проективной плоскости, вершина заменяется границами этой дыры, что даёт в точности построение графа Титце, описанное выше.

Гамильтоновость

И граф Титце, и граф Петерсона максимально негамильтоновы – они не имеют гамильтонова цикла, но любые две несмежные вершины могут быть соединены гамильтоновым путём [2]. Граф Титце и граф Петерсена являются единственными вершинно 2-связными кубическими негамильтоновыми графами с 12 или менее вершинами [3].

В отличие от графа Петерсена граф Титце не является гипогамильтоновым[англ.]* – удаление одной из трёх вершин треугольника образует меньший граф, остающийся негамильтоновым.

Рёберная раскраска и совершенные паросочетания

Рёберная раскраска графа Титце требует четыре цвета. То есть его хроматический индекс равен 4. Это эквивалентно тому, что рёбра графа Титца могут быть разделены на четыре паросочетания, но не меньше.

Граф Титце удовлетворяет части требований определения снарка – он является кубическим графом без мостов и его рёбра не могут быть выкрашены в 3 цвета. Однако некоторые авторы ограничивают снарки графами без 3-циклов и 4-циклов, а при этих более сильных условиях граф Титце не является снарком. Граф Титце изоморфен графу J3, графу из бесконечного семейства снарков «Цветок», предложенных Р. Исаакксом в 1975 [4].

В отличие от графа Петерсена, граф Титце может быть покрыт четырьмя совершенными паросочетаниями. Это свойство играет ключевую роль в доказательстве, что проверка, можно ли покрыть граф четырьмя паросочетаниями, является NP-полной задачей [5].

Дополнительные свойства

Граф Титце имеет хроматическое число 3, хроматический индекс 4, обхват 3 и диаметр 3. Его число независимости равно 5, а группа автоморфизмов имеет порядок 12 и она изоморфна диэдрической группе D6, группе симметрий шестиугольника, включающей как вращения, так и отражения. Эта группа содержит две орбиты размера 3 и одну размера 6 на вершинах, а потому этот граф не вершинно транзитивен.

Галерея

См. также

Примечания

  1. ↑ Tietze, 1910, с. 155-159.
  2. ↑ 1 2 Clark, Entringer, 1983, с. 57–68.
  3. ↑ Punnim, Saenpholphat, Thaithae, 2007, с. 83–86.
  4. ↑ Isaacs, 1975, с. 221–239.
  5. ↑ Esperet, Mazzuoccolo, 2014, с. 144–157.

Литература

  • L. Clark, R. Entringer. Smallest maximally nonhamiltonian graphs // Periodica Mathematica Hungarica. — 1983. — Т. 14, вып. 1. — doi:10.1007/BF02023582.
  • Narong Punnim, Varaporn Saenpholphat, Sermsri Thaithae. Almost Hamiltonian cubic graphs // International Journal of Computer Science and Network Security. — 2007. — Т. 7, вып. 1.
  • R. Isaacs. Infinite families of nontrivial trivalent graphs which are not Tait colorable // Amer. Math. Monthly. — 1975. — Т. 82, вып. 3. — doi:10.2307/2319844. — JSTOR 2319844.
  • Heinrich Tietze. Einige Bemerkungen zum Problem des Kartenfärbens auf einseitigen Flächen (Some remarks on the problem of map coloring on one-sided surfaces) // DMV Annual Report. — 1910. — Т. 19.
  • L. Clark, R. Entringer. Smallest maximally nonhamiltonian graphs // Periodica Mathematica Hungarica. — 1983. — Т. 14, вып. 1. — doi:10.1007/BF02023582.
  • L. Esperet, G. Mazzuoccolo. On cubic bridgeless graphs whose edge-set cannot be covered by four perfect matchings // Journal of Graph Theory. — 2014. — Т. 77, вып. 2. — doi:10.1002/jgt.21778. — arXiv:1301.6926..
Источник — https://ru.wikipedia.org/ruwiki/w/index.php?title=Граф_Титце&oldid=77199897