Гамильтоновы цепи и циклы

В 1857 году математик Гамильтон придумал игру «Кругосветное путешествие». Она включала додекаэдр (правильный многогранник), двенадцать граней которого представляли собой равные правильные пятиугольники. В каждой из двадцати вершин тела просверливалась дырка, в которую вставлялся колышек, изображавший город (столицу). Используя верëвку, требовалось найти путь через города, посетив каждый город один раз, и вернуться в исходный город. Додекаэдр на плоскости изображается так, как показано на рис. 21.

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

Определение 12.1. Простая цепь (цикл) в псевдографе G называется гамильтоновой (гамильтоновым), если она (он) проходит через каждую вершину псевдографа G.

Рис. 21 Определение 12.2. Псевдограф, у которого есть гамильто-

нов цикл, называется гамильтоновым графом.

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

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

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

Планарные графы

В замечании 3.1 отмечалось, что граф с точностью до изоморфизма можно изобразить разными диаграммами. На практике при изготовлении микросхем возникает задача изображения схемы радиоэлектронного устройства, представляющей собой граф, на плоскости так, чтобы проводники не пересекались. Аналогичная задача возникает при проектировании железнодорожных и других путей, где нежелательны переезды.

Таким образом, возникает потребность введения понятия плоского графа.

Определение 13.1. Плоским называется граф, вершины которого являются точками плоскости, а рëбра – непрерывными плоскими линиями без самопересечений, причëм никакие два ребра не имеют общих точек, кроме, быть может, инцидентной им обоим вершины.

Определение 13.2. Планарным называется любой граф, изоморфный плоскому графу.

Все планарныеграфы укладываются на плоскости (имеют плоскую укладку).

Пример 13.1. На рис. 22 изображëн планарный граф G и изоморфный ему плоский граф (плоская укладка графа G). 

Очевидно, что следующие утверждения справедливы:

1) любой подграф планарного графа планарен;

2) граф планарен тогда и только тогда, когда каждая связная компонента этого графа является планарным графом. 

Определение 13.3. Гранью плоского графаназывается множество точек плоскости, каждая пара которых может быть соединена плоской кривой, не пересекающей рëбер этого графа.

Определение 13.4. Границей грани плоского графаназывается множество вершин и рëбер, принадлежащих этой грани.

Пример 13.2. Плоский граф на рис. 22 имеет пять граней: Г₁, Г₂, Г₃, Г₄, Г₅. Неограниченная грань Г₁ называется внешней, а остальные грани: Г₂, Г₃, Г₄, Г₅ – внутренними. 

Теорема 13.1 (Эйлера). Пусть G = (S, U) – связный планарный граф порядка n и = n, = m, f – число граней плоского графа. Тогда справедливо равенство

(13.1)

Доказательство. Пусть G ¢ – некоторый остов графа G. Он имеет всего одну внешнюю грань, n вершин и (n – 1) ребер, поэтому формула (13.1) для остова

G ¢ выполняется. Будем поочерëдно добавлять к остову G ¢ недостающие ребра графа G. При каждом добавлении число вершин не изменится, число ребер и число граней увеличится на единицу.

Таким образом, формула (13.1) будет верна для всякого графа, получающегося в результате таких операций, а поскольку графом G заканчивается вся эта процедура, то формула (13.1) будет верна и для него. 

Известны несколько критериев планарности графа. Для формулировки одного из них введëм понятие гомеоморфизма графов.

Определение 13.5. Два графа называются гомеоморфными, если они могут быть получены из одного и того же графа подразбиением его рëбер.

На рис. 23 изображëн исходный граф G и два гомеоморфных графа G₁ и G₂.

Теорема 13.2 (Понтрягина – Куратовского). Граф планарен тогда и только тогда, когда он не содержит подграфов, гомеоморфных K₅ или K_3,3. 

Следующая теорема представляет собой эквивалентную формулировку критерия планарности 13.2.

Теорема 13.3. Граф планарен тогда и только тогда, когда в нëм нет подграфов, стягиваемых к графам K₅ или K_3,3. 

Для непланарных графов вводятся характеристики, представляющие ту или иную меру непланарности.

Определение 13.6. Искажëнностью sk (G)графа G или числом планарности называется наименьшее число рëбер, удаление которых приводит к планарному графу.

Для полного графа порядка n справедлива следующая формула:

(13.2)

Определение 13.7. Толщиной t (G) графа G называется наименьшее число планарных подграфов графа G, объединение которых даëт сам граф.

Толщина графа равна минимальному числу плоскостей k, при котором граф G разбивается на плоские части G₁, G₂,…, G_k.

Очевидно, что толщина планарного графа равна единице. Для полного графа порядка n справедлива следующая формула:

t (K_n) = (13.3)