Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Теорія графів
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
КН
Кафедра:
Не вказано
Інформація про роботу
Рік:
2013
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Теорія алгоритмів
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
Національний університет “ Львівська політехніка ”
Кафедра САП
/
Звіт
до лабораторної роботи № 11
Теорія графів
з курсу «Теорія алгоритмів»
Мета роботи
Мета роботи – вивчити основні визначення та правила використання теорії графів, правила побудови матриць суміжності та інцидентності.
Теоретичні відомості
В загальному випадку, граф — це сукупність об'єктів із зв'язками між ними.
Першою працею з теорії графів як математичної дисципліни вважають статтю Леонарда Ейлера (1736), у якій розглядалася задача про Кенігсбергські мости. Наступний імпульс теорія графів отримала близько 100 років потому з розвитком досліджень по електричних мережах, кристалографії, органічній хімії та іншим наукам.
Теорія графів не має стійкої термінології. В різних статтях під одними й тими ж термінами розуміють різні поняття. Наведені нижче визначення є одними з найбільш розповсюджених.
Граф або неорієнтований граф — це впорядкована пара (G = (V,E)), для якої виконуються наступні умови:
V - множина вершин або вузлів,
E - множина пар (у випадку неорієнтованого графу — невпорядкованих) вершин, які називають ребрами.
V (і так само E) зазвичай вважаються скінченними множинами. Велика кількість результатів, отриманих для скінченних графів, невірна (або інша) для нескінченних графів. Це пов'язано з тим, що певний набір ідей стає хибним у випадку нескінченних множин.
Граф (геометричний граф) — це фігура на площині, яка складається з не порожньої скінченної множини V точок(вершин) і скінченної множини E орієнтованих чи не орієнтованих ліній (ребер), що з'єднують деякі пари вершин.
Орієнтований граф
Граф, який містить тільки ребра називається неорієнтованим, який містить тільки дуги — орієнтованим. Граф, що має як ребра так і дуги, називається мішаним (див.рис.3). Якщо пара вершин сполучається кількома ребрами чи дугами одного напрямку, то ребра (дуги) називають кратними (паралельними). Дуга чи ребро що сполучає вершину саму із собою називається петлею. Граф без кратних дуг і петель називається простим.
Вершини сполучені ребром чи дугою називають суміжними, також називають суміжними ребра, що мають спільну вершину. Ребро (чи дуга) і її вершина називаються інцидентними. Ребро (u, v) з'єднує вершини u і v, дуга (u, v) починається у вершині u і закінчується у вершині v.
Кожен граф можна відобразити в евклідовому просторі множиною точок які відповідають вершинам, сполучених лініями, що відповідають ребрам (дугам). Іноді є потреба пару вершин з'єднати більше, ніж одним ребром.
Мультиграфом називають пару G=(V,E), де V — множина, елементи якої називають вершинами. E — сім'я ребер, кожне з яких — це пара вершин із V.
Ребра, які з'єднують одну й ту саму пару вершин, називають кратними (паралельними) ребрами.
Мультиграф, який може мати петлі, іноді називають псевдографом.
Тип графу
Ребра
Кратні ребра
Простий граф
Неорієнтовані
Ні
Мультиграф
Неорієнтовані
Так
Орієнтований граф
Орієнтовані
Ні
Орієнтований мультиграф
Орієнтовані
Так
Цикл — замкнутий ланцюг, для орграфів цикл називається контур.
Цикл в орієнтованому графі — це простий шлях довжини не менше 1,
котрий починається і закінчується в одній і тій самій вершині.
Дерево — зв'язний граф без циклів.
2.2. Представлення графа в пам’яті ЕОМ
При реалізації на комп’ютері мережі автомобільних доріг, ліній комунікацій, тощо зручно використовувати граф. При програмній реалізації виникає проблема збереження інформації про цей граф у пам'яті комп'ютера.
Вибір структури даних для збереження графа в пам'яті має визначальне значення у процесі розробки ефективних алгоритмів.
У подальшому будемо припускати, що вершини графа мають номери від 1 до N, а ребра — від 1 до M. Кожному ребру і кожній вершині зіставлена вага — ціле позитивне число.
Одним з шляхів рішення даної задачі є представлення інформації про граф у вигляді матриці суміжності. Отже матриця суміжності — один із способів представлення графа у вигляді матриці. Матриця суміжності це двовимірний масив розміром N*N (де N – вершини графа).
Матриця суміжності графа G зі скінченною кількістю вершин n (пронумерованих числами від 1 до n) — це квадратна матриця A розміру n, в якій значення елементу aij рівне числу ребер з i-ї вершини графа в j-у вершину.
Іноді, особливо у разі неорієнтованого графа, петля (ребро з i-ї вершини в саму себе) вважається за два ребра, тобто значення діагонального елементу aii в цьому випадку рівне подвоєному числу петель навколо i-ї вершини. Матриця суміжності простого графа (що не містить петель і кратних ребер) є бінарною матрицею і містить нулі на головній діагоналі.
Цей спосіб використовують у тих випадках, коли виникає потреба часто перевіряти суміжність чи знаходити вагу ребра за двома заданими вершинами.
Ма́триця інциде́нтності — одна з форм представлення графа, в якій вказуються зв'язок між інцидентними елементами графа (ребро (дуга) і вершина). Стовпці матриці відповідають ребрам, рядки — вершин.
Ненульове значення у клітинці матриці вказує на зв'язок між вершиною і ребром (їх інцидентність).
Кожна комірка матриці може набувати трьох значень:
1: якщо ребро виходить з і входить у ;
-1: якщо ребро входить у і виходить з ;
0: якщо між і немає ребра.
Матриця інцидентності це двовимірний масив розміром N*M:
3. КОНТРОЛЬНІ ЗАПИТАННЯ
1. Що таке граф?
Граф — це сукупність об'єктів із зв'язками між ними
2. Чим цикл відрізняється від дерева?
В дереві неможливо повернутися в точку з якої вийшли через інше ребро.
3. Що таке неорієнтований граф?
Неорієнтований граф — це впорядкована пара (G = (V,E)), для якої виконуються наступні умови:
V - множина вершин або вузлів,
E - множина пар (у випадку неорієнтованого графу — невпорядкованих) вершин, які називають ребрами.
4.Для чого використовують матрицю інцидентності?
Для задання графа. Матриця інцидентності найкраще підходить для операції перерахування ребер, що є інцидентними вершині x.
5. Що таке вага ребра?
Число, яке оже показувати, наприклад, відстань між вершинами.
6.Чим відрізняється список суміжності від матриці суміжності?
Кожен елемент списку суміжності містить масив всіх суміжних елементів з даним. Матриця суміжності – це квадратна матриця в якій на перетині осей міститься
7. Що таке мультиграф?
Мультиграфом називають пару G=(V,E), де V — множина, елементи якої називають вершинами. E — сім'я ребер, кожне з яких — це пара вершин із V.
8.Для чого використовують графи?
При реалізації на комп’ютері мережі автомобільних доріг, ліній комунікацій, тощо зручно використовувати граф.
4. ІНДИВІДУАЛЬНЕ ЗАВДАННЯ (варіант 19)
Побудувати граф на основі карти даної області України, вершинами позначити районні центри, ваги ребра позначати за формулою відстань = відстань в сантиметрах помножити на коефіцієнт масштабу. Відстань перевести у кілометри, побудувати матрицю суміжності, матрицю інцидентності.
Тернопільська область
Граф зображений на рисунку 1.
Будую матрицю суміжності(табл. 1).
Табл1. Матриця суміжності графа на рис.1
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
A
0
64,7
102
0
0
0
0
0
0
0
0
0
0
0
0
0
B
64,7
0
54,8
33,5
85,7
0
0
0
0
0
0
0
0
0
0
0
C
102
54,8
0
67,8
0
109
98,3
151
0
0
153
0
0
0
0
0
D
0
33,5
67,8
0
52
48
0
0
0
0
0
0
0
0
0
0
E
0
85,7
0
52
0
75,3
0
0
0
122
0
0
0
0
0
0
F
0
0
109
48
75,3
0
30,2
0
30,8
72,4
0
0
0
0
0
0
G
0
0
98,3
0
0
30,2
0
36,2
62,4
0
0
0
0
0
0
0
H
0
0
151
0
0
0
36,2
0
33,6
0
55,7
13,7
0
0
0
0
I
0
0
0
0
0
30,8
62,4
33,6
0
39,3
0
42,4
0
0
35,5
0
J
0
0
0
0
122
72,4
0
0
39,3
0
0
0
0
0
72,3
0
K
0
0
153
0
0
0
0
55,7
0
0
0
0
25,1
20,1
0
0
L
0
0
0
0
0
0
0
13,7
42,4
0
0
0
0
51,5
36,8
0
M
0
0
0
0
0
0
0
0
0
0
25,1
0
0
30
0
49,5
N
0
0
0
0
0
0
0
0
0
0
20,1
51,5
30
0
76,5
53,7
O
0
0
0
0
0
0
0
0
35,5
72,3
0
36,8
0
76,5
0
117
P
0
0
0
0
0
0
0
0
0
0
0
0
49,5
53,7
117
0
Рис. 1. Граф
Будую матрицю інцидентності (табл. 2.).
Табл. 2. Матриця інцидентності графа на рис. 1
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
e1
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
e2
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
e3
0
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
e4
0
0
1
1
0
0
0
0
0
0
0
0
0
0
0
0
e5
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
e6
0
1
0
0
1
0
0
0
0
0
0
0
0
0
0
0
e7
0
0
0
1
1
0
0
0
0
0
0
0
0
0
0
0
e8
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
e9
0
0
1
0
0
0
0
1
0
0
0
0
0
0
0
0
e10
0
0
1
0
0
0
1
0
0
0
0
0
0
0
0
0
e11
0
0
1
0
0
1
0
0
0
0
0
0
0
0
0
0
e12
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
e13
0
0
0
0
1
1
0
0
0
0
0
0
0
0
0
0
e14
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
e15
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
0
e16
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
e17
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
e18
0
0
0
0
0
1
0
0
1
0
0
0
0
0
0
0
e19
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
0
e20
0
0
0
0
0
0
0
1
0
0
1
0
0
0
0
0
e21
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
e22
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
e23
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
e24
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
0
e25
0
0
0
0
0
0
0
1
0
0
0
0
0
1
0
0
e26
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
e27
0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
0
e28
0
0
0
0
0
0
0
0
1
0
0
1
0
0
0
0
e29
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
0
e30
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
e31
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
e32
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
e33
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
e34
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
0
e35
0
0
0
0
0
0
0
0
1
0
0
0
0
0
1
0
е36
0
0
0
0
0
0
0
0
0
1
0
0
0
0
1
0
ВИСНОВОК: на основі лабораторної роботи я вивчив основні визначення та правила використання теорії графів, правила побудови матриць суміжності та інцидентності.
29.09.2014 20:09-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора