ВУЗ: Томский государственный университет систем управления и радиоэлектроники
Категория: Учебное пособие
Дисциплина: Дискретная математика
Добавлен: 28.11.2018
Просмотров: 9330
Скачиваний: 24
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