Дискретная математика

156 условия. Более того, даже для конкретных графов бывает очень трудно иногда практически решить, можно ли найти такой цикл. Приведём некоторые достаточные условия существования гамильтоновых циклов, т.е. условий, при которых граф является гамильтоновым. Пусть граф G имеет п вершин vj, v^, ..., v „ и пусть di~deg(v^, i =\,l,...,n - локальные степени его вершин. Будем считать, что вершины обозначены таким образом, что di<d2 < Можно доказать следующую Теорема 5,20 рСватал, 1972 г.). Пусть граф G имеет п вершин v/, v^, v „, dj<d2 < ...<d„w п >3. Если для любого А: верна импликация dk< к<п/1 ^ ^ п-к, то граф G гамильтонов. Из этой теоремы можно получить следующее нетривиальное следствие. Следствие 5.1. Пусть граф О имеет п вергиин Vi, v^, ..., v „, d; d„ и « >3. Граф G гамильтонов, если выполнено одно из.условий: 1) dk > п/2 для любого А:=1,2,...,?7 (теорема Дирака, 1952); 2) deg(u)+deg(v) >?7 для любых двух различных несмежных вершин и и V графа G (теорема Оре, I960); Ъ) dk > к для любого натурального числа к такого, что 1 < к:^ и/2, Орцикл орграфа, проходящий через каждую его вершину, называется гамильтоновым орцитом. Орграф называется гамильтоновым, если он обладает гамильтоновьш орциклом. Напомним, что через deg^(v) обозначается число дуг, входящих в вершину v, а deg'fv) - число дуг, исходящих из вершины v. Можно доказать следующий аналог теоремы Дирака. Теорема 5.21 (Гуйя-Ури). Пусть G - орсвязный граф с п вершинами. ^ и deg'fv) > и/2 для любой его вершины v, то G - гамильтонов орграф. Твой путь? - переспросила Королева. - Не знаю, что ты хочешь этим сказать! Здесь псе пути мои! Л. Кэрролл § 16. Планарные графы Рассмотрим известную задачу (головоломку) о трех домах и трех колодцах. На одном участке построены три дома и имеется три колодца. Колодцы часто пересыхают, поэтому важно, чтобы от каждого дома имелся