Для установки нажмите кнопочку Установить расширение. И это всё.

Исходный код расширения WIKI 2 регулярно проверяется специалистами Mozilla Foundation, Google и Apple. Вы также можете это сделать в любой момент.

4,5
Келли Слэйтон
Мои поздравления с отличным проектом... что за великолепная идея!
Александр Григорьевский
Я использую WIKI 2 каждый день
и почти забыл как выглядит оригинальная Википедия.
Статистика
На русском, статей
Улучшено за 24 ч.
Добавлено за 24 ч.
Альтернативы
Недавние
Show all languages
Что мы делаем. Каждая страница проходит через несколько сотен совершенствующих техник. Совершенно та же Википедия. Только лучше.
.
Лео
Ньютон
Яркие
Мягкие

Из Википедии — свободной энциклопедии

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

Построен Уильямом Таттом в 1946 году[3]. Позднее найдены и другие контрпримеры, в большинстве случаев опирающиеся на теорему Гринберга.

Построение

Фрагмент Татта.

Граф Татта, состоит из трёх одинаковых кусков, так называемых фрагментов Татта. Фрагмент обладает свойством, что из трёх выходящих из него рёбер одно обязательно присутствует в гамильтоновом цикле в любом графе с таким фрагментом. «Обязательные» рёбра фрагмента подходят к центральной вершине. Поскольку любой гамильтонов цикл может использовать лишь два из них, гамильтонова цикла не существует.

Полученный граф является 3-связным и планарным, так что по теореме Штайница этот граф является графом многогранника. Граф имеет 25 граней.

Геометрически может быть получен из тетраэдра (каждая грань которого соответствует четырём большим граням с 9 рёбрами, три из которых находятся между парами фрагментов, а четвёртая образует внешнюю грань) путём многократного отсечения трёх его вершин.

Свойства

  • Имеет 46 вершин и 69 рёбер.
  • Хроматическое число графа равно 3,
  • Хроматический индекс равно 3,
  • обхват равен 4
  • Диаметр равен 8.
  • Граф является 3-связным и планарным. Значит по теореме Штайница этот граф является графом многогранника. (Число граней равно 25.)
  • Группа автоморфизмов графа Татта — , циклическая группа третьего порядка.
  • Характеристический многочлен графа:
    .

Вариации

Хотя граф Татта является исторически первым 3-регулярным негамильтоновым полиэдральным графом, он не является наименьшим из таковых.

  • В 1965 году Ледерберг (Lederberg) нашёл граф с 38 вершинами (граф Барнетта — Босака — Ледерберга)[4][5],
  • В 1968 году Гринберг построил ещё несколько контрпримеров для гипотезы Тэйта — графы Гринберга с 42, 44 и 46 вершинами[6], а в 1974 году найдены ещё два таких графа (графы Фолкнера — Янгера) с 42 и 44 вершинами[7]. В 1988 году установлено, что существует в точности шесть негамильтоновых полиэдральных графов с 38 вершинами, имеющих нетривиальные сечения трёх рёбер, они образуются путём замены двух вершин пятиугольной призмы тем же фрагментом, что используется в примере Татта[8].

Примечания

  1. P. G. Tait. Listing's Topologie // Philosophical Magazine (5th ser.). — 1884. — Т. 17. — С. 30–46.. Статья перепечатана в Scientific Papers, Vol. II, pp. 85-98.
  2. W. T. Tutte. On Hamiltonian circuits // Journal of the London Mathematical Society. — 1946. — Т. 21, вып. 2. — С. 98–101. — doi:10.1112/jlms/s1-21.2.98.
  3. Weisstein, Eric W. Tutte's Graph (англ.) на сайте Wolfram MathWorld.
  4. 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] Архивная копия от 20 мая 2014 на Wayback Machine
  5. Weisstein, Eric W. Barnette-Bosák-Lederberg Graph (англ.) на сайте Wolfram MathWorld.
  6. Э. Я. Гринберг. Плоские однородные графы степени три без гамильтоновых циклов. // Латв. матем. ежегодник. — Т. 4. — С. 51-58..
  7. G. B. Faulkner, D. H. Younger. Non-Hamiltonian Cubic Planar Maps. // Discrete Mathematics. — 1974. — Т. 7. — С. 67-74.
  8. D. A. Holton, B. D. McKay. The smallest non-Hamiltonian 3-connected cubic planar graphs have 38 vertices // Journal of Combinatorial Theory, Series B. — 1988. — Т. 45, вып. 3. — С. 305–319. — doi:10.1016/0095-8956(88)90075-5.
Эта страница в последний раз была отредактирована 28 марта 2022 в 11:41.
Как только страница обновилась в Википедии она обновляется в Вики 2.
Обычно почти сразу, изредка в течении часа.
Основа этой страницы находится в Википедии. Текст доступен по лицензии CC BY-SA 3.0 Unported License. Нетекстовые медиаданные доступны под собственными лицензиями. Wikipedia® — зарегистрированный товарный знак организации Wikimedia Foundation, Inc. WIKI 2 является независимой компанией и не аффилирована с Фондом Викимедиа (Wikimedia Foundation).