Тема: способи представлення графів, пошук у ширину та глибину мовою Python

Мета

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

• що таке граф, ребро, дуга, орієнто­ваний граф, неорієнто­ваний граф, маршрут, цикл, зв'язний граф, дерево;

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

• ідеї пошуку в ширину та у глибину.

• використовувати набуті знання на практиці;
• створювати й використовувати списки суміжності;
• програмно втілювати пошуки в ширину та у глибину;
• дотримуватися санітарно-гігієнічних норм і норм техніки безпеки праці.

Обладнання: комп’ютери зі встановленими ОС та середовищем програмування мовою Python або стійким сполученням з Інтернетом для роботи з середовищами програмування у режимі online.

Структура уроку

1. Організаційний момент.
2. Актуалізація опорних знань.
3. Вивчення нового матеріалу.
4. Інструктаж з ТБ.
5. Закріплення вивченого матеріалу.
6. Підбиття підсумків уроку.
7. Домашнє завдання.

Хід уроку

1. Організаційний момент
Вітання з класом. Перевірка присутності і готовності учнів до уроку. Перевірка виконання домашнього завдання.

2. Актуалізація опорних знань

1. Що таке елемент і множина?
2. Вказати, який запис відповідає упорядкованій та неупорядкованій парам елементів:
   • { a; b };
   • {{ a }, { a; b }};
3. Сформулювати комбінаторне правило множення.
4. Як створити і змінити список?

3. Інструктаж з ТБ
4. Вивчення нового матеріалу

Теорія графів — розділ математики, який традиційно вивчають у вищій школі. Зазвичай школярі стикаються з поняттям графа, розв'язуючи нестандартні (щодо шкільної програми) задачі. Наприклад, беручи участь в олімпіадах з математики. Але ці поняття доступні не лише для розуміння, але й використання дітям дошкільного віку. Досвід щодо цього описано, наприклад, у такій книзі:

Ф. Папи и Ж. Папи. Дети и графы. Обучение детей шестилетнего возраста математическим понятиям. Брюссель — Монреаль — Париж, 1968. Пер. с франц. М., «Педагогика», 1974, 192 с. с ил.

F. Papy, G. Papy, D. Incolle. L'enfants et les graphes. Didier, Bruxelles — Montreal — Paris, 1968, 189 p.

У ній подано ілюстрації дітей до їхніх спроб пояснення стосунків між людьми за допомогою графів.

Означення 1. Запровадимо такі поняття:

• Граф — це множина, що складається з елементів двох типів: вершин і пар вершин (упорядкованих чи неупорядкованих). Граф може не містити жодної пари вершин, але обов'язково містить вершини.

• Упорядковану пару вершин графа називають дугою (орієнтованим ребром в англомовній літературі) і на рисунку позначають лінією зі стріл­кою (від зображення першої вершини до зображення другої). На поданні рисунком різним дугам (ребрам) відповідають різні лінії, що не містять зображень інших вершин графа.

• Неупорядковану пару вершин графа називають ребром (неорієнтованим ребром в англомовній літературі) і на рисунку позна­чають лінією без стрілки (між зображеннями вершин пари).

• Для різних вершин A_j та А_k будемо казати, що дуга чи (неорієнтоване) ребро (A_j ; А_k) сполучає (з’єднує) вершину A_j з вершиною A_k. При цьому ребро (A_j ; А_k) сполучає вершину А_k з вершиною A_j, а дуга (A_j ; А_k) — ні.

• Петля — дуга чи ребро, що сполучає вершину саму із собою.

• Пара вершин можна сполучати двома чи більше дугами (реб­рами). Такі дуги (ребра) називають кратними. Для m-ої дуги (ребра), що сполучає вершину A_j з вершиною A_k, використовують позначення (A_j ; А_k)_m.

• Граф називають:
  • орієнтованим, якщо, крім вершин, він містить лише ду­ги;
  • неорієнтованим, якщо, крім, вершин, він містить лише ребра;
  • порожнім, якщо він містить лише вершини.

• Для орієнтованого (неорієнтованого) графа з N вершинами і скінченною кількістю дуг (ребер) утворюють матрицю суміжності розміру N×N таким, чином: у j-му рядку k-го стов­пчика розташовують загальну кількість дуг (ребер), що сполу­чають j-y вершину з k-ою.

• Послідовність дуг (ребер) (A_j0 ; A_j1), (A_j1 ; A_j2), (A_j2 ; A_j3), …, (A_{jm – 1} ; A_jm) називають маршрутом з вершини A_j0 до A_jm за m кроків.

• Цикл у графі — маршрут з вершини графа до неї самої.

• Граф називають зв’язним, якщо для будь-яких двох його різних вершин існує маршрут з однієї до іншої.

• Дерево — це неорієнтований зв’язний граф без циклів.

Методом математичної індукції можна довести, що кількість ребер дерева з N вершинами дорівнює N — 1.

Прикладом неорієнтованого графа є схема залізничного сполу­чення з вершинами — залізничними станціями — і ребрами — відпо­відними ділянками залізниці.

Прикладом орієнтованого графа є соціограма — схема, на якій круги-вершини позначають окремих людей, а лінії-дуги — виявлене у результаті опитування ставлення (повагу, симпатію) одного з них до іншого.

Зауваження. Деякі властивості графа, можна описати в тер­мінах матриці суміжності:

• Якщо граф не має петель, то всі діагональні елементи його матриці суміжності дорівнюють 0.

• Якщо граф не має кратних ребер, то всі елементи його мат­риці суміжності дорівнюють 0 або 1.

• Якщо граф неорієнтований, то його матриця суміжності си­метрична відносно головної діагоналі.

• Для неорієнтованого незв’язного графа існує така нумерація вершин, для якої матриця суміжності графа має блочно-діагональний вигляд.

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

• перебираючи ребра від першого до останнього, робити таке: якщо на даному кроці розглядають ребро (дугу) між вершинами A та B, то до списку суміжності вершини A додаємо вершину B, а до списку суміжності вершини B додаємо вершину A (останнє робимо лише для ребер).

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

Видається прийнятним намагання подати інформацію про орієнтований чи неорієнтований граф матрицею суміжності. Але для так званих розріджених графів, у яких кількість ребер (дуг) істотно менша від максимально можливої, це призведе до нераціонального використання пам'яті. У цьому випадку матриця суміжності графа переважно складається з нулів. Тому доречно зберігати у пам'яті не матрицю суміжності, а списки суміжності, зручність яких відчуємо при розв'язанні поданих далі завдань. Надалі обмежимося саме таким поданням графа в обчисленнях.

Для мов, у яких масиви мають сталу структуру з моменту оголошення (опису) списки суміжності можна організувати:

• або використавши динамічний розподіл пам'яті з вказівниками;
• або таким чином:
  • створити масив двовимірних масивів, довжина якого:
    • дорівнює кількості дуг орієнтованого графа;
    • удвічі більша від кількості ребер неорієнтованого графа;
  • внести у масив кінці:
    • дуг для орієнтованого графа;
    • ребер — для неорієнтованого графа — двічі у різному порядку;
  • упорядкувати масив за:
    • початком дуги — для орієнтованого графа;
    • першим елементом 2-вимірного масиву — для неорієнтованого графа.

• c_jk⁽¹⁾ — кількість ребер (дуг), що сполучають вершину j з вершиною k. При відсутності кратних ребер ця величина дорівнює 0 або 1;

• при довільному натуральному i у межах від 1 до m включно справджується така рівність:

  c_jk^{(m + 1)} = ∑ c_jl^{(i )} c_lk^{(m + 1 − i )},

  де додавання ∑ здійснюють за всіма вершинами l. Ця формула випливає з комбінаторного правила множення і такого міркування: для того, щоб з вершини j до вершини k потрапити за (m + 1) крок, потрібно:

  • за i кроків потрапити з вершини j у деяку вершину l;
  • за решту (m + 1 − i ) кроків потрапити з вершини l у вершину k.

Остання записана рівність допомагає обчислити значення c_jk^(m) при певному m, використовуючи значення цих величин при менших значеннях m. Зазвичай цю рівність використовують при i = 1 або i = m + 1 − i.

Завдання 1. Вершини неорієнтованого графа занумеровано послідовними цілими числами, починаючи з 0. Скласти програму для подання графу списками суміжності й обчислення кількості різних маршрутів певної довжини від вершини з найменшим номером до вершини з найбільшим номером (дозволено повторно відвідувати вершини).

Вхідні дані. Перший рядок вхідного файлу містить три числа: кількість вершин графа, кількість ребер графа і довжину маршруту. Кожний з наступних рядків містять по два номери вершин, сполучених ребром. Таким чином кожне ребро графа згадано один раз.

Вихідні дані. Єдиний рядок вихідного файлу має містити лише шукану кількість різних маршрутів.

Наприклад, для графа, що має 7 вершин і 8 ребер:

6 — 0 — 4
|   |   | \
5 — 1   2 — 3

7 8 5
0 1
0 4
0 6
2 3
2 4
3 4
5 6
5 1

Вихідний файл у цьому випадку повинен містити:

25

Зберегти файл програми у теці з назвою Ваше_прізвище_1 у вказаному вчителем місці. Порівняти створену програму з демонстра­ційним розв'я­занням.

Поняття пошуків у ширину та глибину розглянемо на прикладі пошуку каркасного дерева.

Означення 2. Запровадимо такі поняття:

1. Підграф G'(V', E') графа G(V, E) називають каркасним, якщо V' = V, тобто множини вершин графа G і підграфа G' збігаються.

2. Каркасним деревом графа називають його довільний каркасний підграф, що є деревом.

Ідея пошуку у ширину каркасного дерева полягає у виборі кореня дерева й послідовному визначенні вершин дерева, які можна досягнути з кореня, пройшовши одне ребро, два ребра, три ребра… Таку кількість пройдених ребер називають рівнем вершин. Позначимо:

• V ^T — множина вершин дерева T;
• E ^T — множина ребер дерева T;
• L(v) — рівень вершини v.

V ^T і E ^T порожні на початку виконання алгоритму.

Алгоритм пошуку в ширину каркасного дерева графа

1. Вибрати вершину v₀ початкового графа. Надати значення:
   L(v₀) = 0;
   V ^T = {v₀};
   l = 0.

2. Вибрати вершину v_l з множини V ^T, при якій L(v_l) = l.

3. Вибрати вершину v з різниці множин V \V ^T, що суміжна з v_l.

4. Долучити:

   • вершину v до множини V ^T;
   • ребро (v_l ; v) до множини E ^T

   і надати значення: L(v) = l + 1.

5. Крок 3–4 здійснювати доти, поки не буде розглянуто всі вершини з V \V ^T, що постійно змінюється.

6. Кроки 2–5 здійснювати доти, поки не буде розглянуто всі вершни v_l з множини V ^T, при яких L(v_l) = l.

7. Збільшити величину l на 1.

8. Кроки 2–7 здійснювати до споравдження рівності V = V ^T.

Алгоритм описано у термінах множин, хоча програмне втілення може використовувати лише лінійні масиви (списки). Інколи (як у наступному завданні) розв'язання не потребує побудови самого графа. У цьому випадку усі дії по його побудові зайві.

Завдання 2. Вершини неорієнтованого графа занумеровано послідовними цілими числами, починаючи з 0. Скласти програму для обчислення довжини найкоротшого маршруту від вершини з найменшим номером до усіх вершин.

Вхідні дані. Перший рядок вхідного файлу містить десяткові записи двох чисел: кількість вершин графа й кількість ребер графа. Кожний з наступних рядків містять по два номери вершин, сполучених ребром. Таким чином кожне ребро графа згадано один раз.

Вихідні дані. Єдиний рядок вихідного файлу має містити шукані довжини у порядку зростання номерів вершин.

Наприклад, для таких вхідних даних:

7 8
0 1
0 4
0 6
2 3
2 4
3 4
5 6
5 1

6 — 0 — 4
|   |   | \
5 — 1   2 — 3

Зберегти файл програми у теці з назвою Ваше_прізвище_2 у вказаному вчителем місці. Порівняти створену програму з демонстра­ційним розв'я­занням.

Подане демонстра­ційне розв'я­зання для у випадку незв'язного графа значення функції L залишає нульовим не лише для вершини 0, але й для недосяжних з неї вершин.

Пошук у ширину передбачає у першу чергу пошук вершин, суміжних з даною, а потім здійснюється перехід на новий рівень.

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

Алгоритм пошуку у глибину каркасного дерева графа

1. Усі вершини графа помітити як «нова».

2. Вибирати вершину v₀ початкового графа, яка буде коренем дерева. Замінити її мітку на «використана». Надати значення: v = v₀.

3. Якщо є вершини w, що суміжні (сполучені ребром) з вершиною v і мають мітку «нова», виконати такі дії:

   • вибрати одну з такик вершин w і замінити її мітку на «використана»;

   • надаємо значення v = w і знову почати виконувати пункт 3.

4. Якщо вершина v відмінна від v₀, замінити поточну величину v на її безпосереднього предка і повторити виконання кроку 3.

Зауваження 1. Для перебору всіх можливих дерев за допомогою описаних методів потрібно передбачити перебір усіх можливих множин вершин і відповідних ребер, які можливо долучити на кроках 1 і 3 відповідно.

Завдання 3. Вершини неорієнтованого графа занумеровано послідовними цілими числами, починаючи з 0. Скласти програму для визначення каркасного дерева пошуком у глибину, починаючи з вершини 0.

Вхідні дані. Перший рядок вхідного файлу містить десяткові записи двох чисел: кількість вершин графа й кількість ребер графа. Кожний з наступних рядків містять по два номери вершин, сполучених ребром. Таким чином кожне ребро графа згадано один раз.

Вихідні дані. Кожний рядок вихідного файлу має містити номери вершин ребра каркасного дерева, отриманого у результаті пошуку у глибину з порядком розгляду ребер такому самому, як у вхідному файлі. Порядок ребер у вихідному файлі такий самий, як при долученні до каркасного дерева.

Наприклад, для таких вхідних даних:

7 8
0 1
0 4
0 6
2 3
2 4
3 4
5 6
5 1

0 1
1 5
5 6
0 4
4 2
2 3

6 — 0 — 4
|   |   | \
5 — 1   2 — 3

Зберегти файл програми у теці з назвою Ваше_прізвище_3 у вказаному вчителем місці. Порівняти створену програму з демонстра­ційним розв'я­занням.

5. Закріплення вивченого матеріалу

1. Дати означення графа, ребра, дуги, орієнто­ваного графа, неорієнто­ваного графа, маршруту, циклу, зв'язного графа, дерева.

2. Як обчислити кількість маршрутів певної довжини від однієї вершини графа до іншої?

3. У чому полягає ідея пошуку в ширину?

4. У чому полягає ідея пошуку у глибину?

6. Підбиття підсумків уроку
Виставлення оцінок.

7. Домашнє завдання

1. Вивчити матеріал уроку.

2. При потребі доробити завдання, виконання яких розпочато у класі.

3. Розв'язати задачу «Вуличнi перегони», керуючись вказівками щодо розв'язання.

Матеріал упорядковано Олександром Рудиком.