Русская Википедия:Граф Татта
Шаблон:Граф Граф Татта — пример кубического полиэдрального графа, не являющегося гамильтоновым. Таким образом, он служит контрпримером к гипотезе Тэйта, предполагавшей, что любой 3-регулярный многогранник имеет гамильтонов цикл[1][2].
Построен Уильямом Таттом в 1946 году[3]. Позднее найдены и другие контрпримеры, в большинстве случаев опирающиеся на теорему Гринберга.
Построение
Граф Татта, состоит из трёх одинаковых кусков, так называемых фрагментов Татта. Фрагмент обладает свойством, что из трёх выходящих из него рёбер одно обязательно присутствует в гамильтоновом цикле в любом графе с таким фрагментом. «Обязательные» рёбра фрагмента подходят к центральной вершине. Поскольку любой гамильтонов цикл может использовать лишь два из них, гамильтонова цикла не существует.
Полученный граф является 3-связным и планарным, так что по теореме Штайница этот граф является графом многогранника. Граф имеет 25 граней.
Геометрически может быть получен из тетраэдра (каждая грань которого соответствует четырём большим граням с 9 рёбрами, три из которых находятся между парами фрагментов, а четвёртая образует внешнюю грань) путём многократного отсечения трёх его вершин.
Свойства
- Имеет 46 вершин и 69 рёбер.
- Хроматическое число графа равно 3,
- Хроматический индекс равно 3,
- обхват равен 4
- Диаметр равен 8.
- Граф является 3-связным и планарным. Значит по теореме Штайница этот граф является графом многогранника. (Число граней равно 25.)
- Группа автоморфизмов графа Татта — <math>\Z/3\Z</math>, циклическая группа третьего порядка.
- Характеристический многочлен графа:
- <math>(x-3)(x^{15}-22x^{13}+x^{12}+184x^{11}-26x^{10}-731x^9+199x^8+1383x^7-576x^6-1061x^5+561x^4+233x^3-151x^2+4x+4)^2</math>
- <math>(x^{15}+3x^{14}-16x^{13}-50x^{12}+94x^{11}+310x^{10}-257x^9-893x^8+366x^7+1218x^6-347x^5-717x^4+236x^3+128x^2-56x+4)</math>.
- <math>(x-3)(x^{15}-22x^{13}+x^{12}+184x^{11}-26x^{10}-731x^9+199x^8+1383x^7-576x^6-1061x^5+561x^4+233x^3-151x^2+4x+4)^2</math>
Вариации
Хотя граф Татта является исторически первым 3-регулярным негамильтоновым полиэдральным графом, он не является наименьшим из таковых.
- В 1965 году Ледерберг (Lederberg) нашёл граф с 38 вершинами (граф Барнетта — Босака — Ледерберга)[4][5],
- В 1968 году Гринберг построил ещё несколько контрпримеров для гипотезы Тэйта — графы Гринберга с 42, 44 и 46 вершинами[6], а в 1974 году найдены ещё два таких графа (графы Фолкнера — Янгера) с 42 и 44 вершинами[7]. В 1988 году установлено, что существует в точности шесть негамильтоновых полиэдральных графов с 38 вершинами, имеющих нетривиальные сечения трёх рёбер, они образуются путём замены двух вершин пятиугольной призмы тем же фрагментом, что используется в примере Татта[8].
Примечания
- ↑ Шаблон:Статья. Статья перепечатана в Scientific Papers, Vol. II, pp. 85-98.
- ↑ Шаблон:Статья
- ↑ Шаблон:MathWorld
- ↑ Lederberg, J. «DENDRAL-64: A System for Computer Construction, Enumeration and Notation of Organic Molecules as Tree Structures and Cyclic Graphs. Part II. Topology of Cyclic Graphs.» Interim Report to the National Aeronautics and Space Administration. Grant NsG 81-60. December 15, 1965. [1] Шаблон:Wayback
- ↑ Шаблон:MathWorld
- ↑ Шаблон:Статья
- ↑ Шаблон:Статья
- ↑ Шаблон:Статья
