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

Название «uамильтонов граф» произошло от задачи «кругосветное путешествие», придуманной Гамильтоном в 19 веке. Нужно обойти все вершины графа, изображенного на рисунке,

по одному разу и вернуться в исходную точку.

Р ис. 20

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

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

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

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

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

Теорема 1. В полном, конечном графе (любая пара вершин которого соединена хотя бы в одном направлении) всегда существует гамильтонов цикл.

Теорема 2. Если для любой пары несмежных вершин v_i и v_j графа G с n вершинами справедливо неравенство d(v_i)+d(v_j)n , то граф обладает гамильтоновым циклом.

Теорема 3. Граф G с n вершинами имеет гамильтонов цикл, если для любой вершины v_i выполняется неравенство d(м_i)n\2,где n – число вершин в графе.

5.4. Оценки числа эйлеровых и гамильтоновых графов

Теорема. В любом графе число вершин нечетной степени всегда четно.

Доказательство: По теореме Эйлера , Это значит, что сумма степеней всех вершин графа есть четное число. Сумма степеней вершин чётной степени также чётна следовательно будет чётна сумма степеней вершин нечётной степени. Это значит, что их число четное.

Пусть G(n) есть множество всех возможных графов с n вершинами, E(n) – множество эйлеровых графов с n вершинами. Можно показать, что , т.е. эйлеровых графов почти нет. С другой стороны почти все графы – гамильтоновы, так как. , где H(p) – множество гамильтоновых графов с n вершинами.

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

6. Фундаментальные циклы и разрезы

6.1. Фундаментальные циклы

Пусть G=(V, E) – неорграф , имеющий n вершин и m ребер и c – компонент связности. Пусть Т – остов графа G. Остов имеет n-c ребер, обозначенных как . Эти ребра называются ветвями остова Т. Оставшиеся m-n+с ребер , не входящие в остов Т, называются хордами остова Т. Если к лесу Т добавить произвольную хорду v_i, то в полученном графе образуется ровно один простой цикл, обозначенный C_i. Этот цикл состоит из некоторых ветвей остова Т и хорды v_i. В этом случае цикл C_i называется фундаментальным циклом графа G относительно хорды v_i остова Т.

Множество всех фундаментальных циклов, относительно хорд остова Т, называется фундаментальным множеством циклов графа G, относительно остова Т. Мощность фундаментального множества циклов не зависит от выбора остова Т и равна цикломатическому числу ν(G)=m-n+c.

Обозначим через (₁, ₂, …, _m) последовательность (v₁, v₂, …, v_m-n+c, u₁, u₂, …, u_n-c) всех ребер графа G. Тогда фундаментальному циклу C_i соответствует вектор , координаты которого определяются по правилу:

Таким образом, фундаментальное множество циклов задается с помощью матрицы фундаментальных циклов, строки которой являются векторами :

.

Так как, каждый фундаментальный цикл C_i содержит ровно одну хорду v_i, то матрица С имеет следующий вид:

.

Таким образом, , где С₁ – единичная матрица, порядка v(G).

Пример. Найти матрицу фундаментальных циклов графа G, изображенного на рисунке

Р ис. 21

Цикломатическое число графа - v(G)=m-n+c=8-6+1=3.

Следовательно, для получения остова, необходимо удалить из графа три ребра. Пусть этими ребрами будут 1, 2, 3 (удаляем так, чтобы в остове не было циклов). Ребрами, входящими в остов, присваиваются номера 4, 5, 6, 7, 8. Они на рисунке изображены жирными линиями. В результате фундаментальный цикл С₁, соответствующий хорде 1, состоит из ребер 1, 4 и 6. Цикл С₂ – из рёбер 2, 6, 7; цикл :С₃ – из рёбер 3, 6, 7, 8. В результате этого, матрица фундаментальных циклов будет иметь вид: