3.12. Елементи теорії графів (14 год)

Основні поняття теорії графів. Представлення графів. Основні поняття теорії графів. Пошук в графі: пошук в ширину та глибину. Побудова остовного дерева мінімальної довжини. Алгоритми Прима та Краскала.

Визначення найкоротшого шляху в графі. Алгоритм Дейкстри. Алгоритм Флойда-Уоршелла.

Задача комівояжера. Метод гілок і границь.

Дводольні графи. Побудова максимального паросполучення в дводольному графі.

Потоки в мережах. Алгоритм Форда-Фалкерсона побудови максимального потоку в мережі.

Учні повинні знати:

• основні поняття теорії графів;

• основні способи подання графів;

• алгоритми пошуку в ширину та глибину, побудову основного дерева мінімальної довжини, визначення найкоротшого шляху в графі;

• постановку задачі комівояжера;

• сутність алгоритму та реалізацію метода гілок і границь;

• поняття про паросполучення та дводольні графи;

• алгоритм побудови максимального паросполучення у дводольному графі;

• поняття потоків у мережах;

• алгоритм побудови максимального потоку в мережі.

• подання інформації у вигляді графа;

• можливість застосування алгоритмів на графах для розв’язування конкретних алгоритмічних задач.

Учні повинні вміти:

• визначати графову задачу;

• застосовувати стандартні алгоритми для роботи з графами при розв’язуванні задач;

• визначати клас задач щодо застосування для їх розв’язання алгоритмів на графах.