Учебное пособие: Дискретная мат-ка_УП

131

Рисунок 9.17 

− Пример графа содержащего мост 

9.4 

Эйлеровы

и

гамильтоновы

графы

Связный

граф

 G=(X, U) 

называется

  эйлеровым, 

если

суще

-

ствует

замкнутая

цепь

  (

цикл

), 

проходящая

через

каждое

ребро

графа

один

раз

. 

 
 

 
Рис. 9.18 

− Неэйлеров      Рис. 9.19 − Полуэйлеров       Рис. 9.20 − Эйлеров  

                граф                                     граф                                     граф                                 

Граф

называется

  полуэйлеровым, 

если

существует

незамк

-

нутая

цепь

, 

проходящая

через

каждое

ребро

один

раз

. 

Рассмотрим

условие

существования

эйлерова

цикла

. 

Конечный

граф

 G 

является

эйлеровым

, 

если

он

связан

и

все

его

локальные

степени

четные

 (

рис

. 9.20). 

Заметим

, 

что

граф

яв

-

132

ляется

полуэйлеровым

, 

если

в

нем

не

более

двух

вершин

имеют

нечетные

локальные

степени

. 

Идея

алгоритма

  Флери 

построения

эйлеровой

цепи

в

эйле

-

ровом

графе

. 

Пусть

 G – 

эйлеров

граф

. 

Тогда

необходимо

выйти

из

произвольной

вершины

и

проходить

по

ребрам

 G, 

соблюдая

правила

: 

1.

Стирать

ребра

по

мере

их

прохождения

и

стирать

изоли

-

рованные

вершины

. 

2.

По

мосту

можно

проходить

только

тогда

, 

когда

нет

дру

-

гих

возможностей

. 

При

программировании

использовать

 2 

стека

. 

Цикл

, 

проходящий

по

всем

вершинам

графа

 G 

один

раз

, 

на

-

зывается

  гамильтоновым, 

а

граф

 G 

называется

гамильтоновым

графом

. 

Для

гамильтонова

графа

не

существует

критерия

суще

-

ствования

гамильтонова

цикла

, 

есть

только

теоремы

, 

дающие

достаточные

условия

его

существования

или

отсутствия

. 

Теорема

 1. 

Если

в

графе

с

 n (n 

≥ 3) 

вершин

для

любой

пары

несмежных

вершин

 x

i

, x

j

   

ρ(x

i

)+ 

ρ (x

j

) 

≥n,  

то

граф

имеет

гамиль

-

тонов

цикл

. 

Теорема

 2. 

В

графе

без

гамильтонова

цикла

длина

его

наи

-

больших

простых

цепей

удовлетворяет

неравенству

ℓ

  

≥

ρ (x

n1

) + 

+

ρ (x

n2

), 

где

ρ (x

n1

) 

и

ρ (x

n2

) – 

две

наименьшие

локальные

степени

графа

. 

 
 
 
 
 
 
 
 

                    Рисунок 9.21                                                     Рисунок 9.22 

Если

в

графе

 G 

существует

висячая

вершина

, 

то

гамильто

-

нов

цикл

отсутствует

. 

Если

граф

 G 

полный

, 

то

он

содержит

га

-

мильтонов

цикл

. 

х

1

х

4

х

2

х

5

х

6

х

3

х

1

х

4

х

2

х

5

х

6

х

3

133

9.5 

Деревья

Связный

граф

без

циклов

называется

деревом

и

обозначает

-

ся

Т

 = (

Х

, U),       | X | = n,   | T | = n–1.  

Начальную

вершину

назы

-

вают

  корнем, 

из

которого

выходят

ребра

, 

называемые

  ветвями 

дерева

. 

Любые

две

вершины

дерева

связаны

единственной

цепью

. 

В

любом

связном

графе

 G 

можно

выделить

некоторое

дерево

Т

. 

Дерево

, 

у

которого

число

вершин

равно

числу

вершин

графа

из

которого

выделено

дерево

, 

а

ребро

является

подмножеством

этого

графа

, 

называется

 покрывающим 

деревом

. 

Для

одного

и

того

же

связного

графа

можно

выделить

неко

-

торое

множество

покрывающих

его

деревьев

. 

Теорема

 3. 

Число

 t  

покрывающих

деревьев

в

полном

графе

K

n

составляет

  t=n

n–2

. 

Множество

деревьев

называется

 лесом. 

Задачи

выделения

эйлеровых

и

гамильтоновых

циклов

, 

а

также

покрывающих

деревьев

, 

связаны

с

задачами

о

лабиринте

, 

коммивояжере

, 

с

построением

деревьев

минимальной

точности

. 

Задача

о

лабиринте

в

терминах

теории

графов

формулируется

как

задача

отыскания

в

связном

графе

 G=(X, U) 

маршрута

с

наи

-

меньшим

числом

ребер

, 

который

начинается

в

заданной

вершине

х

i

∈

Х

и

приводит

в

искомую

вершину

х

j

∈

Х

. 

 
Метод Тремо 

От

вершины

х

i

необходимо

перейти

ко

всем

вершинам

, 

на

-

ходящимся

на

расстоянии

 1 

дин

. 

Каждое

ребро

 u

i

 = (

х

i

, x

ℓ

) 

поме

-

чается

один

раз

, 

когда

оно

смежно

с

вершинами

х

i

, x

ℓ   

в

вершине

х

i

, 

это

ребро

помечается

как

  «

открытое

». 

Если

окажется

, 

что

нет

ребер

, 

инцидентных

 x

ℓ

, 

кроме

 u

i

, 

то

, 

вернувшись

в

х

i

, 

ребро

 u

i

по

-

мечается

как

  «

закрытое

». 

Если

некоторое

другое

ребро

 u’

i

  =            

=(

х

i

, x

ℓ

)  

также

ведет

из

х

i

в

 x

ℓ   

оно

также

помечается

как

закры

-

тое

.  

Для

попадания

   

в

вершины

, 

находящиеся

   

на

расстоянии

 2, 

берется

открытое

ребро

 u = (

х

i

, x

ℓ

) 

и

снова

помечается

. 

В

  x

ℓ   

от

-

крытые

  

ребра

проходятся

и

помечаются

как

закрытые

, 

если

они

ведут

к

пройденным

вершинам

, 

и

так

со

всеми

открытыми

реб

-

рами

. 

Если

искомая

вершина

расположена

на

расстоянии

 n, 

то

при

ее

достижении

все

открытые

ребра

будут

помечены

 n 

раз

. 

134

Рисунок 9.23 

Задача

 2. 

Пусть

необходимо

проложить

сеть

проводов

меж

-

ду

терминалами

при

условии

, 

что

количество

затраченного

про

-

вода

должно

быть

минимальным

, 

т

.

е

. 

построить

граф

типа

дере

-

во

. 

Задача

состоит

в

нахождении

одного

из

 n

n–2 

деревьев

. 

Пусть

 G=(X, U)  

связной

граф

, 

и

каждому

ребру

  u

i

∈U 

ста

-

вится

в

соответствие

некоторое

неотрицательное

число

ν

i

, 

назы

-

ваемое

мерой

. 

Необходимо

найти

покрывающее

дерево

Т

, 

для

ко

-

торого

сумма

мер

, 

взятая

по

всем

ребрам

, 

минимальна

. 

 
 
 
 
Метод Краскала 
 
1.

В

связном

графе

 G=(X, U), | X | = n, 

определяется

ребро

с

наименьшей

мерой

. 

2.

Строится

по

индукции

последовательность

ребер

 u

2

, u

3

,…, 

u

n–1

, 

причем

на

каждом

шаге

выбирается

ребро

с

наименьшей

ме

-

рой

, 

не

совпадающее

с

выбранными

и

не

образующее

циклов

с

предыдущими

ребрами

 u

i

. 

Полученный

подграф

Т

графа

 G 

явля

-

ется

искомым

деревом

. 

 
 

( )

.

min

1

=

∑

=

m

i

i

u

ν

135

 
 

 
 
 
 
 
 
 
 
 
 

 
9.6 

Понятие

метрики

графа

Метрика

графа

основана

на

понятии

расстояния

. 

Назовем

    

расстоянием

 d(x

i

, x

j

) = d

ij

между

вершинами

 x

i

,x

j

∈X 

графа

 G=(X, U) 

длину

кратчайшей

цепи

, 

соединяющей

эти

вершины

. 

Под

длиной

цепи

понимается

число

входящих

в

нее

ребер

. 

Функция

 d(x

i

, x

j

), 

определенная

на

множестве

ребер

графа

 G, 

называется

  метрикой 

графа

. 

Метрика

удовлетворяет

аксиомам

Фреше

: 

∀ x

i

 x

j

∈ X[d(x

i

, x

j

) 

≥ 0]; 

∀ x

i

 x

j

∈ X[d(x

i

, x

j

) = 0 

↔ x

i

 = x

j

]; 

∀ x

i

 x

j

∈ X[d(x

i

, x

j

) = d(x

i

, x

j

)]; 

∀ x

i

,x

j

,x

k 

∈ X[d(x

i

, x

j

) + d(xj, x

k

) 

≥ d(x

i

, x

k

)], 

т

.

к

. d(x

i

, x

j

) 

кратчайшая

цепь

Функция

расстояний

задается

матрицей

  

   

0, 

если

 x

i

 = x

j

; 

              D = || d

ij

|| =  

   

d

ij

, 

если

 x

i

≠ x

j

; 

Список

  

расстояний

   

можно

   

задать

   

в

виде

множества

кор

-

тежей

длины

  

три

  < x

i

,x

j

,d

ij

 >. 

Для

графа

, 

приведенного

на

рисунке

 9.24. 

D={<1,2,3>, <1,3,1>, <1,4,3>, <1,5,2>, <2,3,2>, <2,4,1>, 

<2,5,1>, <3,4,2>,  <3,5,1>,  <4,5,1>} 

(х

2

х

6

)=1 

(х

6

х

3

)=2 

(х

3

х

5

)=1 

(х

3

х

1

)=2 

(х

2

х

4

)=1