Графи. Застосування графів для вирішення завдань
1. Методичні поради до теми “Графи”.
Поняття графа доцільно вводити після того, як розібрано кілька завдань, подібних до завдання 1, вирішальне міркування в яких – графічне уявлення. Важливо, щоб учні відразу усвідомили, що той самий граф може бути намальований різними способами. Суворе визначення графа, мій погляд, давати не треба, т.к. воно надто громіздке і це тільки ускладнить обговорення. Спочатку вистачить і інтуїтивного поняття. Під час обговорення поняття ізоморфізму можна вирішити кілька вправ визначення ізоморфних і неізоморфних графів. Одне з центральних місць теми – теорема про парність числа непарних вершин. Важливо, щоб учні до кінця розібралися у її доказі та навчилися застосовувати до вирішення завдань. При розборі кількох завдань рекомендую не посилатися теорему, а фактично повторювати її доказ. Надзвичайно важливим є також поняття зв'язності графа. Змістовним міркуванням тут розгляд компоненти зв'язності, цього необхідно звернути особливу увагу. Ейлерові графи – тема майже ігрова.
Перша і головна мета, яку слід переслідувати щодо графів, –навчити школярів бачити граф за умови завдання і грамотно перекладати умову на мову теорії графів. Не варто розповідати обидві всім на кількох заняттях поспіль. Краще рознести заняття за часом на 2–3 навчальні роки. (Додається розробка заняття "Поняття графа. Застосування графів до вирішення завдань" у 6 класі).
2. Теоретичний матеріал до теми "Графи".
Графи – чудові математичні об'єкти, з допомогою можна вирішувати дуже багато різних, зовні не схожих друг на друга завдань. У математиці існує цілий розділ - теорія графів, який вивчає графи, їх властивості та застосування. Ми ж обговоримотільки основні поняття, властивості графів і деякі способи вирішення завдань.
Розглянемо дві задачі.
Завдання 1.Між дев'ятьма планетами сонячної системи встановлено космічне повідомлення. Рейсові ракети літають наступними маршрутами: Земля - Меркурій; Плутон – Венера; Земля – Плутон; Плутон – Меркурій; Меркурій – Відні; Уран - Нептун; Нептун - Сатурн; Сатурн - Юпітер; Юпітер – Марс та Марс – Уран. Чи можна долетіти на рейсових ракетах із Землі до Марса?
Рішення: Намалюємо схему умови: планети зобразимо точками, а маршрути ракет – лініями.
Тепер одразу видно, що долетіти із Землі до Марса не можна.
Завдання 2.Дошка має форму подвійного хреста, який виходить, якщо з квадрата 4x4 прибрати кутові клітини.
Чи можна обійти її ходом шахового коня і повернутися на вихідну клітину, побувавши на всіх клітинах рівно по одному разу?
Рішення: Занумеруємо послідовно клітини дошки:
А тепер за допомогою малюнка покажемо, що такий обхід таблиці, як зазначено в умові, може бути:
Ми розглянули два несхожі завдання. Проте вирішення цих двох завдань поєднує загальна ідея – графічне уявлення рішення. При цьому і картинки, намальовані для кожного завдання, виявилися схожими: кожна картинка – це кілька точок, деякі з яких з'єднані лініями.
Такі картинки називаються графами. Крапки у своїй називаються вершинами, а лінії – ребрами графа. Зауважимо, що не кожна картинка такого виду називатиметься графом. Наприклад. якщо вас попросять намалювати у зошиті п'ятикутник, то такий малюнок графом не буде. Будемо називати що малюнок такого виду, як у попередніх завданнях, графом, якщо є якесь конкретне завдання, для якого такий малюнок побудований.
Інше зауваженнястосується виду графа. Спробуйте перевірити, що граф для однієї і тієї ж задачі можна намалювати різними способами; і навпаки для різних завдань можна намалювати однакові на вигляд графи. Тут важливо лише те, які вершини з'єднані одна з одною, а які – ні. Наприклад, граф для задачі 1 можна намалювати по-іншому:
Такі однакові, але по-різному намальовані графи називаються ізоморфними.
Ступіні вершин та підрахунок числа ребер графа
Запишемо ще одне визначення: Ступенем вершини графа називається кількість ребер, що виходять з неї. У зв'язку з цим, вершина, що має парний ступінь, називається парною вершиною, відповідно, вершина, що має непарний ступінь, називається непарною вершиною.
З поняттям ступеня вершини пов'язана одна з основних теорем теорії графів - теорема про чесність числа непарних вершин. Доведемо її трохи пізніше, а спочатку для ілюстрації розглянемо завдання.
Теорема: Будь-який граф містить парне число непарних вершин.
Доказ: Кількість ребер графа дорівнює половині суми ступенів його вершин. Оскільки кількість ребер має бути цілим числом, то сума ступенів вершин має бути парною. А це можливо лише в тому випадку, якщо граф містить парне число непарних вершин.
Є ще одне важливе поняття, що стосується графів – поняття зв'язності.
Граф називається зв'язковим, якщо будь-які дві його вершини можна з'єднати шляхом, тобто. безперервною послідовністю ребер. Існує ціла низка завдань, вирішення яких засноване на понятті зв'язності графа.
Завдання 4.У країні Сімка 15 міст, кожен із міст з'єднаний дорогами щонайменше, ніж із сімома іншими. Доведіть, що з кожного міста модно дістатися будь-якої іншої.
Доказ: Розглянемо двадовільних А і В міста і припустимо, що між ними немає шляху. Кожен з них з'єднаний дорогами не менше, ніж з сімома іншими, причому немає такого міста, яке було б з'єднане з обома розглянутими містами (інакше існував би шлях з A до B). Намалюємо частину графа, що відповідає цим містам:
Тепер очевидно, що ми отримали щонайменше різних 16 міст, що суперечить умові завдання. Отже, твердження доведене від протилежного.
Якщо взяти до уваги попереднє визначення, то затвердження завдання можна переформулювати й інакше: "Довести, що граф доріг країни Семерка пов'язаний."
Тепер ви знаєте, як виглядає зв'язковий граф. Незв'язний граф має вигляд кількох “шматків”, кожен із яких – чи окрема вершина без ребер, чи зв'язковий граф. Приклад незв'язного графа ви бачите малюнку:
Кожен такий окремий шматок називається компонентом зв'язності графа. Кожна компонента зв'язності є зв'язковим графом і для неї виконуються всі твердження, які ми довели для зв'язкових графів. Розглянемо приклад задачі, в якій використовується компонент зв'язності:
Завдання 5. У Тридев'ятому царстві лише один вид транспорту – килим-літак. Зі столиці виходить 21 ковролінія, з міста Далекий – одна, а з усіх інших міст, – по 20. Доведіть, що зі столиці можна долетіти до міста Далекого.
Доказ: Зрозуміло, якщо намалювати граф ковроліній Царства, він може бути нескладним. Розглянемо компоненту зв'язності, що включає столицю Царства. Зі столиці виходить 21 ковролінія, а з будь-яких інших міст, крім міста Далекий – по 20, тому, щоб виконувався закон про парне число непарних вершин необхідно, щоб і місто Далеке входило в цю ж саму компоненту зв'язності. А такяк компонента зв'язності - зв'язковий граф, то зі столиці існує шлях по ковролінії до міста Далекий, що і вимагалося довести.
Ви, напевно, стикалися з завданнями, в яких потрібно намалювати будь-яку фігуру, не відриваючи олівець від паперу і проводячи кожну лінію лише один раз. Виявляється, що таке завдання не завжди можна розв'язати, тобто. існують фігури, які вказаним способом намалювати не можна. Питання розв'язності таких завдань також належить до теорії графів. Вперше його досліджував у 1736 році великий німецький математик Леонард Ейлер, вирішуючи завдання про Кенігсберзькі мости. Тому графи, які можна намалювати вказаним способом, називаються графами Ейлера.
Завдання 6.Чи можна намалювати зображений на малюнку граф не відриваючи олівець від паперу і проводячи кожне ребро рівно один раз?
Рішення. Якщо ми малюватимемо граф так, як сказано в умові, то в кожну вершину, крім початкової та кінцевої, ми увійдемо стільки ж разів, скільки вийдемо з неї. Тобто всі вершини графа, крім двох, мають бути парними. У нашому ж графі є три непарні вершини, тому його не можна намалювати вказаним за умови способом.
Зараз ми довели теорему про Ейлерові графи:
Теорема: Ейлерів граф повинен мати не більше двох непарних вершин.
І насамкінець – завдання про Кенігсберзькі мости.
Завдання 7.На малюнку зображено схему мостів міста Кенігсберга.
Чи можна прогулятися так, щоб пройти по кожному мосту рівно 1 раз?
3. Завдання до теми "Графи"
Поняття графа.
1. На квадратній дошці 3x3 розставлено 4 коня так, як показано на рис.1. Чи можна зробивши кілька ходів кіньми, переставити в положення, показане на рис.2?
Мал. 1
Мал. 2
Рішення. Занумеруємо клітини дошки, як показано на малюнку:
Кожній клітині поставимо у відповідність точку на площині і, якщо з однієї клітини можна потрапити в іншу ходом шахового коня, відповідні точки з'єднаємо лінією. Вихідна та необхідна розстановка коней показана на малюнках:
 |  |
При будь-якій послідовності ходів конями порядок їхнього прямування, очевидно, змінитися не може. Тому переставити коней необхідним чином неможливо.
2. У країні Цифра є 9 міст з назвами 1, 2, 3, 4, 5, 6, 7, 8, 9. Мандрівник виявив, що два міста з'єднані авіалінією в тому і лише в тому випадку, якщо двозначне число, утворене назвами міст, ділиться на 3. Чи можна долетіти повітрям з міста 1 до міста 9 ?
Рішення. Поставивши у відповідність кожному місту точку і з'єднавши точки лінією, якщо сума цифр ділиться на 3, отримаємо граф, у якому цифри 3, 5, 9 пов'язані між собою, але з іншими. Значить долетіти з міста 1 до міста 9 не можна.
Ступені вершин та підрахунок числа ребер.
3. У державі 100 міст до кожного міста виходить 4 дороги. Скільки всього доріг у державі.
Рішення. Підрахуємо загальну кількість вихідних міст доріг – 100. 4 = 400. Однак за такого підрахунку кожна дорога порахована 2 рази – вона виходить з одного міста і входить до іншого. Отже всього доріг вдвічі менше, тобто. 200.
4. У класі 30 осіб. Чи може бути так, що 9 осіб мають по 3 друга, 11 – по 4 друга, а 10 – по 5 друзів?
Відповідь. Ні (теорема про парність числа непарних вершин).
5. У короля 19 васалів. Чи може виявитися так, що у кожного васала 1, 5 чи 9 сусідів?
Відповідь. Ні не може.
6. Чи може в державі, в якій з кожного міста виходить рівно 3 дороги, бути рівно 100 доріг?
Рішення. Підрахуємо кількість міст. Число доріг дорівнює числу міст х, помноженому на 3 (кількість доріг, що виходять з кожного міста) і розділеному на 2 (див. задачу 3). Тоді 100 = Зх/2 = gt; Зх = 200, чого не може бути при натуральному х. Отже, 100 доріг у такій державі бути не може.
7. Доведіть, що кількість людей, які коли-небудь жили на Землі і зробили непарну кількість рукостискань, парна.
Доказ безпосередньо випливає з теореми парності числа непарних вершин графа.
Зв'язок.
8. У країні з кожного міста виходить 100 доріг і з кожного міста можна дістатися будь-якого іншого. Одну дорогу закрили на ремонт. Доведіть, що й тепер із будь-якого міста можна дістатися будь-якого іншого.
Доведення. Розглянемо компоненту зв'язності, до якого входить одне з міст, дорогу між якими закрили. По теоремі парності числа непарних вершин до неї входить і друге місто. А отже, як і раніше, можна знайти маршрут і дістатися з одного з цих міст до іншого.
Графи Ейлера.
9. Є група островів, з'єднаних мостами отже кожного острова можна дістатися будь-якого іншого. Турист обійшов усі острови, пройшовши по кожному мосту по-різному 1 раз. На Троєкратному острові він побував тричі. Скільки мостів веде з Троєразового, якщо турист
а) чи не з нього почав і не на ньому закінчив? б) з нього почав, але не на ньому закінчив? в) з нього почав і на ньому закінчив?
10. На малюнку зображено парк, розділений на кілька частин огорожами. Чи можна прогулятися парком та його околицями так, щоб перелізти через кожен паркан по-різному 1 раз?