Дискретная математика: графы и автоматы. Альпин Ю.А - 10 стр.

UptoLike

ВУЗ: 

КФУ | Казань

Составители: 

Рубрика: 

10 Глава 1. Неориентированные графы
Эйлера, где из уважения к исторически первой задаче теории графов
допускаются кратные рёбра.
§ 2. Эйлеровы и гамильтоновы графы
Теория графов началась со следующей задачи о кёнигсбергских
мостах, поставленной и решённой Эйлером. В этом городе семь мо-
стов переброшены через реку Прегель, как показано на карте ниже.
Рис. 3
Спрашивается, можно ли, выйдя из дома, вернуться обратно, пройдя
по каждому мосту ровно один раз? Граф, отображающий математи-
ческое существо задачи, изображен на рис. 3 рядом с картой.
Общая задача будущей теории графов, поставленная Эйлером,
формулируется так: при каких условиях связный граф содержит
цикл, проходящий через каждое его ребро?
Цикл, проходящий через все рёбра графа, называют эйлеровым,
а граф, содержащий эйлеров цикл, — эйлеровым графом.
Для решения задачи потребуется новое понятие. Назовём степе-
нью вершины количество инцидентных ей рёбер.
Теорема 1 (Эйлер, 1736 г). Связный граф содержит эйле-
ров цикл тогда и только тогда, когда степень каждой его вершины
есть чётное число.
Д о к а з а т е л ь с т в о. Необходимость. Пусть эйлеров цикл суще-
ствует. Будем проходить по нему, удаляя из графа пройденные рёбра.
Ясно, что при входе в вершину её степень уменьшается на единицу,
а при выходе — ещё на единицу, то есть, при проходе через вершину
из её степени вычитается двойка. Когда все рёбра цикла пройдены,
остаётся пустой граф: степень каждой вершины равна нулю. Таким
образом, степень каждой вершины исходного графа есть сумма двоек,
то есть, чётное число.
Достаточность. Начиная с произвольно выбранной вершины v,
строим маршрут, соблюдая единственное правило: не проходить два-
10                                        Глава 1. Неориентированные графы


Эйлера, где из уважения к исторически первой задаче теории графов
допускаются кратные рёбра.

             § 2. Эйлеровы и гамильтоновы графы

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




                                 Рис. 3

Спрашивается, можно ли, выйдя из дома, вернуться обратно, пройдя
по каждому мосту ровно один раз? Граф, отображающий математи-
ческое существо задачи, изображен на рис. 3 рядом с картой.
    Общая задача будущей теории графов, поставленная Эйлером,
формулируется так: при каких условиях связный граф содержит
цикл, проходящий через каждое его ребро?
    Цикл, проходящий через все рёбра графа, называют эйлеровым,
а граф, содержащий эйлеров цикл, — эйлеровым графом.
    Для решения задачи потребуется новое понятие. Назовём степе-
нью вершины количество инцидентных ей рёбер.
    Теорема 1 (Эйлер, 1736 г). Связный граф содержит эйле-
ров цикл тогда и только тогда, когда степень каждой его вершины
есть чётное число.
    Д о к а з а т е л ь с т в о. Необходимость. Пусть эйлеров цикл суще-
ствует. Будем проходить по нему, удаляя из графа пройденные рёбра.
Ясно, что при входе в вершину её степень уменьшается на единицу,
а при выходе — ещё на единицу, то есть, при проходе через вершину
из её степени вычитается двойка. Когда все рёбра цикла пройдены,
остаётся пустой граф: степень каждой вершины равна нулю. Таким
образом, степень каждой вершины исходного графа есть сумма двоек,
то есть, чётное число.
    Достаточность. Начиная с произвольно выбранной вершины v,
строим маршрут, соблюдая единственное правило: не проходить два-

Страницы