Гамильтонов граф и условия его существования

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

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

Следует иметь в виду, что понятия эйлерова графа и гамильтонова графа не зависят друг от друга. Граф может быть эйлеровым и гамильтоновым одновременно (рис. 3.18, а), эйлеровым, но не быть гамильтоновым (рис. 3.18, б), гамильтоновым и не эйлеровым (рис. 3.18, в), наконец, не быть ни тем, ни другим (рис. 3.18, г).

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

Рис. 3.18.

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

Пусть полный ориентированный граф F содержит n вершин. Тогда при построении гамильтоновой цепи первую вершину в нем можно выбрать n способами, вторую - n-1 способами,..., n-ю - 1 способом. В соответствии с правилом произведения в полном орграфе с n вершинами существует n! различных гамильтоновых цепей.

Поскольку начало цикла не фиксируется, т.е. все маршруты, получающиеся друг из друга циклическим сдвигом, считаются одним и тем же циклом, то гамильтоновых циклов в полном орграфе будет в n раз меньше, чем цепей, т.е. (n-1)!.

Для неориентированного графа цепей (циклов) имеется в 2 раза меньше, чем для орграфа.

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

1. Если граф F гамильтонов, то он связный.

 Предположим, что F не является связным. Значит, в нем найдется такая пара вершин v’ и v”, что в F не существует соединяющего их маршрута, а следовательно, в F не удастся построить цикл, проходящий через все его вершины, т.е. граф F - не гамильтонов. 

2. Если граф F гамильтонов, то в нем отсутствуют точки сочленения.

 Предположим, что в гамильтоновом графе F есть точка сочленения. Обозначим ее v₀. Так как F - гамильтонов, то в нем можно построить гамильтонов цикл с началом и концом в этой точке v₀: С=(v₀,v₁,v₂,...,v_n-1,v₀).

Поскольку v₀ - точка сочленения, то, удалив ее из графа F,получим вместо F граф F’ с компонентами связности F₁,F₂,...,F_m, где m³2.

По определению гамильтонова цикла v₀¹v₁¹v₂¹...¹v_n-1, следовательно, после удаления вершины v₀ и инцидентных ей ребер от цикла С в графе F’ останется (v₁,v₂,...,v_n-1) - цепь, соединяющая все вершины графа F’. Это означает, что F’ - связный граф, т.е. он имеет одну компоненту связности: m=1.