Сходинки маленького дослідника: теорія графів
Початок статті про дослідження читайте за
посиланням
Багато з нас поважають математику як серйозну науку, доступну небагатьом.
Доведення теорем нам здається дуже складним, що можуть робити тільки особливі
люди — математики, а всі інші можуть тільки читати їхні доведення і розуміти як
це робиться.
Сьогодні спробую спростувати цю думку, показати Вам, що теореми можна (і потрібно!) доводити самим і це можуть робити навіть молодші школярі. Запрошую Вас у царство Графів. Ви не знаєте що таке граф? Але ж Ви досить часто бачите їх! Читаючи і міркуючи разом зі мною Ви ознайомитеся з теорією графів, зрозумієте як доступно можна розповісти про це дітям, і, головне, зрозумієте навіщо все це потрібно робити.
Задача 13
Обведи малюнок, не відриваючи олівця од паперу і не проводячи двічі по
одній і тій самій лінії.
Покажи, де ти починав обводити фігуру. Стрілочками вкажи, як рухався твій
олівець.
Під час розв’язування таких задач раджу починати досліджувати не одразу, а
тоді, коли у дітей вже з’явиться певний досвід розв’язання задач цього типу.
Потім варто ще раз повернутися до результатів розв’язку перших задач для
підтвердження висунутих гіпотез.
З першого погляду постановка проблеми зрозуміла, а процес розв’язування —
послідовність експериментів. А чи завжди ми будемо певні, що не помилилися?
Звичайно, якщо під час експериментування ми досягли успіху (обвели фігуру, не
відриваючи олівця од паперу і не проводячи двічі по одній і тій самій лінії),
про помилку й мова не йде. А якщо обвести фігуру, згідно умові задачі, не
вдалося? Чи дійсно обвести фігуру неможливо? Можливо, наші експерименти були
помилковими? Як заздалегідь бути певним, що запропоновану фігуру можна або
неможна обвести, не відриваючи олівця од паперу і не проводячи двічі по одній і
тій самій лінії?
Звичайно, точна відповідь вже відома, її давно знайшли вчені-математики.
Результатом їх праці стали добре відомі всім теореми. Але ж цікаво спробувати
самостійно знайти відповідь. Чи зможуть це зробити діти? Так, діти можуть
наблизитися (а іноді й відповісти) на це запитання: за допомогою дорослих знайти
принаймні деякі ознаки фігур, які точно можна обвести, згідно умові задачі, а
які — ні. Розпочнемо дослідження.
Проблему, поставлену умовою задачі, важко одразу осягнути, тому дослідження
проводитиметься поетапно. Проміжні результати етапів можуть бути такими:
- знайти ознаки фігур, які неможна обвести, не відриваючи олівця од паперу;
- знайти ознаки фігур, які можна обвести, не відриваючи олівця од паперу і не проводячи двічі по одній і тій самій лінії;
- знайти ознаки фігур, які можна обвести, не відриваючи олівця од паперу і не проводячи двічі по одній і тій самій лінії, починаючи і закінчуючи обведення в одній і тій самій вершині.
Отже, мета першого етапу визначена. Його результатом буде перелік ознак, за
якими можна точно визначити можна або неможна обвести певну фігуру, не
відриваючи олівця од паперу.
Одразу необхідно визначити, як ми перевірятимемо висунуті гіпотези.
Звичайно, як і завжди, нам допоможе експеримент, але цього разу він буде
особливим. У гіпотезах формулюється узагальнена властивість багатьох фігур,
тому гіпотеза вважається неправильною, якщо вдалося знайти хоча б один приклад
фігури, яка спростовує гіпотезу. Іншими словами контрприклад завжди спростовує
гіпотезу. До речі так перевіряють правильність гіпотез і у наукових
дослідженнях. Правильність гіпотез перевіряти набагато складніше, адже
необхідно за допомогою логічних висновків довести, що гіпотеза діятиме для
будь-яких фігур. Діти це поки-що робити можуть не завжди. Тому в кінці
дослідження варто залишити тільки ті гіпотези, які діти змогли точно
обгрунтувати.
Особливість цього дослідження ще й в тому, що гіпотези важко не тільки
перевіряти, а й висувати. Тому спробуємо навести приклади найпростіших
фігур, які можна і неможна обвести, не відриваючи олівця од паперу, а потім —
порівняємо їх і узагальнимо висновки.
У дітей вже є певний досвід розв’язування таких задач, вони вже бачили і
добре уявляють фігури, які можна обвести, не відриваючи олівця од паперу. Тому
запропонуйте їм намалювати фігури, які неможна обвести, не відриваючи олівця од
паперу. Адже діти ще не розмірковували, як можуть виглядати такі фігури. Через
деякий час вони самостійно або за допомогою дорослого доходять висновку, що
такою фігурою може бути кілька окремих точок.
Чим відрізняються ці фігури одна від одної? Що у них спільного? Ці
запитання допомагають виділити ознаки, за якими по зовнішньому вигляду фігури
можна визначитись щодо можливості обведення фігури, не відриваючи олівця од
паперу. Для цього діти узагальнюють інформацію, отриману за допомогою
прикладів.
Сформульовано першу гіпотезу: якщо фігура складається тільки з
точок, не з’єднаних лініями, її неможливо обвести, не відриваючи олівця од
паперу. Чи правильна вона?
Спробуємо разом з дітьми обгрунтувати її. Наприклад: ми обвели олівцем
будь-яку точку фігури, щоб потрапити до наступної нам потрібна лінія, яка б
з’єднувала їх, інакше необхідно відірвати олівець від паперу.
Здається, що це надто простий висновок. Але ж у математиці це один з
прикладів незв’язних графів! А це не таке вже й просте поняття.
Далі відповімо на запитання: чи тільки такі фігури неможна обвести, не
відриваючи олівця од паперу? Як можна це з’ясувати? Спробуємо навести приклади
фігур з лініями, які неможна обвести, не відриваючи олівця од паперу.
Виходить, якщо до складу будь-якої фігури входить хоча б одна точка, не
з’єднана з іншими частинами фігури, її неможна обвести, не відриваючи олівця од
паперу. У нас з’явилася ще одна гіпотеза. То попередня гіпотеза правильна чи
ні? З одного боку, ці гіпотези одна одній не суперечать, а це головне. З
іншого боку, будь-яка фігура, яка задовольняє вимогам першої гіпотези,
задовольняє і вимогам другої. Інакше кажучи, друга гіпотеза загальніша.
Це дозволяє нам відкинути першу гіпотезу (але якщо ми її залишимо, грубої
помилки не буде, просто перевіряючи фігури ми робитимемо зайву роботу).
І знову перед нами постає запитання: чи тільки такі фігури неможна обвести,
не відриваючи олівця од паперу? Спробуємо знайти інші приклади фігур.
Яка спільна властивість притаманна усім наведеним фігурам? Вони складаються
з кількох маленьких фігур: хоч кожну з них і можна обвести, не відриваючи
олівця од паперу, між ними немає зв’язку. Таким чином сформульовано наступну
гіпотезу: якщо фігура складається з кількох фігур, не пов’язаних між
собою лініями, її неможна обвести, не відриваючи олівця од паперу.
Порівняємо другу і третю гіпотези. З точки зору математики точка — це теж
фігура. Точка — найпростіша фігура. Але не всі діти готові до такого «сміливого»
узагальнення. Вони ще маленькі і не варто наполягати. Отож ці гіпотези
залишаються, їх можна використовувати для перевірки фігур. Усі інші фігури
обвести, не відриваючи олівця од паперу, можна.
Чи висунуто всі гіпотези? Більше не вдається навести прикладів фігур, які
не задовольняють висунутим гіпотезам. Етап дослідження вважаєтимемо завершеним.
Які фігури можна обвести, не відриваючи олівця од паперу і не проводячи
двічі по одній і тій самій лінії? На це запитання має відповісти наступний,
третій, етап дослідження.
Діти вже мають досвід обведення різноманітних фігур, малювали алгоритм
розв’язку таких задач. Вони помітили: деякі фігури ми починали і закінчували
обводити в одній і тій самій вершині фігури, інші — можна обвести тільки, якщо
починати і закінчувати обведення в різних вершинах. На цьому етапі дослідження
нам все одно де ми починаємо і закінчуємо обводити фігуру: на запитання «Чому так
виходить?» відповість останній етап дослідження.
Щоб висунути гіпотези другого етапу дослідження, наведу приклади фігур (як
завжди, почнемо з найпростіших).
Усі ці фігури можна обвести, не відриваючи олівця од паперу і не проводячи
двічі по одній і тій самій лінії. Що спільного у всіх них? Всі вони ламані —
замкнені або незамкнені. Це слушна думка, але діти ще не досить добре знають,
що таке ламана лінія і чим вона відрізняється від інших ліній. Спробуємо знайти
іншу спільну властивість фігур. Для цього намалюємо алгоритми їх обведення.
Розглянемо їх уважно. Для всіх вершин, окрім першої і останньої,
справедливе твердження: завжди одна лінія веде до вершини, інша — веде від
неї. Від першої вершини лінія завжди веде до наступної, також одна лінія
завжди веде до останньої вершини.
Довести це твердження ми можемо за допомогою наступних міркувань. Якщо ми
обводимо фігуру, не відриваючи олівця од паперу і не проводячи двічі по одній і
тій самій лінії, то до кожної вершини маємо довести олівець по окремій лінії і
по іншій лінії довести олівець до наступної вершини. Щоб здійснити це, кожна
вершина повинна мати принаймні дві лінії. Тільки перша і остання вершини можуть
мати по одній лінії: від першої вершини ми потрапляємо до другої вершини і
потім можемо до неї не повернутися; по одній лінії ми потрапляємо в останню
вершину і закінчуємо обведення фігури. Перевіримо висунуту нами гіпотезу.
Наведені приклади показують: як тільки хоча б від одної з вершин, крім
першої і останньої, відходить більше або менше двох ліній, фігуру неможна
обвести, не відриваючи олівця од паперу і не проводячи двічі по одній і тій
самій лінії.
Таким чином, перша гіпотеза дослідження наступна. Якщо від кожної
вершини фігури відходить по дві лінії, то її можна обвести, не відриваючи
олівця од паперу і не проводячи двічі по одній і тій самій лінії. У фігур, які
є незамкненеми лініями, тільки від першої і останньої вершин може відходити по
одній лінії.
Перевіримо правильність висунутої гіпотези. Наведемо інші приклади фігур,
які можна обвести, не відриваючи олівця од паперу і не проводячи двічі по одній
і тій самій лінії.
Як ми вже помітили, в таких задачах немає значення пряма лінія чи зігнута.
Важливе значення має тільки кількість ліній, що відходять од кожного кута
фігури. Це тому, що кожна така фігура в математиці розглядається як граф —
сукупність ліній і точок (вершин фігури), обидва кінця кожної лінії обов’язково
закінчуються точками. Діти про це ще не знають (в технології «Логіки світу»
поняття «граф» не розглядається зовсім), і ми не повинні підкреслювати різницю
між лініями фігури. Будь-які лінії фігури ми називатимемо просто «лінія», і
шукатимемо інші властивості кутів фігури.
Усі фігури, наведені вище, можна обвести, не відриваючи олівця од паперу і
не проводячи двічі по одній і тій самій лінії. Але жодна з них не задовольняє
умовам нашої першої гіпотези: майже від усіх вершин відходить більше двох
ліній — чотири або шість. Можна навести й інші приклади, де ліній буде ще
більше. Таким чином настав час узагальнити гіпотезу.
Яка спільна властивість притаманна наведеним фігурам? Ще раз полічімо
кількість ліній, які відходять від усіх вершин, — 2, 4, 6, 8... Добре видно, що
всі ці числа парні. Отож, гіпотеза уточнюється. Якщо від
кожної вершини фігури відходить парна кількість ліній, то її можна обвести, не
відриваючи олівця од паперу і не проводячи двічі по одній і тій самій лінії.
У фігур, які є незамкненеми лініями, тільки від першої і останньої вершин
може відходити по одній лінії.
Наступні міркування підтверджують гіпотезу. Якщо від будь-якої вершини
відходить більше двох ліній, то ми маємо кілька разів провести олівець через цю
вершину. Щоб двічі не проводити по одній і тій самій лінії, нам потрібні ще дві
лінії: для «входу» і «виходу» з вершини. Таким чином, кожна вершина, крім
першої і останньої, повинна мати кілька пар ліній. Скільки разів лінія приведе
олівець до вершини, стільки ж разів олівець повинен вийти з вершини по іншій
лінії. Перевіримо гіпотезу (див. малюнок).
Зверніть увагу: до кожної фігури, наведеної на попередньому малюнку, додано
лише одну лінію, від двох вершин кожної з фігур відходить непарна кількість
ліній, але їх все одно можна обвести, не відриваючи олівця од паперу і не
проводячи двічі по одній і тій самій лінії. Жодна з цих фігур не задовольняє
умові попередньої гіпотези. Тобто попередня гіпотеза не відкидається і ми
знайшли ще одну властивість фігур.
Наступна гіпотеза формулюється так. Якщо від кожної
вершини фігури відходить парна кількість ліній і фігура має тільки дві вершини,
від яких відходить непарна кількість ліній, то її можна обвести, не відриваючи
олівця од паперу і не проводячи двічі по одній і тій самій лінії. Якщо вершин з
непарною кількістю ліній лише дві, то останньою нашою дією під час обведення фігури
буде проведення олівця по «непарній» лінії з одної вершини в іншу. Якщо вершин
з непарною кількістю ліній більше двох, то під час обведення друга «непарна»
лінія або залишається необведенною, або нам необхідно провести по певній лінії
двічі, щоб довести олівець до цієї лінії і обвести її.
Прикладів, які не задовольняють висунутим гіпотезам, навести не вдається.
Таким чином, другий етап дослідження закінчено: ми сформулювали дві правильні
гіпотези. Якщо фігура задовольняє будь-якій з них, її можна обвести, не
відриваючи олівця од паперу і не проводячи двічі по одній і тій самій лінії.
Тепер зосередимо свою увагу на тих вершинах, де ми починали і закінчували
обведення фігур.
Порівнюючи алгоритми обведення фігур, ми помітили: обводячи одні фігури ми
починали і закінчували в одній і тій самій вершині, у інших фігур початок і
кінець обведення відбувався у різних вершинах. Спробуємо знайти ознаку фігур,
які можна обвести, починаючи і закінчуючи в одній і тій самій вершині.
Порівняємо фігури на малюнку. Одразу помітно, що обвести фігури у другому
рядку можна тільки, якщо починати і закінчувати у двох різних вершинах. Про
це свідчать і спроби дітей починати обведення в інших вершинах. Чим вони
відрізняються від усіх інших вершин? Від них відходить непарна кількість
ліній. Також помітно, що обвести фігури, починаючи і закінчуючи в одній
вершині, можна тільки, якщо від усіх вершин фігури відходить парна кількість
ліній.
Тому можна висунути наступну гіпотезу. Якщо від кожної вершини
фігури відходить парна кількість ліній, то її можна обвести, не
відриваючи олівця од паперу і не проводячи двічі по одній і тій самій лінії,
починаючи і закінчуючи в одній і тій самій вершинах. Якщо від кожної вершини
фігури відходить парна кількість ліній і фігура має тільки дві вершини,
від яких відходить непарна кількість ліній, то її можна обвести, не
відриваючи олівця од паперу і не проводячи двічі по одній і тій самій лінії,
починати і закінчути обведення ми можемо тільки у різних вершинах.
Щоб упевнитися в правильності висунутої гіпотези, варто ще раз розглянути
всі фігури, які ми обводили у попередніх задачах.
Звичайно, не всі наші висновки строго сформульовані і доведені з точки зору класичної математики. Але їх робили першокласники. Звичайні діти, не вундеркінди. Пізніше, у старших класах, це дослідження можна повторити і сформулювати висновки так, як прийнято у теорії графів.
А зараз дозволю собі маленький відступ у теорію графів. Ось основні поняття і теореми, які нам потрібні (деякі поняття я подаю, на інтуїтивному рівні).
Ейлерів шлях у графі — це шлях, який охоплює всі ребра графа.
Ми побудували ейлерові шляхи в усіх розв’язаних задачах.
Ейлерів цикл у графі — це цикл, який охоплює всі ребра
графа. Ми побудували такі ейлерові цикли:
Ми починали і закінчували обводити ці графи в одній і тій самій вершині.
Теорема 1. Якщо граф зв’язний (кожні дві вершини графа
пов’язані) і всі його вершини парні (мають парну кількість ліній), то в ньому є
ейлерів цикл. (Пригадайте нашу останню гіпотезу.)
Теорема 2. Якщо граф зв’язний та А і В єдині непарні його
вершини, то у графі є ейлерів шлях з кінцями А і В (початок і кінець не
обов’язково в одній і тій самій вершині, строго кажучи, цикл — це один з
прикладів шляху).
Приклади ейлерових шляхів дивіться на малюнку.
Ці теореми також допоможуть нам узагальнити попередні висновки і ми зможемо
швидше перевіряти розв’язування дітей.
От нібито я сьогодні закінчила публікацію циклу статей «Дослідження по-дорослому», але точку не ставлю, адже про дослідження йдеться у багатьох статтях про технологію «Логіки світу»: на сторінках блогу ми слухаємо (досліджуємо) музику, роздивляємося (досліджуємо) картини, розв’язуємо (досліджуємо) задачі… Сподіваюсь, наступні приклади Ви наведете самі. До зустрічі на сторінках блогу «Інформація і МИ», у FaceBook, Pinterest, Google+…
Щасти!
науковий співробітник Міжнародного науково-навчального
центру інформаційних технологій та систем Національної академії наук України
та Міністерства освіти і науки України,
автор технології «Логіки світу»
для дітей від 4 до 12 років
