Теория графов. Пути и циклы Эйлера
Цикл Эйлера – это цикл, включающий все ребра и вершины графа.
|
Теорема 1. |
Граф более чем с одной вершиной имеет цикл Эйлера тогда и только тогда, когда он связный и каждая его вершина имеет четную степень. |
Вернемся к задаче о кенигсбергских мостах (рис. 2.3). В данной задаче невозможно пройти все вершины, не проходя по данному мосту несколько раз.
Как говорилось выше, путь Эйлера – это путь, который включает каждое ребро графа только один раз. Если эйлеровый путь не является эйлеровым циклом, то он называется собственным эйлеровым путем.
Рисунок 2.14 – Пример собственного эйлерового пути.
|
Теорема 2. |
Граф имеет собственный эйлеровый путь тогда и только тогда, когда он связный и ровно две его вершины имеют четную степень. |
Таким образом, если рассматривать задачу о кенигсбергских мостах (рис. 2.3), то можно сделать вывод, что собственный эйлеровый путь отсутствует, то есть невозможно пройти все мосты за 1 раз не возвращаясь на пройденный мост.
Задача 2.1. Как соединить точки так, чтобы отрезки не пересекались (рис. 2.15).
Рисунок 2.15 – К задаче 2.1.
а) – Условие; б) – Варианты решения.
Литература:
- Шевченко В.В. Конспект лекций по курсу "Логистика". Донецк, ДонНТУ - 2009 г.
- Ткачук А.Н. Конспект лекций по курсу "Логистика". Донецк, ДонНТУ - 2008 г.
Популярные рубрики
Популярные теги
