Теория графов. Пути и циклы Эйлера


Цикл Эйлера – это цикл, включающий все ребра и вершины графа.

Теорема 1.

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

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

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

 1-puti-i-tcikly-eilera

Рисунок 2.14 – Пример собственного эйлерового пути.

Теорема 2.

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

Таким образом, если рассматривать задачу о кенигсбергских мостах (рис. 2.3), то можно сделать вывод, что собственный эйлеровый путь отсутствует, то есть невозможно пройти все мосты за 1 раз не возвращаясь на пройденный мост.

Задача 2.1. Как соединить точки так, чтобы отрезки не пересекались (рис. 2.15).

2-puti-i-tcikly-eilera

Рисунок 2.15 – К задаче 2.1.

а) – Условие; б) – Варианты решения.

Литература:

  1. Шевченко В.В. Конспект лекций по курсу "Логистика". Донецк, ДонНТУ - 2009 г.
  2. Ткачук А.Н. Конспект лекций по курсу "Логистика". Донецк, ДонНТУ - 2008 г.


Категории: Логистика  

Об этой статье

teoriia-grafov-puti-i-tcikly-eilera-avatar
2017-11-02 12:22:27
367
user
Логистика; Лекции; Теория графов;
В статье рассматриваются циклы и пути Эйлера