Понятие эйлеров граф. Критерий эйлеровости графа

1.5. Понятие эйлеров граф. Критерий эйлеровости графа.

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

[pic 1]

              А)                                        Б)                               В)

Рисунок 8. А) Эйлеров граф, Б) Полуэйлеров граф В) – граф, не являющийся ни эйлеровым, ни полуэйлеровым.

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

Критерий эйлеровости:

Теорема 1. Чтобы в связанном неориентированном графе G существовал эйлеров цикл, необходимо и достаточно, чтобы число вершин нечетной степени было четным.[6]

Доказательство необходимого условия существования
эйлерового  графа:  

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

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

 Пусть точка А- произвольная вершина графа G (рис.9).

[pic 2] 

Рисунок 9.

Начнём из вершины А путь L по одному из рёбер и продолжим этот путь, каждый раз проходя по новому ребру. Число рёбер конечно, поэтому этот путь обязательно  закончиться, причём в вершине А (на рис. 9 путь L и направление его обхода показаны штриховыми стрелками). Путь L не может закончиться в другой вершине, потому что тогда  все рёбра, принадлежащие этой вершине,  окажутся пройденными по одному разу и их число будет нечётным. Действительно, мы либо зашли в вершину один раз, либо вышли из неё по другому ребру и опять вошли по новому ребру, то есть число рёбер
инцидентных этой вершине равно 3, и т.д.  Этого быть не может, так как степени вершин в нашем графе чётные.

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

Начнём новый путь S из В, будем использовать только рёбра,которые не принадлежат L. Этот путь кончится в В (на рис. 9 путь S обозначен сплошными стрелками). Это доказывается аналогично, как доказывалось, что путь кончится в A.