Застосування теорії графів на вирішення завдань

Курсова.docx

Завдання 12. Марсіани дуже люблять танцювати танці, у яких потрібно братися

за руки. У танці «Дружба» може брати участь не більше 7 марсіан, кожен з яких має не більше трьох рук. Яке найбільше рук може бути в танцюючих, якщо будь-яка рука одного марсіаніна тримає рівно одну руку іншого марсіаніна?

Рішення. Побудуємо граф G, у якому вершини позначатимуть марсіан, і дві вершини з'єднані рубом, якщо відповідні їм марсіани взялися за руки. Тоді ступінь вершини відповідатиме кількості рук марсіаніну, а сума ступенів — числу рук, що беруть участь у танці. За теоремою 1 граф не може мати 7 вершин непарного ступеня. Тому найбільша можлива сума ступенів графа G вийде, якщо граф матиме 6 вершин ступеня 3 та одну вершину ступеня 2. У танцюючих 20 рук.

Завдання 13. Міста країни з'єднані авіалініями. Зі столиці виходить 21 лінія, з міста Далекий — одна, а з кожного з інших міст — по дванадцять ліній. Доведіть, що зі столиці можна долетіти до міста Далекий (можливо, з пересадками).

Рішення. Розглянемо граф G авіаліній, поставивши у відповідність містам країни вершини графа, а авіаліній - ребра. Взагалі кажучи, граф G може виявитися нескладним. Потрібно довести, що вершини графа, що відповідають столиці та місту Далекому, належать до одного компоненту графа. Це випливає зі слідства з теореми 1, тому що в іншому випадку компоненти, що містять вершини, що позначають столицю та місто Далекий, матимуть рівно по одній вершині непарного ступеня. Тому потрібні нам вершини належать одному компоненту графа G, і зі столиці можна долетіти до міста Далекий.

Задача 14. У країні з кожного міста виходить рівно по 12 доріг, якими з будь-якого міста можна дістатисябудь-який інший. Для ремонту закрили одну дорогу. Доведіть, що і тепер з будь-якого міста можна дістатися будь-якої іншої.

Рішення. Для цієї країни збудуємо граф доріг. Ступінь кожної вершини графа дорівнює 12. Для розв'язання задачі слід довести, що видалення будь-якого ребра залишає граф зв'язковим.

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

Завдання 15. У морі мешкають восьминіжки. У кожного з них або один або два друга. Коли зійшло сонце, ті, у кого було двоє друзів, посиніли, а ті, у кого один друг, — почервоніли, і виявилося, що будь-які двоє друзів — різнобарвні. Однак друзі повинні мати однаковий колір, і тому 10 синіх восьминіжок перефарбувалися у червоний колір, а 12 червоних – у синій. Скільки восьминіжок живе в морі?

Рішення. Розглянемо граф G, у якому вершини зображатимуть восьминіжок, і дві вершини будуть з'єднані руба, якщо відповідні їм восьминіжки дружать. Перефарбування восьминіжок визначає таке ж перефарбування відповідних їм вершин графа.

Досліджуємо будову графа G.

З умови випливає, що ступінь кожної вершини графа дорівнює або 1 або 2. Отже, компонентами графа можуть бути лише ланцюги або цикли. Однак після перефарбування всі вершини кожного циклу стануть синіми, що заборонено умовами завдання. Тому цикли у графі G відсутні. Так як після перефарбування всі вершини ланцюгів, крім кінцевих, стануть синіми, то G відсутні ланцюги, що складаються більш, ніж з двох ребер. Отже, компонентами графа G є ланцюги, які з двох ребер. Кінцеві вершини ланцюгів червоні, а центральні сині. У кожному ланцюзі дві вершини червоні, а одна синя. Тому у графі є 6 ланцюгів, у якихвершини перефарбуються у синій колір, і 10 ланцюгів, у яких вершини перефарбуються у червоний колір, лише 16 ланцюгів. Тому у графі G буде 48 вершин, а в морі 48 восьминіжок.

Завдання 16. За столом сидить 5 хлопчиків та 7 дівчаток, а на столі у вазі лежать цукерки. Деякі з дітей знайомі. Кожна дівчинка дала по цукерці із вази знайомому хлопчику, а потім кожен хлопчик дав по цукерці із вази незнайомій дівчинці. Після цього у вазі не залишилося цукерок. Скільки цукерок було у вазі?

Рішення. Поставимо у відповідність дітям вершини графа. З'єднаємо дві вершини зеленим ребром, якщо відповідні хлопчик та дівчинка знайомі, і червоним, якщо незнайомі. Отримаємо повний дводольний граф K5,7, ребра якого розфарбовані у два кольори. У графі 5 7 = 35 ребер. Кожному ребру графа відповідає одно цукерка, оскільки якщо ребро зелене, то цукерку отримує хлопчик, якщо червоне — дівчинка. Отже, у вазі було 35 цукерок.

Завдання 17. У класі 12 хлопчиків та 16 дівчаток. Кожна дівчинка дружить рівно із 3 хлопчиками. Кількість дівчаток, з якими дружать хлопчики, однакова. Зі скільки дівчаток дружить кожен хлопчик?

Рішення. Нехай кожен хлопчик дружить рівно до дівчат. Розглянемо дводольний граф, що описує дружбу хлопчиків та дівчаток. Сума ступенів вершин частки, що відповідає дівчаткам, дорівнює 16 • 3 = 48, а сума ступенів вершин частки, що відповідають хлопчикам, дорівнює 12к. З теореми про суму ступенів вершин часток дводольного графа випливає, що 16 • 3 = 12k. Звідси k = 4 і кожен хлопчик дружить з чотирма дівчинками.

Завдання 18. Кроти, що живуть на лузі, вирішили створити систему тунелів, що з'єднують їхнє житло. Кожен тунель повинен з'єднувати рівно два житла, користуючись тунелями, кожен кріт зможе відвідати будь-яке інше, і для кожних двох жител повиненбути єдиний шлях від одного житла до іншого. Доведіть, що існуватиме кріт, до житла якого вестиме рівно один тунель.

Рішення. Розглянемо граф, де житла будуть вершинами, а тунелі — ребрами. Цей граф дерево. Зв'язність графа випливає з того, що будь-який кріт може відвідати будь-яке інше. У графі відсутні цикли, тому що в іншому випадку для будь-яких двох жител, через які проходить цикл, існує принаймні два шляхи переходу від одного житла до іншого. Існування у графі вершини ступеня 1 випливає з теореми 6. Ця вершина визначає необхідне житло крота.

Завдання 19. Андрій пішов із батьком у тир. Умовляння було таке: Андрій робить п'ять пострілів і за кожне потрапляння отримує право ще на два постріли. Андрій вистрілив 25 разів. Скільки разів він влучив?

Рішення. Стрілянину Андрія можна описати деревом, яке називається кореневим деревом (див. рис.14). У цьому дереві всі вершини, крім верхньої, відповідають пострілам. Якщо Андрій потрапив, то ступінь відповідної вершини дорівнює трьом, якщо промазав одиниці.

Ступінь верхньої вершини дорівнює п'яти. Дерево має 26 вершин та 25 ребер (за теоремою 7). Нехай n – число влучень Андрія. Тоді граф містить n вершин ступеня 3, (25 - n) вершин ступеня 1 і одну вершину ступеня 5. Скористаємося теоремою 1:

Розв'язавши це рівняння, отримаємо n. Андрій потрапив у 10 разів.

Завдання 20. Шість островів річці у парку з'єднані мостами (рис.15). Чи можна, розпочавши прогулянку на одному з островів, пройти по кожному з містків рівно один раз і повернутися на той самий острів? У разі негативної відповіді визначте, скільки містків і між якими островами потрібно побудувати, щоб така прогулянка стала можливою.

Рішення. Побудуємо граф G, у якому кожній ділянці сушіпоставимо у відповідність вершину і з'єднаємо дві вершини рубом тоді і лише тоді, коли відповідні ділянки суші будуть з'єднані мостом (див. рис.16).

Розглянемо побудований граф G. У цьому графі вершини 2 та 4 мають непарний ступінь, отже, граф G не є ейлеровим. Це означає, що бажану прогулянку містками здійснити не можна.

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

Завдання 21. У парку (див. задачу 20) побудували місток, що з'єднує острови 2 і 4. Знайдіть маршрут прогулянки, який починається і закінчується в тому самому місці і проходить кожен місток рівно один раз.

Рішення. Для того щоб знайти необхідний маршрут, потрібно визначити ейлерів цикл у графі G, що описує острови і містки парку.

Для пошуку циклу скористаємось способом доказу теореми Ейлера. Пошук ейлерового циклу почнемо у вершині ПБ. Вийшовши з цієї вершини, для продовження ланцюга щоразу вибиратимемо ще не використане ребро. Припустимо, що отримали цикл С1 = (ПБ, 1, 4, ЛБ, 5, 2, ПБ) (див рис.17).

Видалимо ребра циклу С1 із графа. У графі, що залишився, побудуємо цикл С2 - (1, 3, ЛБ, 6, 5,4, 1). Об'єднаємо цикли С1 і С2 у цикл С = (ПБ, 1, 3, ЛБ, 6, 5, 4, 2, 1, 4, ЛБ, 5, 2, ПБ) за правилом, запропонованим у теоремі Ейлера (як вершина v2 використовується вершина 1).

Завдання 22. Є три будинки та три колодязі. Кожен господар користується будь-яким із трьох колодязів. У деякий момент мешканці будинків посварилися і вирішили прокласти свої доріжки до колодязів так,щоб доріжки не перетиналися. Чи це можливо?

Рішення. Розв'язання задачі про три будинки та три колодязі зводиться до відповіді на запитання: чи є планарним граф К3,3 (рис. 18)?

Спробуймо намалювати граф К3,3 на площині так, як цього вимагає визначення планарності. На будь-якому малюнку графа повинен обов'язково бути присутнім цикл С = (1,4,2,5,3,6, 1), який ділить площину на дві частини: усередині та поза циклом (рис. 19).

Нам залишилося ще намалювати ребра (3,4), (1, 5), (6, 2). Для зображення ребра (3,4) є дві можливості: усередині циклу та поза циклом (рис.20).

Тоді ребро (1,5) у першому випадку можна намалювати лише поза циклом, а в другому — лише всередині (рис. 21).

Останнє ребро (6,2) неможливо намалювати так, щоб воно не мало спільних точок з раніше намальованими ребрами в жодному з цих випадків.

Ми довели, що граф К3,3 не планарний. Це означає, що неможливо провести доріжки від будинків до колодязів належним чином.

Завдання 23. Мерія вирішила побудувати у кожному кварталі міста, що має 155 перехресть та 260 відрізків вулиць між перехрестями, універсам. Скільки буде збудовано універсамів?

Рішення. Карту міста можна вважати плоским графом G, де перехрестя будуть вершинами, а відрізки вулиць — ребрами.

Оскільки квартали міста відповідають внутрішнім граням плоского графа G, знайдемо число граней за формулою Ейлера. Граф G має 155 вершин та 260 ребер. Число граней у ньому:

f = m - n + 2 = 260 - 155 + 2 = 107.

Віднімаємо зовнішню грань. Таким чином, у місті потрібно збудувати 106 універсамів.

Висновок

Ця робота не претендує на повноту дослідження теми «Основи теорії графів». Незважаючи на це, робота буде цікава не лише школярам та студентампедагогічних вузів як відправна точка щодо елементів теорії графів, а й вчителям математики.

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

Використання мови та методів теорії графів часто прискорює вирішення практичних завдань, полегшує розрахунки, підвищує продуктивність наукової, конструкторської думки. Саме запити практики значною мірою сприяють інтенсивному розвитку теорії графів.

Застосування графів допомагає думати, пояснювати, наочно уявляти, тому їх використання має природну тенденцію до розвитку.

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

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

Література

Березіна Л. Ю. Графи та їх застосування: Посібник для вчителів. - М.: Просвітництво, 1979. - 143 с.
Мельников О. І. Теорія графів у цікавих завданнях. Вид. 3-тє, испр. та дод. - М.: Книжковий дім «ЛІБРОКОМ», 2009. - 232 с.
Мендель В. В. Графи та їх застосування. - Журнал "МІФ-2", №1, 2003 р.