у прикладу, у графі ребер, тобто було 30 пісень.
Звернути увагу на те, що ребра вважати легше, ніж пісні або проводу. Ребра легко зображати, саме ця властивість (наочність) зумовило настільки широке поширення графів.
Завдання 5. Чи можна намалювати графи, зображені на ріс.1.4.3а і на ріс.1.4.3б, не відриваючи олівець від паперу і проводячи кожне ребро один раз?
рис. 1.4.3а ріс.1.4.3б
Рішення. а можна. Наприклад, послідовність вершин може бути такою: 1-2-3-1-4-2-5-3-4. б) Оскільки з кожної вершини (крім першої і останньої) ми виходимо стільки ж разів, скільки входимо, ступеня цих вершин повинні бути парними. У графі на рис. 1.4.3б всі чотири вершини мають ступінь 3, тому його не можна намалювати, не відриваючи олівця від паперу.
Можливо, вам знайома аналогічна задача про відкритий конверт (або будиночок). (ріс.1.4.4)
ріс.1.4.4
Завдання 6. Схема мостів Кенігсберга зображена на рис. 1.4.5. Чи можна здійснити прогулянку, пройшовши по кожному мосту рівно один раз?
ріс.1.4.5
Вказівка. Побудуйте граф, вершинами якого є частини міста Кенігсберг (для зручності можна назвати їх латинськими літерами або пронумерувати), а ребрами - мости.
Задачa 7. У кутах шахівниці 33 стоять 4 коня: 2 білих (в сусідніх кутах) і два чорних (ріс.1.4.6а). Чи можна за кілька ходів (по шаховими правилами) поставити коней так, щоб у всіх сусідніх кутах стояли коні різного кольору?
ріс.1.4.6а ріс.1.4.6б ріс.1.4.6в
Рішення. Відзначимо центри клітин дошки і з'єднаємо відрізками пари зазначених точок, якщо з однієї в іншу можна перейти кроком коня (кінь ходить буквою Г). Ми отримали граф (рис. 1.4.6б). У ньому є ізольована вершина (зауваження 1), це вершина 5. Спробуйте обійти всі інші вершини графа і повернутися у вихідну вершину. У вас повинно вийти, адже ребра і всі вершини, крім вершини 5, утворюють ейлерів граф, що містить цикл. Переміщення коней по дошці відповідає руху по ребрах цього циклу. Для графа на ріс.1.4.6 (б) зображений ізоморфний граф (ріс.1.4.6 в і зауваження 2). Ясно, що при русі по циклу не можна змінити порядок проходження коней.
Зауваження.
. Вершини, з яких не виходить жодного ребра, називаються ізольованими.
. Корисно уявити граф як набір гудзиків, деякі з яких з'єднані нитками. При цьому, де саме розташовані ґудзики, і як проходять нитки - не важливо: граф від цього не змінюється, важливо лише те, які пари ґудзиків (вершини) з'єднані нитками.
Завдання 8. Чотири учениці: Марія, Ніна, Оля і Юля брали участь у лижних змаганнях і зайняли 4 перших місця. На питання, хто яке місце зайняв, вони дали три різних відповіді:
Перший: Ольга посіла перше місце, Ніка - друге.
Другий: Ольга посіла друге місце, Юля - третє.
Третій: Марія посіла друге місце, Юля - четверте.
відповідаю учениці при цьому визнали, що одне з висловлювань кожної відповіді вірно, а інше невірно. Яке місце зайняла кожна з учениць?
Рішення.
12341234Мария-+-Мария-+--Нина-+--Нина---+Оля---Оля+---Юля--+-Юля--+-Предположим, що Оля зайняла не перше місце і отримаємо, що Марія і Ніна посіли друге місце, що неможливо за умовою задачі.Пусть Оля зайняла перше місце, отже, Ніна не посіла друге і т.д. Отримуємо вірне рішення.
Завдання 9. На малюнку 1.4.7 зображені відстані між пунктами A, B, C, D, E і F. Рухатися по дорогах можна тільки в напрямках, зазначених стрілочками. Водій їде з пункту А в пункт Е. Як він повинен їхати, щоб добратися по найкоротшому шляху?
D C
E A
F B
ріс.1.4.7
Рішення. Розглянемо послідовно можливі шляхи поїздки і порівняємо їх довжину. ABFE=14, ABFCDE=15, ABFDE=13, ACDE=16.Виберем найменша відстань. Воно дорівнює 13, значить потрібно їхати за маршрутом ABFDE.
Завдання 10. Аркуш паперу Плюшкін розрізав на 3 частини. Деякі з отриманих листів він також розрізав на три частини. Кілька нових листочків він знову розрізає на три більш дрібні частини і т.д. Скільки Плюшкін отримує листків, якщо розрізає k листків?
Рішення. Листки паперу позначимо на малюнку гуртками. Гуртки, відповідні листам, які розрізаються, закрасимо цілком; решта гуртки залишимо НЕ зафарбованими. На малюнку 1.4.9 видно, що при розрізанні одного аркуша на 3 частини число листків збільшується на два. Якщо ж розрізано k листків, то утворилося 1+ 2k листів.
рис. 1.4.9
Розглянувши основні положення теорії графів, покажемо далі, як можна реалізувати цю теорії при вирішенні завдань на факультативних заняттях у школі [12].
...
