Свойства маршрутов, цепей и циклов

• 1) Всякий незамкнутый (u, v) — маршрут, содержит в себе простую (u, v) — цепь. Вчастности, любая (u, v) — цепь, содержит в себе простую (u, v) — цепь. Причем, если (u, v) — маршрут содержит в себе вершину w (w?u и w? v), то в общем случае, простая (u, v) — цепь может не содержать в себе вершину w.
• 2) Всякий непростой цикл можно разбить на два или более простых. Причем для замкнутого маршрута такое утверждение не верно.
• 3) Всякая непростая (u, v) — цепь, может быть разбита на простую (u, v) — цепь и один или более простых циклов. Причем для незамкнутого маршрута такое утверждение не верно.
• 4) Для любых трех вершин u, w, v из существования (u, w) — цепи их и (w, v) — цепи, следует существование (u, v) — цепи. Причем может не существовать (u, v) — цепи, содержащей вершину w.
• 5) Объединение двух несовпадающих простых (u, v) — цепей содержит простой цикл.
• 6) Если граф содержит 2 несовпадающих цикла с общим ребром e, то после удаления этого ребра граф по-прежнему содержит цикл.

Понятие гамильтонова графа. Теорема Дирака

Граф называется гамильтоновым, если в нем имеется простой цикл, содержащий каждую вершину этого графа. Сам этот цикл также называется гамильтоновым. Гамильтоновой называют и простую цепь, содержащую каждую вершину графа. Слово «гамильтонов» в этих определениях связано с именем известного ирландского математика У. Гамильтона, которым в 1859 году предложена следующая игра «Кругосветное путешествие». Каждой из 20 вершин додекаэдра (рис. 1) приписано название одного из крупных городов мира.

рис. 2.

Требуется, переходя от одного города к другому по ребрам додекаэдра, посетить каждый город в точности один раз и вернуться в исходный город.

Теорема Оре (О.Оре, 1960). Если для любой пары u и v несмежных вершин графа G порядка n?3 выполняется неравенство deg u+deg v? n, то G — гамильтонов граф.

Теорема Дирака (следствие теоремы Оре) (Г.Дирак, 1952 г.). Если |G|=n?3 и для любой вершины v графа G выполняется неравенство deg v? n/2, то G — гамильтонов граф.

Лемма (о длине цикла) Пусть — произвольный неориентированный граф и — минимальная степень его вершин. Если, то в графе существует цикл длиной .

Доказательство:

Рассмотрим путь максимальной длины. Все смежные с вершины лежат на. Обозначим. Тогда. Цикл имеет длину.

Доказательство теоремы Дирака Пусть — цикл наибольшей длины в графе. По лемме его длина. Если — гамильтонов, то теорема доказана. Предположим обратное, т. е.. Рассмотрим путь наибольшей длины. Заметим, что по условию, а значит и каждая вершина из смежна с некоторыми вершинами из. Заметим, что вершина не может быть смежна:

• · с вершинами из, расстояние от которых до (по) не превышает m. Действительно, пусть вершина и расстояние от до по циклу меньше либо равно. Тогда этот участок цикла можно заменить на, длина которого. Таким образом образуется цикл большей длины, что противоречит предположению о максимальности цикл .
• · двум смежным вершинам на. Пусть и. Тогда заменив ребро на, увеличим длину цикла на .
• · вершинам из, поскольку максимальный.

Получаем .

Противоречие.

граф теорема коммивояжер