Міністерство освіти і науки України Національний університет “Львівська політехніка” Кафедра “Телекомунікації” Лабораторна робота №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 -  / ВИСНОВОК На даній лабораторній роботу було досліджено методи обходу та модифікації графів. Існують декілька методів обходу графа в ширину та в глибину. У даній роботі було використано метод Прима. Також, було розглянути ранги для обходів, величина яких різнить, якщо використовувати різні алгоритми. В більшій мірі у роботі фігурували орієнтовані графи, для яких були виявлені певні дерева шляху, остання виявлена вершина та інше. Також, для деяких графів було виявлена вага, що є сумою всіх ребер графа. Треба зазначити, що вагу можна порахувати як для орієнтованого, так і неорієнтованого графа. В останньому завданні вимагалося побудувати мінімальне зв'язне дерево для графа за його матрицею суміжності.