АкушерствоАнатомияАнестезиологияВакцинопрофилактикаВалеологияВетеринарияГигиенаЗаболеванияИммунологияКардиологияНеврологияНефрологияОнкологияОториноларингологияОфтальмологияПаразитологияПедиатрияПервая помощьПсихиатрияПульмонологияРеанимацияРевматологияСтоматологияТерапияТоксикологияТравматологияУрологияФармакологияФармацевтикаФизиотерапияФтизиатрияХирургияЭндокринологияЭпидемиология

ОПРЕДЕЛЕНИЕ. Цикл в графе Gназывается циклом Эйлера, если он проходит через все ребра графа и каждое ребро проходится один раз.

Прочитайте:
  1. I. Доход от прироста стоимости при реализации ценных бумаг (инвестор самостоятельно несет ответственность за определение и выплату налогов в бюджет Республики Казахстан)
  2. I. ОПРЕДЕЛЕНИЕ ОСНОВНЫХ ТЕРМИНОВ
  3. I. Определение СКФ по клиренсу креатинина
  4. II. Договорные отношения могущие влиять на определение управомоченного лица
  5. А. Определение группы крови стандартными изогемагглютинирующими сыворотками.
  6. Аборты. Определение, классифиация, диагностика и профилактика.
  7. Ангины: 1) определение, этиология и патогенез 2) классификация 3) патологическая анатомия и дифференциальная диагностика различных форм 4) местные осложнения 5) общие осложнения
  8. Антигены. Определение. Свойства. Виды.
  9. Асептика, антисептика. Определение понятий. Способы проведения.
  10. Б. Определение группы крови с помощью цоликлонов (моноклональных антител)

Цикл в графе G называется циклом Эйлера, если он проходит через все ребра графа и каждое ребро проходится один раз.

 

Например, для графа G, изображенного на рис. 5.17., имеется цикл Эйлера, а граф G 1 такого цикла не имеет.

 

 
 


G G 1

 

Рис. 5.17

Для тривиального графа, состоящего из единственной вершины, цикл Эйлера - это цикл длины 0 или цикл, состоящий из единственной вершины.

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

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

 

А A


B C

B C

 


D D

 

Рис. 5.18.

 

Для графа, представленного на этом рисунке задача прохождения по мостам трансформируется в задачу нахождения цикла Эйлера в соответствующем графе. Заметим, что структура, изображенная в левой части рисунка, содержит кратные ребра и поэтому не является графом. Однако такие структуры нередко возникают в практических задачах. Напомним, что они называются мультиграфами, и для них могут быть обобщены многие свойства и методы для обычных графов.

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

Большое число перестановок даже для графов с небольшим количеством ребер делает предложенный метод практически неприменимым.

Рассмотрим более простой способ установления существования и построения циклов Эйлера. Он основан на использовании характеристического свойства графов, имеющих такие циклы.

 


Дата добавления: 2015-09-27 | Просмотры: 425 | Нарушение авторских прав







При использовании материала ссылка на сайт medlec.org обязательна! (0.003 сек.)