Математическая культура. Мациевский С.В. - 41 стр.

                         п. 2. Эйлеров граф
    1. Эйлеров граф. Цепь замкнута, если первая вершина цепи совпадает
с последней. Связный граф эйлеров, если ∃ замкнутая цепь, проходящая
через каждое ребро графа. Такая цепь также называется эйлеровой.
    Замечание. По определению цепи, каждое ребро проходится только
один раз, а вершины могут проходиться многократно.
    Если условие замкнутости цепи эйлерова графа необязательно, то такой
граф называется полуэйлеровым. Очевидно, что каждый эйлеров граф яв-
ляется также и полуэйлеровым.
    Примеры.
    1. Три графа: не эйлеров, полуэйлеров и эйлеров.
    Упр. 4. Нарисуйте понятным образом на этих графах эйлерову цепь.
                 2. Эйлер первым решил задачу о кёнигсбергских мостах
              (см. рис. слева): можно ли пройти по всем мостам, пройдя по
              каждому 1 раз? Соединив точки на рисунке ребрами-мостами,
              получим задачу: имеет ли следующий общий граф (т.е. граф,
имеющий петли и параллельные ребра, см. рис. справа) Эйлерову цепь?
    3. Для обвода рисунка не отрывая карандаша от бумаги и не проводя
никакую линию дважды его граф должен быть полуэйлеров.
    4. Существует только один эйлеров граф порядка 3:
    Упр. 5. Нарисуйте единственный эйлеров граф порядка 4 и все четыре
эйлерова графа порядка 5.
    2. Степень вершины графа — число ребер, выходящих из этой вершины.
    Имеет место следующее замечательное утверждение: связный граф тогда
и только тогда эйлеров, когда каждая его вершина имеет четную степень.
    Аналогично доказывается, что связный граф тогда и только тогда полуэй-
леров, когда в нем нечетные степени имеют не более двух вершин. Существу-
ет алгоритм построения эйлеровой цепи в данном эйлеровом графе, т.е. рисо-
вания фигуры не отрывая карандаша от бумаги и не проводя линии дважды.
    Сумма степеней всех вершин всегда четное число, равное удвоенному
числу ребер,— ведь каждое ребро участвует в этой сумме ровно 2 раза.
Этот результат называют леммой о рукопожатиях: если несколько чело-
век обменялись рукопожатиями, то общее число пожатых рук четно. След-
ствие: в любом графе число вершин нечетной степени всегда четно.
    В полуэйлеровом графе с двумя вершинами нечетной степени незамк-
нутая цепь начинается в одной такой вершине и кончается в другой. Полу-
эйлеров граф либо совсем не имеет вершин нечетной степени (и тогда это
эйлеров граф), либо имеет две таких вершины.
    Упр. 6. Имеет ли граф из примера 2 Эйлерову цепь (можно ли пройти по
старым кёнигсбергким мостам, побывав на каждом только 1 раз)? Почему?

                                    40