ВУЗ: Национальная металлургическая академия Украины
Категория: Учебное пособие
Дисциплина: Маркетинг
Добавлен: 06.02.2019
Просмотров: 2039
Скачиваний: 7
31
Т
ЕМА
4
Е
ЛЕМЕНТИ ТЕОРІЇ ГРАФІВ
О
СНОВНІ ВИЗНАЧЕННЯ
,
ЗАДАЧІ ТА ВПРАВИ
Основні визначення
Неорієнтованим мультиграфом G називається пара (V, E), де E
⊆
MV
(2)
. Елементи множини V називаються вершинами, а елементи множини
E – ребрами. Ребра позначаються (u, v), де u, v – вершини з V.
Мультиграф G = (V, E) називається неорієнтованим графом, якщо E
⊆
V
(2)
. Всякий граф є мультиграфом, але не всякий мультиграф буде графом.
Якщо G = (V, E) – мультиграф, то Е може мати кілька ребер, що з’єднують
одні і ті ж вершини u i v. Такі ребра називаються кратними ребрами.
Два ребра називаються суміжними, якщо вони мають спільний кінець.
Вершина u і ребро е називаються інцидентними, якщо u є кінцем ре-
бра е, і неінцидентними в протилежному випадку.
Степенем n(u) вершини u графа G називається число інцидентних їй
ребер. Вершина степені 0 називається ізольованою, а вершина степені 1 –
висячою, або кінцевою. Ребро, інцидентне кінцевій вершині, також назива-
ється кінцевим.
Якщо G = (V, E) – скінчений граф порядку n, то йому відповідає квад-
ратна матриця A(G) розмірності n
∗
n, яка називаєтьяс матрицею суміжності
Приклад визначення ребер і вершин графа за допомогою
матриці суміжності
1, коли вершини v
i
i u
j
суміжні
a
ij
0 – в протилежному випадку
Нехай маємо матрицю
0
0
0
0
0
1
0
0
1
1
0
1
1
1
1
0
Цій матриці відповідає
орграф (малюнок 7)
1
2
3
4
Рис.7
32
Всяка квадратна матриця, елементи якої 0 і 1, буде матрицею суміж-
ності орієнтованого графа. Ранги матриць суміжностей ізоморфних графів
рівні між собою.
Матриця I(G) графа G = (V, E), де V = {1, 2, … n}, E = {e
1
, … e
m
}, на-
зиваєтьяс матрицею інцидентності, вона задовольняє таким умовам
Задачі і вправи
1.
Неорієнтований граф G = (V, E, O) заданий аналітичним способом.
V = (v1,v2,v3,v4,v5), E = (e1,e2,e3,e4,e5,e6,e7,e8,e9,e10), O = ((v1,v1),
(v1,v3), (v1,v5), (v2,v3), (v2,v4), (v2,v5), (v3, v1), (v3,v4), (v4,v2), (v4,v5)).
Необхідно:
a) задати граф геометричним способом;
b) знайти матрицю суміжності;
c) визначити степені вершин графа.
2. Задано неорієнтований граф (малюнок 8).
Необхідно:
a) знайти матрицю суміжності
b) визначити степені вершин графа;
1, якщо вершина k і ребро e
l
інцидентні
i
kl
0 – в протилежному випадку
Рис.8
33
3. Орієнтований граф G = (V,E,O) заданий аналітичним способом.
V = (v1,v2,v3,v4,v5), E = (e1,e2,e3,e4,e5,e6,e7,e8,e9,e10), O = ((v1,v1),
(v1,v3), (v1,v5), (v2,v3), (v2,v4), (v2,v5), (v3, v3), (v3,v4), (v4,v5), (v5,v5)).
Необхідно:
a) задати граф геометричним способом;
b) знайти матрицю інцидентності;
c) визначити полу-степені вершин графа.
4. Задано орієнтований граф (малюнок 9).
Необхідно:
a) знайти матрицю інцидентності;
b) визначити полу-степені вершин графа.
5. Знайти найкоротший шлях у графі G (мал. 10) між вершинами х
1
і х
10
.
Рис.9
Рис.10
34
6. Знайти остовне дерево найменшої ваги для графа з задачі №5.
7. Вирішити задачу комівояжера, якщо задана матриця відстаней
X1
X2 X3 X4 X5 X6
X1
∞
22
26
56
38
60
X2
34
∞
12
51
37
27
X3
45
33
∞
44
47
37
X4
39
7
16
∞
57
8
X5
35
56
40
58
∞
27
X6
9
20
36
31
18
∞
8. Знайти максимальну течію у мережі (малюнок 11).
9. Нехай V – множина додатних цілих чисел від 1 до 20 і a|b – відношення
подільності, тобто a|b означає, що число а є дільником числа b. Нама-
люйте граф відношення a|b для множини V.
10. Побудуйте матриці суміжності та інцидентності для платонових графів.
11. Нехай G – регулярний граф порядку n і степеня d. Покажіть, що X
p
(G)
≥
≥
n / (n – d).
12. Граф називається критичним, якщо вилучення будь-якої його вершини
приводить до графа з меншим хроматичним числом.
Доведіть, що:
a) K
n
є критичним для всіх n
>
1;
b) С
n
критичний тоді, і тільки тоді, коли n непарне;
z
10;10
12;10
13;9
7;7
x
6
x
0
x
7
x
8
x
1
x
2
x
3
x
4
x
5
4;4
4;4
8;8
7;2
7;2
6;6
4;4
4;4
4;4
22;18
12;7
6;3
5;4
Рис.11
35
c) якщо n непарне, то з’єднання С
n
i C
n
є критичним графом, хроматичне
число якого дорівнює 6.
13. Знайдіть Ейлерів ланцюг для графа, зображеного на малюнку 12.
14. Побудуйте граф, множина вершин котрого відповідає множині курсів
навчання, котрі вам необхідно пройти для отримання ступеня бакалав-
ра. При цому, дугу от вершини x до вершини y включайте в граф тільки
в тому випадку, якщо курс x попередній від курсу y. Інтерпретуйте на-
ступні елементи побудови графа:
a) путь,
b)
ланцюг,
c)
цикл,
d)
контур,
d) зв’язану компоненту.
15. Степінь входження d
-
(x) вершини x визначається як число дуг, які захо-
дять у вершину x. Степінь сходу d
+
(x) вершини x визначається як число
дуг, які починаються у вершині x. Степінь d(x) вершини x визначається
як сума степеней входження та сходу для даної вершини. Покажіть, що
в будь-якому графі G кількість вершин з непарним степенем парно. По-
кажіть, що для будь-якого графа G = (X, A) має місце співвідношення
∑
∑
∈
∈
−
=
=
X
x
X
x
x
d
x
d
)
(
)
(
.
16. Нехай Т – дерево, яке покриває для графа G. Покажіть, що в G для будь-
яких двох вершин існує єдиний ланцюг, який складається тільки із ре-
бер дерева Т.
17. Чи можливо, щоб розтин і цикл вміщували в точності загальну дугу?
Якщо неможливо, то чому?
Рис.12