АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

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

Читайте также:
  1. Наиболее распространенными формами представления алгоритмов являются таблицы и древовидные графы.
  2. Ориентированные графы.
  3. Подграфы. Операции над графами.

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

На рис. 3.9 граф G не является эйлеровым, т.к. вершина Р3 инцидентна только одному ребру. Если путь приведёт в вершину Р3 , то не будет ребра, по которому можно было бы выйти из Р3.

 

Рис. 3.9 Рис. 3.10

 

 

Рис.3.11

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

Граф G, изображённый на рис. 3.10 , является эйлеровым. Последовательность рёбер ( 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,) образуют эйлеровый цикл.

 

Теорема: Граф G обладает эйлеровым путём с концами Р1, Р2 тогда и только тогда , когда G связный и Р1, Р2 - единственные его вершины нечётной степени.

На рис. 3.9 изображён граф G, обладающий эйлеровым путём ( 1, 2, 3, 4, 5, 6) с концевыми вершинами Р5 и Р3.

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

Критерий существования гамильтонова цикла в произвольном графе G ещё не найден. Достаточным условием существования гамильтонова цикла является полнота графа G.

Граф на рис. 3.9. не является гамильтоновым, а граф на рис.3.11 содержит гамильтонов цикл ( 1, 2 , 4, 5, 6).


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 |


При использовании материала, поставите ссылку на Студалл.Орг (0.011 сек.)