Таблицы Брадиса

Какие из следующих графов эйлеровы?

Какие из следующих графов эйлеровы?

Элементы математики в задачах - Г. А. Мерзон

Задача 15. На рисунке изображена схема расположения мостов в городе Кёнигсберге XVIII века. Можно ли совершить прогулку так, чтобы пройти по каждому мосту ровно один раз?

 

140                                    Теория графов 1

Решение. Пусть наша прогулка не начиналась и не закончилась на острове X. Заметим, что впервые пройдя через него, мы восполь­зовались двумя выходящими из X мостами (по одному пришли, по другому ушли). Но это значит, что воспользоваться оставшимся вы­ходящим из X мостом мы уже не могли, иначе на X прогулка бы закончилась.

Определение 8. Граф называется эйлеровым, если в нем существует цикл, проходящий по каждому ребру ровно один раз.

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

Задача 16. Какие из следующих графов эйлеровы?

 

Решение. Первый граф не является эйлеровым по соображениям, аналогичным задаче 15. Один из возможных обходов второго графа ^         изображен на рисунке:

 

Задача 17. Докажите, что граф эйлеров тогда и только тогда, когда он связен и степень каждой его вершины четна.

Решение. Докажем сначала, что в эйлеровом графе степень каждой вершины четна. Для этого рассмотрим произвольную вершину наше­го графа. Аналогично задаче 15, посмотрим на то, сколько раз эйлеров цикл входит в эту вершину и сколько раз из нее выходит. Заметим, что эти числа равны: каждый раз, входя в вершину по какому-то ребру, мы из нее выходим по какому-то другому. При этом, если цикл начинается в рассматриваемой вершине, то первому «выходу» из вершины надо поставить в соответствие последнее «возвращение». Следовательно, степень вершины четна. В силу произвольности вы­бора вершины, степени всех вершин четны.