logo search
лекции по МОТС / ДИСКРЕТНАЯ МАТЕМАТИКА Графы

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

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

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

ТЕОРЕМА Если граф G связен и нетривиален, то следующие утверждения экви­валентны:

G — эйлеров граф;

каждая вершина G имеет четную степень;

множество ребер G можно разбить на простые циклы.

доказательство

1 => 2 Пусть Z — эйлеров цикл. Двигаясь по Z, будем подсчитывать степе-

ни вершин, полагая их до начала прохождения нулевыми. Прохождение каждой вершины вносит 2 в степень этой вершины. Поскольку Z содер­жит все ребра, то когда обход Z будет закончен, будут учтены все ребра, а степени всех вершин — четные.

2 => 3 G — связный и нетривиальный граф, следовательно, Vv d(v) > 0. Степени

вершин четные, следовательно, Vv d(v) ^ 2. Имеем:

2q = d(v) ^ 2р

^ р => q > р - 1.

Следовательно, граф G — не дерево, а значит, граф G содержит (хотя бы один) простой цикл Z\. (Zi — множество ребер.) Тогда G - Z\ -остовный подграф, в котором опять все степени вершин четные. Исклю­чим из рассмотрения изолированные вершины. Таким образом, G - Zi тоже удовлетворяет условию 2, следовательно, существует простой цикл Z2 С (G—Zi). Далее выделяем циклы Zi, пока граф не будет пуст. Имеем: Е = Zi и П Zi = 0.

3 =4> 1 Возьмем какой-либо цикл Z\ из данного разбиения. Если Zi = Е, то теорема доказана. Если нет, то существует цикл Z%, такой что

3ui (vi e Zi&v-i е Z2),

так как G связен. Маршрут Z\ U Z2 является циклом и содержит все свои ребра по одному разу. Если Z\ U Z2 = Я, то теорема доказана. Если нет, то существует цикл Z3, такой что Зи2 (г;2 € Zi U Z2&i;2 G Z3). Далее будем наращивать эйлеров цикл, пока он не исчерпает разбиения. П