Графи як структури даних та алгоритми їх обробки. Алгоритми на графах. Методи пошуку вглибину і вширину. Цикли у графах. Ейлерові, гамільтонові цикли.

Дізнаємось

Поняття графа як структури даних:
Дізнаємось, що таке граф як структура даних і як його можна використовувати для моделювання різноманітних задач. Розглянемо компоненти графа (вершини та ребра) і два основні способи його представлення:
Матриця суміжності: Як зберігати граф у вигляді двовимірної матриці.
Список суміжності: Як зберігати граф у вигляді списку, що для кожної вершини містить список суміжних до неї вершин.

Алгоритми на графах:
Ознайомимось з основними алгоритмами для роботи з графами, такими як:
Пошук вглибину (DFS): Як здійснюється пошук вершин графа, переходячи від однієї вершини до іншої, поки не досягнемо тупика.
Пошук вширину (BFS): Як здійснюється пошук по графу, відвідуючи вершини рівно віддалені від початкової, по черзі.

Цикли в графах:
Розглянемо поняття циклів у графах:
Ейлерові цикли: Це цикли, які проходять через кожне ребро графа рівно один раз і повертаються в початкову вершину.
Гамільтонові цикли: Це цикли, які проходять через кожну вершину графа рівно один раз і повертаються в початкову вершину.

Застосування алгоритмів пошуку та циклів:
Дізнаємось, де та як застосовуються ці алгоритми в реальних задачах, таких як маршрутизація, планування, пошук у мережах, вирішення задач на графах і т.д.

Навчимось

Реалізовувати графи:
Навчимося реалізовувати графи в програмі за допомогою матриць та списків суміжності, вивчимо, які структури даних зручніші для різних задач.

Реалізовувати алгоритми пошуку вглибину та вширину:
Навчимося реалізовувати алгоритми пошуку вглибину (DFS) та пошук вширину (BFS) на графах, а також розуміти, як вони працюють і в яких випадках кожен з них є кращим вибором.

Шукати ейлерові та гамільтонові цикли:
Ознайомимося з алгоритмами для пошуку ейлерових і гамільтонових циклів у графах. Дізнаємось про умови їх існування та застосування.

Аналізувати графи та їх властивості:
Навчимося аналізувати графи на наявність циклів, їх зв'язність, пошук компонент зв'язності та інші важливі властивості.

Домашнє завдання
Задача на представлення графа:

Реалізуйте граф за допомогою списку суміжності та матриці суміжності. Створіть граф з 5 вершин і 6 ребер.
Напишіть програму, яка виводить граф у вигляді списку суміжності та матриці суміжності.
Задача на пошук вглибину (DFS):

Реалізуйте алгоритм пошуку вглибину (DFS) для графа, представленного списком суміжності.
Програма повинна відвідати всі вершини графа, починаючи з певної вершини, та вивести порядок відвідуваних вершин.
Задача на пошук вширину (BFS):

Реалізуйте алгоритм пошуку вширину (BFS) для графа, представленного списком суміжності.
Програма повинна відвідати всі вершини графа, починаючи з певної вершини, та вивести порядок відвідуваних вершин.
Задача на пошук ейлерового циклу:

Напишіть програму, яка визначає, чи має граф ейлеровий цикл. Реалізуйте алгоритм перевірки за допомогою властивості графа: граф має ейлеровий цикл, якщо всі його вершини мають парну ступінь.
Виведіть ейлеровий цикл, якщо він існує.
Задача на пошук гамільтонового циклу:

Реалізуйте програму для пошуку гамільтонового циклу в графі (на основі методів перебору або аппроксимації).
Програма повинна вивести гамільтоновий цикл, якщо він існує, або повідомити, що циклу немає.

Проблемні питання

Д.з.

Доступно тільки для зареєстрованих користувачів