Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Методи обходу та модифікації графів
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
О
Факультет:
Не вказано
Кафедра:
Кафедра Телекомунікації
Інформація про роботу
Рік:
2017
Тип роботи:
Лабораторна робота
Предмет:
Телекомунікаційні та інформаційні мережі
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
Національний університет “Львівська політехніка”
Кафедра “Телекомунікації”
Лабораторна робота №3 на тему:
“ Методи обходу та модифікації графів ”
з дисципліни "Телекомунікаційні та інформаційні мережі. Частина 1"
Мета роботи:Навчитись застосовувати алгоритми обходу графів, побудови дерева шляхів та мінімального зв’язного дерева.
ХІД РОБОТИ
1) За допомогою лабораторного макету побудувати випадковий неорієнтований граф G={8,12}:
/
а) Побудувати дерево за алгоритмом обходу в ширину (BFS); (для 2-х різних вершин)
/
/
б) Чи будуть однаковими топології дерев побудованих з різних кореневих вершин? Чому?
Обидва мають третій ранг, але вони не є однакові, тому, що якщо виходити з різних вершин, то кількість вершин інших рангів буде постійно змінюватись.
в) Побудувати дерево за алгоритмом обходу в глибину (DFS); (для 2-х різних вершин)
г) Чи будуть однаковими топології дерев побудованих з різних кореневих вершин? Чому?
Не будуть, тому, що початок у різних вершинах, а значить і наступні точки різні, тому у другій топології приходиться вертатись на один (або декілька) кроків назад.
2) За допомогою лабораторного макету побудувати випадковий орієнтований граф G={6,10}:
/
а)Побудувати дерево за алгоритмом обходу в ширину (BFS);
/
б) Яка вершина (вершини) буде знайдена останньою?
Залежить від початкової вершини, але буде та, що не має виходів, а має входи.
в) Визначити чи існують цикли. Вказати послідовність ребер і їх довжину.
Існують такі цикли: 1-2-3; 2-6; 2-3.
г) Визначити кількість хвиль, які пройдуть по ребрах доки буде виявлена остання вершина.
Три хвилі пройдуть по ребрах доки буде виявлена остання вершина.
д) Побудувати дерево за алгоритмом обходу в глибину (DFS);
/
3) Побудувати дерево шляхів рангом r=4 для випадкового графа G={6,9}.
Граф:
Дерево шляхів рангом r=4:
/
4) Побудувати мінімальне зв’язне дерево для графа G. Вказати його вагу.
G=
-
12
8
5
8
15
12
-
0
10
0
9
8
0
-
8
5
3
5
10
8
-
0
7
8
0
5
0
-
11
15
9
3
7
11
-
/
ВИСНОВОК
На даній лабораторній роботу було досліджено методи обходу та модифікації графів. Існують декілька методів обходу графа в ширину та в глибину. У даній роботі було використано метод Прима. Також, було розглянути ранги для обходів, величина яких різнить, якщо використовувати різні алгоритми. В більшій мірі у роботі фігурували орієнтовані графи, для яких були виявлені певні дерева шляху, остання виявлена вершина та інше. Також, для деяких графів було виявлена вага, що є сумою всіх ребер графа. Треба зазначити, що вагу можна порахувати як для орієнтованого, так і неорієнтованого графа. В останньому завданні вимагалося побудувати мінімальне зв'язне дерево для графа за його матрицею суміжності.
21.12.2017 23:55
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора