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

Изучаемое понятие связано с существованием в графе цикла, проходящего ровно один раз через каждую вершину. Граф называется гамильтоновым, если в нем такой цикл существует и полугамильтоновым. если существует путь, проходящий через каждую вершину точно один раз. Ясно, что это определение можно распространить на ориентированные графы, если путь считать ориентированным. В отличие от эйлеровых графов, где имеется критерий для графа быть эйлеровым, для гамильтоновых графов такого критерия нет. Большинство известных фактов имеет вид: " если граф G имеет достаточное количество ребер, то граф является гамильтоновым". Приведем одну из таких теорем, известную как теорема Дирака.

Теорема 1. Пусть в графе G(V, E) с n вершинами (n 3) выполняется условие d(v) для любого v V. Тогда граф G является гамильтоновым.

Заметим сначала следующее. Если к любому графу G добавить некоторое количество новых вершин, соединяя каждую из них с каждой вершиной графа, то мы получаем гамильтонов граф G'. Пусть мы добавили к графу G(V, E) минимальное число k новых вершин, k> 0, после чего граф стал гамильтоновым. Рассмотрим гамильтонов цикл

v₁, w, v₂,..., v₁ в графе G', где v_i V, w - одна из новых вершин. Следовательно v₂, не является смежной с v₁ в графе G, поскольку тогда мы могли не использовать вершину w, что противоречило бы минимальности числа k. Далее, пусть вершина v₂' смежная с v₂, а v₁' - смежная с v₁. Тогда v₁' не может следовать за v₁' в цикле. Действительно, в этом случае цикл v₁, w, v₂,..., v₁', v₂',..., v₁ можно заменить на v₁, v₁',..., v₂, v₂',..., v₁ и снова высвободить вершину w. Значит, число вершин графа G', не являющихся смежными с v₂, не меньше числа вершин, смежных с v₁, поскольку на гамильтоновом цикле за любой вершиной, смежной с v₁, следует вершина, не смежная с v₂. Число вершин, смежных с v₁, не меньше, чем +k, то же и для вершины v₂. Далее, поскольку любая вершина графа G' является либо смежной, либо не смежной вершине v₂, то, значит, общее число вершин n+k не меньше, чем 2( + k) = n+ 2k. Полученное противоречие показывает, что k=0, т.е. исходный граф гамильтонов.

Приведем примеры гамильтоновых графов.

1. Полный граф K_n гамильтонов.

2. Граф единичного куба В_n гамильтонов.

3. Определим ориентированный граф Г(S_n) - вершинами которого являются n! перестановок. При этом от перестановки s₁ к перестановке s₂ идет дуга, если существует транспозиция, переводящая перестановку s₁ в s₂. Полученный граф Г(S_n)является гамильтоновым.

В качестве примера приведем граф Г(S₃):

Из предыдущего следует, что многие важные прикладные задачи сводятся к построению гамильтонова цикла некоторого графа. Учитывая важность задачи перечисления перестановок. приведем еще один такой алгоритм на языке построения гамильтонова цикла в Г(S_n). Алгоритм построения цикла опишем индуктивно. Пусть L_n - список всех перестановок символов 1, 2,..., n. Обозначим через L_n(i)(l i n+1) множество перестановок символов 1,..., i-l, i+l,..., n+1, полученных следующим образом: L_n(n+l)= L_n и L_n(i), (1 i n) получено из L_n(i+l) заменой всех появлений i на i+1. Тогда положим

_Ln+1=L_n(n+l) (n+l), (n), L_n(n-l) (n-l), (n-2),... (4) Здесь символ означает, что в списке все перестановки из L_n(i) дополняются дописыванием справа элемента i. Список - это список L_n(i), написанный в обратном порядке. Нетрудно показать индукцией по n, что таким образом построенная последовательность перестановок содержит каждую перестановку точно один раз и каждая последующая перестановка отличается от предыдущей одной транспозицией.

Пример, n = 3 Имеем:

L₂(3): (12) (21)

L₂(2): (13) (31)

L₂(l): (23) (32)

L₃ = L₂(3) 3, L2(2)v2, L2(l)v 1 =

- (123) -> (213) -> (312) -^ (132) -> • (231) -> (321).

Понятие " почти все" графы.

Пусть G(n) - множество всех графов на множестве вершин

V-{1, 2,..., n}. Пусть Р - некоторое свойство, которым каждый граф из G(n) может обладать или нет. Пусть G_p(n) - множество тех графов из G(n), которые обладают свойством Р.

Говорят, что почти все графы обладают свойством Р, если

и почти нет графов со свойством Р, если

В качестве примера использования данного понятия докажем один результат.

Теорема. Почти нет эйлеровых графов.

Пусть G₁(n) - множество эйлеровых графов, G(n) - множество всех графов, G₂(n) - множество графов, вершины которых имеют четную степень. По теореме Эйлера имеем, т.к. в G₂ не учтена связность.

Ясно, что графы из G₂(n) можно получить из графов G(n- 1) добавлением новой вершины и соединением ее со всеми вершинами нечетной степени.

Имеем

Отсюда получаем, что

|G₂(n)|-0(|G(n)|) и

|G₁(n)|-0(|G(n)|)

что и доказывает утверждение.

Отметим без доказательства другие утверждения такого типа.

Теорема. Почти все графы связны.

Теорема. Диаметры почти всех графов равны 2.

Теорема. Почти все графы гамильтоновы.

Теорема. Множество автоморфизмов почти каждого графа состоит из одного тождественного автоморфизма.