Эйлеровы графы

Эйлерова цепь – замкнутая цепь в графе G, если она содержит все вершины и все ребра графа.

Эйлеров граф– граф, содержит эйлерову цепь.

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

Теорема: Для неодноэлементного связного графа G следующие условия эквивалентны:

1. G – эйлеров граф;

2. Любая вершина графа G имеет четную степень;

3. Множество всех ребер графа G можно разбить на циклы.

Следствие: Пусть граф G содержит 2l вершин нечетной степени и l ≥1, тогда множество всех ребер графа можно разбить на l цепей, каждая из которых соединяет две вершины нечетной степени.

Полуэйлерова цепь в графе G – если она содержит все вершины и все ребра графа.

Полуэйлерова граф – 1. если в нем существует полуэйлерова цепь;

2. связный граф, в котором имеется цепь, проходящая через каждое ребро ровно один раз.

Утверждение: связный граф G является полуэйлеровым графом тогда и только тогда, когда граф G содержит не более двух вершин нечетной степени.

Следствие: Пусть связный граф G содержит две вершины нечетной степени U и V, тогда

существует (U,V) цепь, содержащая все ребра графа G.

Граф ,произвольновычерчиваемый из вершины V – если любая его цепь с началом в вершине V может быть продолжена до эйлеровой цепи графа G.

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

План построения графа, произвольновычерчиваемого из вершины V:

Возьмем произвольный лес h, любую вершину нечетной степени из h, соединим нечетным число числом кратных ребер с вершиной V, а любую вершину четной степени – четным числом ребер (ø не исключается). Причем любую изолированную вершину из h обязательно соединим с V. Кроме того, к вершине V можно присоединить несколько петель. Получили граф G, который связен, имеет только вершины четной степени, является произвольно вычерчиваемым из вершины V. В таком графе мы можем построить эйлерову цепь: выходим из вершины V и идем произвольным образом по маршруту, соблюдая лишь одно ограничение: из каждой достигнутой вершины только по любому из непройденных ранее ребер, причем движемся до тех пор, пока это будет возможно.