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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
Интерактивная навигация по истории
(Показать все непатрулированные изменения)
[отпатрулированная версия][непроверенная версия]
← Предыдущая правка
Содержимое удалено Содержимое добавлено
ВизуальныйВики-текст
Спасено источников — 0, отмечено мёртвыми — 1. #IABot (v2.0beta)
 
(не показаны 2 промежуточные версии 2 участников)
Строка 3: Строка 3:
| Название = Граф Титце
| Название = Граф Титце
| Изображение = Tietze's graph.svg
| Изображение = Tietze's graph.svg
| namesake = [[Титце, Ханс Фридрих|Генрих Титце]]
| namesake = [[Титце, Генрих Фридрих|Генрих Титце]]
| Вершин = 12
| Вершин = 12
| Рёбер = 18
| Рёбер = 18
Строка 16: Строка 16:


В [[Теория графов|теории графов]] '''граф Титце''' — это [[Неориентированный граф|неориентированный]] [[кубический граф]] с 12 вершинами и 18 рёбрами.
В [[Теория графов|теории графов]] '''граф Титце''' — это [[Неориентированный граф|неориентированный]] [[кубический граф]] с 12 вершинами и 18 рёбрами.
Граф назван именем [[Титце, Ханс Фридрих|Генриха Титце]], показавшего в 1910 году, что [[Лента Мёбиуса|ленту Мёбиуса]] можно разделить на шесть областей, касающихся друг друга — три вдоль границы ленты и три вдоль центральной линии — а потому для графов, допускающих [[Вложение графа|вложение]] в ленту Мёбиуса, может потребоваться [[Раскраска графов|шесть цветов]]{{sfn|Tietze|1910|с=155-159}}. Граничные сегменты областей Титца разделения ленты Мёбиуса (включая сегменты вдоль границы самой ленты) образуют вложение графа Титце.
Граф назван именем [[Титце, Генрих Фридрих|Генриха Титце]], показавшего в 1910 году, что [[Лента Мёбиуса|ленту Мёбиуса]] можно разделить на шесть областей, касающихся друг друга — три вдоль границы ленты и три вдоль центральной линии — а потому для графов, допускающих [[Вложение графа|вложение]] в ленту Мёбиуса, может потребоваться [[Раскраска графов|шесть цветов]]{{sfn|Tietze|1910|с=155-159}}. Граничные сегменты областей Титца разделения ленты Мёбиуса (включая сегменты вдоль границы самой ленты) образуют вложение графа Титце.


== Связь с графом Петерсена ==
== Связь с графом Петерсена ==
Строка 25: Строка 25:
И граф Титце, и граф Петерсона ''максимально негамильтоновы'' — они не имеют [[Гамильтонов граф|гамильтонова цикла]], но любые две несмежные вершины могут быть соединены гамильтоновым путём{{sfn|Clark, Entringer|1983|с=57–68 }}. Граф Титце и граф Петерсена являются единственными [[Вершинно k-связный граф|вершинно 2-связными]] кубическими негамильтоновыми графами с 12 или менее вершинами{{sfn|Punnim, Saenpholphat, Thaithae|2007|с=83–86}}.
И граф Титце, и граф Петерсона ''максимально негамильтоновы'' — они не имеют [[Гамильтонов граф|гамильтонова цикла]], но любые две несмежные вершины могут быть соединены гамильтоновым путём{{sfn|Clark, Entringer|1983|с=57–68 }}. Граф Титце и граф Петерсена являются единственными [[Вершинно k-связный граф|вершинно 2-связными]] кубическими негамильтоновыми графами с 12 или менее вершинами{{sfn|Punnim, Saenpholphat, Thaithae|2007|с=83–86}}.


В отличие от графа Петерсена, граф Титце не является {{не переведено 5|Гипогамильтоновый граф|гипогамильтоновым||hypohamiltonian graph}} — удаление одной из трёх вершин треугольника образует меньший граф, остающийся негамильтоновым.
В отличие от графа Петерсена, граф Титце не является [[Гипогамильтоновый граф|гипогамильтоновым]] — удаление одной из трёх вершин треугольника образует меньший граф, остающийся негамильтоновым.


== Рёберная раскраска и совершенные паросочетания ==
== Рёберная раскраска и совершенные паросочетания ==
Строка 32: Строка 32:
Граф Титце удовлетворяет части требований определения [[Снарк (теория графов)|снарка]] — он является кубическим графом [[Мост (теория графов)|без мостов]] и его рёбра не могут быть выкрашены в 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}}.


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

Текущая версия от 11:54, 13 ноября 2024

Разбиение ленты Мёбиуса на шесть взаимно соприкасающихся областей. Вершины и рёбра разбиения образуют вложение графа Титце в ленту.
Граф Титце
Назван в честь Генрих Титце
Вершин 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. — Mathematical Association of America, 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=141437144