П. 2. Эйлеров граф

1. Эйлеров граф. Цепь замкнута, если первая вершина цепи совпадает с последней. Связный граф эйлеров, если $ замкнутая цепь, проходящая через каждое ребро графа. Такая цепь также называется эйлеровой.

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

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

Примеры.

1. Три графа: не эйлеров, полуэйлеров и эйлеров.

Упр. 4. Нарисуйте понятным образом на этих графах эйлерову цепь.

2. Эйлер первым решил задачу о кёнигсбергских мостах (см. рис. слева): можно ли пройти по всем мостам, пройдя по каждому 1 раз? Соединив точки на рисунке ребрами-мостами, получим задачу: имеет ли следующий общий граф (т.е. граф, имеющий петли и параллельные ребра, см. рис. справа) Эйлерову цепь?

3. Для обвода рисунка не отрывая карандаша от бумаги и не проводя никакую линию дважды его граф должен быть полуэйлеров.

4. Существует только один эйлеров граф порядка 3:

Упр. 5. Нарисуйте единственный эйлеров граф порядка 4 и все четыре эйлерова графа порядка 5.

2. Степень вершины графа — число ребер, выходящих из этой вершины.

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

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

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

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

Упр. 6. Имеет ли граф из примера 2 Эйлерову цепь (можно ли пройти по старым кёнигсбергким мостам, побывав на каждом только 1 раз)? Почему?

П. 3. Дерево

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

v     w   y   x   z

Цикл длины три называется треугольником.

Пример. На рисунке имеются следующие цепи:

1) цепь v ® w ® x ® y ® z ® x;

2) простая цепь v ® w ® x ® y ® z;

3) замкнутая цепь v ® w ® x ® y ® z ® x ® v;

4) цикл v ® w ® x ® y ® v;

5) треугольник v ® w ® x ® v.

2. Дерево. Лесом называется граф, не содержащий циклов. Связный лес называется деревом.

Граф является деревом тогда и только тогда, когда любые две его вершины соединены ровно одной простой цепью.

Очевидно, что дерево не содержит циклов, но, добавляя к нему 1 ребро, получаем ровно 1 цикл.

Дерево порядка n имеет n – 1 ребро.

Примеры.

1. Существуют только два дерева порядка 4, и только три — порядка 5.

Упр. 7. Нарисуйте все 6 деревьев порядка 6.

2. Задача о соединении городов. Соединить города железными дорогами так, чтобы были соединены любые два города при минимальной длине железных дорог. Решением этой задачи является дерево. Имеется алгоритм для его построения.

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

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

Граф полный, если в нем любые две вершины смежны. Полный граф порядка n обозначается Kn. Граф K 5не планарен, поскольку его нельзя нарисовать на плоскости без пересечений ребер.

Пример. Изоморфные полные планарные графы порядка 4. Первый из этих графов не плоский.

Упр. 8. Нарисуйте на плоскости полный граф K 5.

Каждый подграф планарного графа планарен.

Граф, имеющий непланарный подграф, непланарен.