Розробка уроку

Тема: способи представлення графів, пошук у ширину та глибину мовою 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. Запровадимо такі поняття:

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

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

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

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

Традиційно вершини графа зображають точками, а ребра — відрізками або кривими, що сполучають зображення відповідних вершин графа.

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

Одержати з переліку ребер (дуг) списки суміжності нескладно:

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

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

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

Позначимо через cjk(m) кількість маршрутів з вершини j до вершини k за m кроків. Маємо:

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

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

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

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

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

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

і m = 5 файл вхідних даних може мати такий вигляд:

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 і E T порожні на початку виконання алгоритму.

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

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

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

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

  4. Долучити:

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

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

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

  6. Кроки 2–5 здійснювати доти, поки не буде розглянуто всі вершни vl з множини V T, при яких L(vl) = 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

вихідний файл повинен містити:

0 1 2 2 1 2 1

Пояснення щодо прикладу даних: описано такий граф:

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

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

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

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

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

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

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

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

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

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

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

  4. Якщо вершина v відмінна від v0, замінити поточну величину 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 перегони», керуючись вказівками щодо розв'язання.


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