- •7.091501: "Комп'ютерні системи та мережі"
- •7.091502: ”Системне програмування”
- •Лабораторна робота №1
- •Теоретичні відомості
- •Задачі на теорію множин
- •Задачі для самостійної роботи студентів
- •Завдання
- •Зобразити множину ab-c
- •Приклад відношень g
- •Контрольні питання
- •Лабораторна робота №2
- •Теоретичні відомості
- •Задачі на теорію множин
- •Задачі для самостійної роботи студентів
- •Контрольні питання
- •Лабораторна робота №3
- •Теоретичні відомості
- •Формули з’єднань
- •Біном Ньютона
- •2) Основна властивість біноміальних коефіцієнтів
- •Правило суми
- •Перестановки
- •Перестановки з повторенням
- •Розміщення
- •Розміщення з повтореннями
- •Сполучення
- •Сполучення з повтореннями
- •Біном Ньютона
- •Поліноміальна формула
- •Задачі для самостійної роботи студента
- •Контрольні питання
- •Лабораторна робота №4
- •Теоретичні відомості.
- •Лінійні рекурентні співвідношення з постійними коефіцієнтами
- •Твірна функція
- •Розбиття множини на підмножини
- •Задачі по темі Твірні функції:
- •Задачі для самостійної роботи студентів
- •Контрольні питання
- •Лабораторна робота №5.
- •Теоретичні відомості
- •Способи збереження інформації о графах
- •Задачі на теорію графів
- •Задачі для самостійної роботи студентів
- •Ізоморфізм графів
- •Досяжність і зв’язність.
- •Орієнтовані графи
- •Процедура пошуку в глибину у графі
- •Пошук у ширину
- •Ейлерові цикли
- •Гамільтонові цикли
- •Алгоритми пошуку мінімальних шляхів у графі
- •Задачі на теорію графів
- •Задачі для самостійної роботи студентів
- •Плоскі графи. Розфарбування графа
- •Контрольні питання
- •Пошук максимального потоку у мережі
- •Задачі з теорії графів
- •Задачі для самостійної роботи студентів
- •Лабораторна робота №8.
- •Теоретичні відомості
- •Задачі з теорії кодування
- •Задачі для самостійної роботи студентів
- •Контрольні питання
- •Список рекомендованої літератури
Процедура пошуку в глибину у графі
Пошук починається з деякої фіксованої вершини v. Розглядається вершина u, суміжна з v. Вона вибирається. Процес повторюється з вершиною u. Якщо на черговому кроці ми працюємо з вершиною q і немає вершин, суміжних з q і не розглянутих раніше (нових), то повертаємося з вершини q до вершини, яка була до неї. У тому випадку, коли це вершина v, процес перегляду закінчений. Для реалізації даного методу потрібна структура даних - стек.
Розглянемо приклад пошуку в глибину на графі, описаному матрицею суміжності (рис.6.1). Почнемо пошук з першої вершини. Нехай:
• Матриця сигналу перегляду чергової вершини - FLAG
• Стек для зберігання номерів переглянутих вершин - ST
• Покажчик вершини стека - Y
• Номер чергової вершини - T
Рис 6.1. Приклад графа і його матриці суміжності
Рис. 6.2. Трасування пошуку в глибину для даного прикладу
Рис. 6.3. Черговість перегляду вершин графа при пошуку в глибину
Пошук у ширину
Суть методу полягає в тому, щоб розглядати всі вершини, пов'язані з поточною. Принцип вибору наступної вершини - вибирається та, яка була раніше розглянута. Для реалізації даного принципу необхідна структура даних - черга.
Розглянемо приклад пошуку в глибину на графі, описаному матрицею суміжності (рис.6.4). Почнемо пошук з першої вершини. Нехай:
• Матриця сигналу перегляду чергової вершини - FLAG
• Черга перегляду вершин - ORDER
• Покажчик початку черги - X
• Покажчик кінця черги - Y
Рис.6.4. Приклад графа і його матриці суміжності
Рис.6.5. Трасування пошуку в ширину для даного прикладу
Рис.6.6. Черговість перегляду вершин графа при пошуку в ширину
Ейлерові цикли
Ейлерів цикл - це такий цикл, який проходить рівно один раз по кожному ребру.
Теорема. Зв'язаний неорієнтований граф G містить Ейлерів цикл тоді і тільки тоді, коли число вершин непарного ступеня дорівнює нулю.
Ступінь вершини - кількість ребер, інцидентних з цією вершиною.
Пошук ейлерева циклу. Задано граф, що задовольняє умові теореми. Потрібно знайти Ейлерів цикл. Використовується перегляд графа в глибину, при цьому ребра видаляються. Порядок перегляду (номери вершин) запам'ятовуються в першому стеку. При виявленні вершини, з якої не виходять ребра, її номер записується в другий стек. Процес продовжується до тих пір, поки перший стек не стане порожнім. У другому стеку після цього будуть записані номери вершин графа в порядку відповідному ейлереву циклу.
Гамільтонові цикли
Граф називається гамільтоновим, якщо в ньому є цикл, який проходить через кожну вершину цього графа. Сам цикл також називається гамільтоновим. Не всі пов'язані графи гамільтонові.
Пошук гамільтонова циклу. Метод рішення - перебір з поверненням.
Починаємо пошук рішення, наприклад, з першої вершини графа. Припустимо, що вже знайдено перші k компонент рішення. Розглядаємо ребра, що виходять з останньої вершини. Якщо є такі, що йдуть до раніше не переглянутих вершин, то включаємо цю вершину в рішення і викреслюємо як переглянуту. Отримано k-1 компонента рішення. Якщо такої компоненти немає, то повертаємося до попередньої вершині і намагаємося знайти ребро з неї, що виходить в іншу вершину. Рішення отримано при перегляді всіх вершин графа і можливості досягти з останньої вершини першу. Рішення виводиться і триває процес знаходження наступних циклів. Процедура знаходження гамільтонова циклу є рекурсивною.