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

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

Гамильтоновый граф имеет связность не меньше 2. Действительно, все его вершины принадлежат гамильтонову циклу, который двусвязен. Однако, двусвязности недостаточно, чтобы граф был гамильтоновым (см. рис.). Простого критерия для определения, является ли граф гамильтоновым или нет (как, например, для определения эйлеровости графа) не существует. Всё же понятно, что чем больше ребер в графе, чем больше степени вершин графа, тем более вероятно ожидать, что граф является гамильтоновым. В частности, полный граф КN при N ³ 3 очевидно является гамильтоновым. В то же время, существуют гамильтоновы графы и с небольшим числом рёбер, например, циклы СN, N ³ 3.

Известны следующие достаточные (но не необходимые!) условия гамильтоновости.

Теорема (Дирак). Если граф G имеет порядок N ³ 3 и для любой вершины V графа G её порядок deg V ³ N/2, то G является гамильтоновым.

Обобщением этого утверждения является

Теорема (Оре). Если для любой пары несмежных вершин U И V Графа G порядка N ³ 3 сумма их степеней deg V + deg U ³ N, то G гамильтонов.

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

Теорема. Во всяком турнире порядка N ³ 3 существует гамильтонов путь.

< Предыдущая		Следующая >