У роботі розглядаються
- Теорія графів
- Алгоритми обходу графів
- Пошук в ширину
- Пошук в глибину
- Дерево шляхів
- Мінімальне зв'язне дерево
- Орієнтовані графи
Методи обходу та модифікації графів
Оригінальна назва роботи
Тема роботи: Методи обходу та модифікації графів.
Інформація про навчальний заклад
ВУЗ:
Національний технічний університет України «КПІ імені Ігоря Сікорського»
Інститут:
ООП
Факультет:
Факультет інформатики та обчислювальної техніки
Кафедра:
Кафедра обчислювальної техніки
Інформація про роботу
Рік:
2026
Тип роботи:
Лабораторна робота
Предмет:
Алгоритми і структури даних
Група:
БІ 21
Коротко про документ
Про що ця робота
Лабораторна робота спрямована на вивчення та практичне застосування методів обходу та модифікації графів. Завдання охоплюють побудову дерев за допомогою алгоритмів пошуку в ширину та глибину.
Зміст і розділи
- Теоретичні відомості
- Хід роботи
- Варіанти індивідуального завдання
Для кого:Студенти технічних спеціальностей вищих навчальних закладів, які вивчають алгоритми та структури даних.
Викладачі:Баран
Ключові поняття
графобхід у ширинуобхід у глибинудеревовершинареброциклмінімальне зв'язне деревоорієнтований графнеорієнтований граф
Частина тексту файла (без зображень, графіків і формул):
Тема роботи: Методи обходу та модифікації графів.
Мета роботи: Навчитись застосовувати алгоритми обходу графів, побудови дерева шляхів та мінімального зв’язного дерева.
ТЕОРЕТИЧНІ ВІДОМОСТІ
ХІД РОБОТИ
1) За допомогою лабораторного макету побудувати випадковий неорієнтований граф G={8,12}:
а) Побудувати дерево за алгоритмом обходу в ширину (BFS); (для 2-х різних вершин)
б) Чи будуть однаковими топології дерев побудованих з різних кореневих вершин? Чому?
в) Побудувати дерево за алгоритмом обходу в глибину (DFS); (для 2-х різних вершин)
г) Чи будуть однаковими топології дерев побудованих з різних кореневих вершин? Чому?
2) За допомогою лабораторного макету побудувати випадковий орієнтований граф G={6,10}:
а) Побудувати дерево за алгоритмом обходу в ширину (BFS);
б) Яка вершина (вершини) буде знайдена останньою?
в) Визначити чи існують цикли. Вказати послідовність ребер і їх довжину.
г) Визначити кількість хвиль, які пройдуть по ребрах доки буде виявлена остання вершина.
д) Побудувати дерево за алгоритмом обходу в глибину (DFS);
3) Побудувати дерево шляхів рангом r=4 для випадкового графа G={6,9}.
4) Побудувати мінімальне зв’язне дерево для графа G. Вказати його вагу.
G=
ВАРІАНТИ ІНДИВІДУАЛЬНОГО ЗАВДАННЯ
Допоможи студентському архіву
Ми допомогли тобі — допоможи наступному студенту
Оголошення від адміністратора
Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!