Файл: С. Д. Данилова С. С. Михайлова УланУдэ 2022дискретнаяматематика.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 04.12.2023
Просмотров: 287
Скачиваний: 10
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
92
Определение 3.23. Граф ???? =
(
????′′, ????′′
)
называется подграфом графа ???? =
(
????, ????
)
, если
????′
′
⊂ ????, и для любых вершин ????
????
, ????
????
∈ ????′′ ребро (????
????
, ????
????
) ∈ ????′′, если ????
????
, ????
????
) ∈ ????.
Пример
Рассмотрим графы ????, ???? и ???? (рис. 3.9).
Граф ???? является частью графа ????, но не является его суграфом, так как в нем отсут- ствует вершина 4; также граф ???? не является подграфом графа ????, так как отсутствует ребро
(2,3).
Граф ????является и частью, и подграфом графа ????.
Рисунок 3.9 – Примеры части графа и подграфа
3.1.5. Связность графа
Определение 3.25. Граф ???? =
(
????, ????
)
называется связным, если для любых
????, ???? ∈ ???? су- ществует маршрут (путь) из вершины ???? в вершину ????.
Определение 3.26. Связный ориентированный граф называется сильно связным.
Определение 3.27. Орграф называется слабо связным, если он не является сильно связ- ным, но при игнорировании ориентации дуг соответствующий ему неориентированный граф будет связным.
Пример
Граф G
1
,
изображенный на рисунке 3.10, является слабо связным, так как не суще- ствует пути из вершины 2 в любую другую вершину, и при игнорировании ориентации со- ответствующий ему неориентированный граф G'
1
является связным.
Граф G
2
является сильно связным, так как существует путь из любой вершину в лю- бую другую вершину.
93
Рисунок 3.10 – Связные графы
Определение 3.28. Компонентом связности (компонентом) графа ???? = (????, ????) называ- ется его связный подграф, не являющийся подграфом никакого другого связного подграфа графа ????.
Пример
На рисунке 3.11 изображен граф, состоящий из 3-х компонентов:
1-й компонент содержит вершины 1, 2, 3, 4, 5;
2-й – вершину 6;
Рисунок 3.11 – Несвязный граф из 3-х компонентов
Определение 3.29. Лесом называется граф без циклов.
Определение 3.30. Деревом называется связный граф без циклов.
Определение 3.31. Остовным деревом или остовом графа ???? =
(
????, ????
)
называется вся- кий остовной граф графа ????, являющийся деревом.
Пример
На рисунке 3.12 графы P
1
и P
2
являются различными остовами графа
????.
3- й – вершину 7.
2 5
3 6
1 4
7
94
Рисунок 3.12 – Остовы графа
3.1.6. Обходы графа
Во многих задачах на графы требуется обойти граф таким образом, чтобы каждая вер- шина графа «посещалась» и «обрабатывалась» только один раз. Таким образом, обход графа может быть представлен последовательностью вершин, соответствующих порядку, в котором они обрабатываются.
Определение 3.32. Если ???? = (????, ????), |????| = ????, ????: ????
????
⟶
????
????
– перестановка, то вектор
???? = (????
????(1)
, … , ????
????(????)
) определяет обход графа.
Так как каждый обход – это перестановка, то существует
????!
способов обхода графа.
Рассмотрим два метода обхода графов: по глубине и по ширине. Данные методы по- лезны в практических приложениях при определении различных свойств как ориентирован- ных, так и неориентированных графов.
Пусть граф представлен структурой смежности:
Вектор t – последовательность вершин, которая определяет обход графа.
95
96
97
Контрольные
вопросы
1. Какая структура называется графом, ориентированным графом?
2. Как определяется ребро в графе?
3. Что является геометрической интерпретацией графа?
4. Какие вершины графа называются смежными?
5. Что означает в графе понятие инцидентности?
6. Какие существуют машинные представления графа?
7. Чем отличаются матрицы смежности графа и орграфа?
8. Чем отличаются матрицы инцидентности графа и орграфа?
9. Что представляет собой структура смежности?
10. В чем преимущество структуры смежности от матричных представлений графа?
11. В каких случаях предпочтительно использовать список ребер графа?
12. От чего зависит выбор представления графов?
13. Что такое маршрут в графе, конечный маршрут?
14. Какая метрическая характеристика имеется у маршрута?
15. Какой маршрут называется циклическим, цепью (простой цепью), циклом (простым циклом)?
16. Какие понятия в орграфе соответствуют понятиям ребра, маршрута, цикла?
17. Какие существуют части графа?
18. Какой граф называется связным, сильно связным, слабо связным?
19. Что такое компонент графа?
20. Как называется граф без циклов, связный граф без циклов?
21. Что такое остов графа?
22. Что такое обход графа, и сколько существует обходов графа?
23. Какие методы обхода графа существуют?
98
1 2 3 4 5 6 7 8 9 ... 12
Тема 3.2. Метрические характеристики графов
3.2.1. Степени вершин графа
Определение 3.32. В неориентированном графе число ребер, инцидентных вершине v, называется степенью вершины v и обозначается ????(????) или ????????????(????).
Определение 3.34. Вершина со степенью 0 называется изолированной, со степенью 1
– висячей.
Определение 3.35. В ориентированном графе количество дуг, исходящих из вершины
????, называется полустепенью исхода и обозначается ????
−
(????), а количество дуг, входящих в вершину v, полустепенью захода и обозначается ????
+
(????).
Пример
Рассмотрим неориентированный и ориентированный графы (рис. 3.14):
v
1
v
2
v
5
v
4 5
v
4
v
3
(а)
(б)
Рисунок 3.14 – (а) неориентированный граф; (б) ориентированный граф
Для неориентированного графа (рис. 3.14а):
????(????
1
) = 4; ????(????
2
) = 2; ????(????
3
) = 3; ????(????
4
) = 2; ????(????
5
) = 1; ????(????
6
) = 0.
Вершина ????
5
является висячей, вершина
????
6
– изолированной.
Для ориентированного графа (рис. 3.14б):
d
–
(
v
1
)
= 0 ; d
–
(
v
2
)
=1; d
–
(
v
3
)
= 2 ; d
–
(
v
4
)
=1; d
–
(
v
5
)
=1;
d
+
(
v
1
)
=1; d
+
(
v
2
)
=1; d
+
(
v
3
)
=1; d
+
(
v
4
)
= 0; d
+
(
v
5
)
= 2 .
v
3
v
v
6
v
1
v
2
99
Определение 3.36. Граф называется однородным степени k, если степени всех его вер- шин равны k. Или граф является однородным, если степени всех его вершин равны.
Теорема Эйлера. Для любого графа ???? =
(
????, ????
)
справедливы утверждения:
1) ∑
????(????)
????∈????
= 2 ∙ |????|;
2) число вершин четной степени четно.
По матрицам смежности и инцидентности графа можно определить его степени вер- шин.
Пусть даны матрица смежности ????(???? × ????) и матрица инцидентности ????(???? × ????) графа ????.
Степени вершин неориентированного графа определяются по формулам:
Степени вершин ориентированного графа определяются по формулам:
Пример
По матрицам смежности и инцидентности неориентированного графа G
1
(рис. 3.15 а) и ориентированного графа G
2
(рис. 3.15 б) определим их степени вершин.
100
Рисунок 3.15 – (а) неориентированный граф; (б) ориентированный граф
Степени вершин графа G
1 приведены справа строк и ниже столбцов матрицы смежно- сти.
Полустепени исхода вершин орграфа G
2 приведены справа строк, а полустепени за- хода – ниже столбцов матрицы смежности:
Степени вершин графа G
1 приведены ниже столбцов матрицы инцидентности:
Полустепени исхода вершин орграфа G
2
приведены в первом ряду, а полустепени за- хода – во втором ряду ниже столбцов матрицы инцидентности:
3.2.2. Взвешенный граф
Связи между объектами с помощью графов можно описать с помощью приписывания ребрам некоторых количественных значений, качественных признаков или характерных
v
1
v
2
v
3
v
4
v
5
v
6
v
1
v
2
v
3
v
4
v
5
а
(
) б
(
)
e
1
e
2
e
3
e
4
e
5
e
6
e
1
e
2
e
3
e
4
e
5
101 свойств, называемых весами. В простейших случаях это может быть порядковая нумерация ребер, указывающая на очередность их рассмотрения: приоритет или иерархия.
Вес ребра может означать длину пути сообщения, пропускную способность линии связи, напряжение или ток электрических цепей, количество набранных очков на турнире, валентность связей химических формулы, количество рядов движения на автомобильных дорогах, цвет проводника в монтажных схемах электронного устройства, характер отноше- ний между людьми и т. п.
Вес можно приписывать не только ребрам, но и вершинам. Например, вершины, со- ответствующие населенным пунктам, могут характеризоваться количеством мест в гости- ницах, пропускной способностью станций техобслуживания. Вообще, вес вершины озна- чает любую характеристику соответствующего ей объекта – атомный вес элемента в струк- турной формуле, цвет изображаемого вершиной предмета, возраст человека и т. п.
Определение 3.37. Граф ???? =
(
????, ????
) называется взвешенным (реберно), если опреде- лена функция:
????: ???? ⟶ ????.
Функция ???? называется весовой, а ее значение на том или ином ребре – весом ребра.
Любой подграф данного графа и любой путь в данном графе имеют свой вес: это – сумма весов ребер, входящих в этот подграф или в этот путь.
Замечание: обычный (невзвешенный) граф можно интерпретировать как взвешенный граф, в котором все ребра имеют одинаковый вес.
Определение 3.38. Граф ???? =
(
????, ????
) называется вершинно-взвешенным, если опреде- лена функция:
????: ???? ⟶ ????. где ???? – весовая функция, а ее значение на той или иной вершине – вес вершины.
Пример
Рассмотрим взвешенный граф (рис.3.16):
102
Рисунок 3.16 – Взвешенный граф
Отметим, что взвешенные графы по-другому называет еще помеченными, при этом веса, указанные рядом с ребром или вершиной, называют метками или пометками ребра или вершины.
3.2.3. Расстояния в графе
Определение 3.39. Вес любого маршрута (пути) ???? между вершинами ???? и ???? связного графа ???? =
(
????, ????
)
называется длиной этого пути, обозначим ее как
????(????, ????) или ????(????).
Определение 3.40. Минимальная длина между двумя вершинами ???? и ???? называется
расстоянием, обозначим его как ????(????, ????):
Определение 3.41. Путь, который реализует расстояние графа, называется кратчай-
шим.
Определение 3.42. Эксцентриситетом вершины ???? ∈ ???? в графе ???? =
(
????, ????
)
называ- ется максимальное из расстояний от вершины ???? до остальных вершин графа:
103
Определение 3.42. Радиусом графа ???? =
(
????, ????
)
называется минимальный из эксцен- триситетов вершин:
Определение 3.43. Диаметром графа ???? =
(
????, ????
)
называется максимальный из эксцен- триситетов вершин:
Определение 3.45. Центром графа ???? =
(
????, ????
)
называется такая вершина
???? ∈ ????, у ко- торой эксцентриситет равен радиусу графа:
Определение 3.46. Периферийной вершиной графа ???? =
(
????, ????
)
называется та, у кото- рой эксцентриситет равен диаметру графа:
Очевидно, что центров графа и периферийных вершин у графа может быть несколько.
Определение 3.47. Передаточным числом вершины
???? ∈ ???? взвешенного графа ???? =
(
????, ????
)
называется величина:
Определение 3.48. Медианой графа ???? =
(
????, ????
)
называется такая вершина
????
∗
∈ ????, у ко- торой передаточное число минимально:
Пример
Воспроизведем взвешенный граф, изображенный на рисунке 3.16:
104
Рисунок 3.17
Аналогичным образом, определяя расстояния от вершины v
2
до остальных двух вер- шин, получим следующий набор расстояний:
105
3.2.4. Вершинная и реберная связность графа
С точки зрения связности графа представляют интерес два частных случая:
1) наличие в графе вершины, называемой точкой сочленения, удаление которой вме- сте с инцидентными ей вершинами приводит к несвязному графу;
2) наличие в графе ребра, называемого мостом, удаление которого приводит к несвяз- ному графу.
Пример
В графе ????′ (рис. 3.18) точкой сочленения является вершина v
1
Рисунок 3.18 – Граф ????′ с точкой сочленения
v
1
v
2
v
3
v
4
v
5
v
6
106
В графе ????′′ (рис. 3.19) мостом является ребро (????
1
, ????
2
).
Рисунок 3.19 – Граф с мостом
Определение 3.49. Минимальное число вершин, удаление которых делает граф ???? =
(
????, ????
)
несвязным, называется числом вершинной связности графа, обозначается
????(????).
Определение 3.50. Минимальное число ребер, удаление которых делает граф несвяз- ным, называется числом реберной связностью графа, обозначается ????(????).
Если обозначить через ????(????) минимальную степень вершины в графе ????,то имеет место следующее неравенство:
????(????) ≤ ????(????) ≤ ????(????).
Контрольные вопросы
1. Что называется степенью вершины графа, и как она обозначается?
2. Какая вершина называется изолированной, какая висячей?
3. В орграфе как называются степени вершин графа?
4. Как по матрицам смежности и инцидентности можно вычислить степени вершин графа?
5. Что такое взвешенный граф, и какие взвешенные графы бывают?
6. Какими структурами могут быть представлены взвешенные графы?
7. Как определяется вес маршрута?
8. Что такое расстояние между вершинами, и какое расстояние называется кратчай- шим?
v
1
v
2
v
3
v
4
v
5
v
6