Граф Татта

Что такое гамильтонов граф.

Посмотрите на следующий рисунок. Попытайтесь отыскать в нём путь, который проходит через каждую вершину только один раз и заканчивается в исходной точке.

Пример простого графа

На данном рисунке найти такой путь совершенно не составляет труда. Например, этот путь может выглядеть так, как показано ниже.

Гамильтонов путь, на предыдущем графе.

Подобного рода рисунки (точки, соединённые ребрами) представляют собой один из способов описания графа. Если на рисунке (в графе) присутствует описанный выше путь, то он называется гамильтоновым циклом (цикл – путь, начинающийся и заканчивающийся в одной вершине), а граф, соответственно, гамильтоновым графом.

Можно дать и более строгие определения.

Гамильтонов граф
граф, содержащий гамильтонов цикл.
Гамильтонов цикл
цикл, проходящий через все вершины графа по одному разу.

В нашем примере мы очень быстро смогли обнаружить гамильтонов цикл. На самом деле, для произвольного графа эта задача является трудноразрешимой. Это означает, что нет простого способа точно сказать, является ли данный граф гамильтоновым или нет.

В качестве развлечения попытайтесь найти гамильтоновы циклы в следующих графах.

Граф головоломки Гамильтона.

Упрощенный граф Татта.

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

Кубический граф
граф, из каждой вершины которого, выходит ровно три ребра.
Планарный граф
граф, который можно изобразить на плоскости без пересечения ребер.

Действительно, если вы попробуете нарисовать планарный кубический граф, то, скорее всего, в нем вы найдёте гамильтонов цикл. Может быть поэтому данная гипотеза просуществовала достаточно долго. Но в 1946 году Уильям Татт построил планарный кубический граф на 46 вершинах, который не является гамильтоновым. Вот как выглядит этот граф.

Граф Татта.

Построение графа Татта. Доказательство отсутствия гамильтонова цикла.

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

Блок Татта. Граф Вольтера.

Этот блок устроен специфическим образом. Невозможно, начав путь в одной из боковых вершин, пройти по всем внутренним вершинам и закончить путь в другой боковой вершине. Всегда, начиная из крайней вершины, мы будем заканчивать свой путь в центральной вершине.

Допустим теперь, что этот кусочек является частью другого графа. Если в этом «большом» графе существует гамильтонов цикл, то он обязательно должен проходить и через все вершины этого блока, иначе какой же это гамильтонов цикл. Учитывая описанное выше интересное свойство этого блока, можно с уверенностью говорить, что гамильтонов цикл «большого» графа если существует, то через наш блок пройдет по одному из следующих вариантов.

Гамильтоновы пути через блок Татта.

Татт объединил три таких блока и легко показал, что в таком случае нельзя обойти этот граф, не побывав в какой-либо вершине дважды. Проверим это самостоятельно. Рассмотрим упрощенную схему графа Татта, а именно, заменим каждый блок Татта на соответствующую развилку.

Схема замены блока Татта, на развилку.

Получим следующую схему

Упрощенный граф Татта.

В этой схеме уже учтена особенность каждого блока Татта. Начиная путь из любой боковой вершины, и посетив все внутренние вершины по одному разу, мы обязательно закончим путь в центральной вершине. И наоборот, если начнем путь в центральной вершине, то при условии, что мы обошли все вершины по одному разу, закончим свой путь мы в одной из боковых вершин.

А теперь, если еще не пробовали, то попробуйте найти в этом графе гамильтонов цикл. Уверен, у вас это не получится.

Несколько позже были найдены примеры других графов, которые являются кубическими планарными графами, но не являются при этом гамильтоновыми. На данный момент, граф Barnette-Bośak-Lederberg является наименьшим по количеству вершин контрпримером гипотезы П. Тэта. В графе Barnette-Bośak-Lederberg (BBL) 38 вершин.

Назад к разделу
К списку предметов
На главную