Графи та їх застосування

Размещено на http://www.allbest.ru/

Кафедра математичного аналізу

КУРСОВА РОБОТА

на тему

«Графи та їх застосування»

Зміст

• Вступ 3
• Розділ 1 5
• 1.1 Застосування теорії графів 5
• 1.2 Що таке граф? 6
• 1.3 Основні строгі означення теорії графів 9
• Розділ 2 14
• 2.1 Графи в логічних задачах 14
• 2.2 Елементи теорії графів у задачах 23
• 2.3 Задачі на використання дерев 272
• Висновки 31
• Література 32

Вступ

Перша робота з теорії графів, що належить відомому швейцарському математику Л. Ейлеру, з'явилася в 1736 р. Спочатку теорія графів здавалася досить незначним розділом математики, так як вона мала справу в основному з математичними розвагами й головоломками. Однак подальший розвиток математики і особливо її додатків дало сильний поштовх розвитку теорії графів. Вже в XIX столітті графи використовувалися при побудові схем.

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

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

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

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

Розділ 1

1.1 Застосування теорії графів

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

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

Наприклад, у вигляді графа можуть бути зображені:

Ш електричні і транспортні мережі;

Ш інформаційні і комп'ютерні мережі;

Ш карти автомобільних, залізничних і повітряних шляхів, газо- і нафтопроводів;

Ш моделі кристалів;

Ш структури молекул хімічних речовин;

Ш моделі ігор;

Ш різні математичні об'єкти (відношення, частково впорядковані множини, решітки, автомати, ланцюги Маркова, алгоритми і програми тощо);

Ш лабіринти;

Ш плани діяльності або плани виконання певних робіт (розклади);

Ш генеалогічні дерева тощо.

Приклади застосування теорії графів:

Ш пошук зв'язних компонентів у комунікаційних мережах;

Ш пошук найкоротших, “найдешевших” та “найдорожчих” шляхів у комунікаційних мережах;

Ш побудова кістякового дерева: зв'язність з найменшою можливою кількістю ребер;

Ш пошук максимальної течії для транспортної мережі, в якій визначено вхідні та вихідні вершини та пропускні спроможності ребер;

Ш ізоморфізм графів: ідентичність структур молекул (ізометрія);

Ш знаходження циклів графів:

Ш гамільтонів цикл: обійти всі вершини графа, побувавши в кожній з них лише один раз (задача комівояжера);

Ш ейлерів цикл: обійти всі ребра (контроль дієздатності мережі);

Ш розфарбування графів: розфарбування географічних карт, укладання розкладів, розміщення ресурсів тощо;

Ш планарність графів: проектування друкованих електронних та електричних схем, транспортних розв'язок тощо;

Ш знаходження центрів графа: вершин, максимальна відстань від яких до всіх інших вершин графа є мінімальною (“столиць”)

тощо.

1.2 Що таке граф

Для початку розглянемо рис. 1.1 і 1.2, на яких зображено відповідно ділянка електричного кола і частина карти дороги. Ясно, що обидва малюнка можуть бути представлені однією і тією ж самою діаграмою з точок і ліній, що зображені на рис. 1.3. Точки Р, Q, R , S i T називаються вершинами, лінії називаються ребрами, а вся діаграма називається графом. Степенем вершини називається число ребер, кінцем якої являється дана вершина; на рис. 1.2 це відповідає числу доріг, що сходяться у перехресті; так, степінь вершини Q рівна 4.



Розглянуті ситуації можна описати іншим графом, що зображений на рис. 1.4.

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

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

Розглянутий раніше граф, «простий» у тому сенсі, що у ньому будь-яку пару вершин з'єднує не більш ніж одне ребро. Припустимо, що дороги від Q до S і від S до T (рис 1.5) занадто загружені і для їх розгрузки проклали паралельні дороги, що з'єднують ті самі точки; тоді діаграма буде виглядати так, як на рис. 1.6 (ребра, що з'єднують Q з S або S з T, називаються кратними). Якщо ж ми ще хочемо побудувати гараж в пункті P, то на діаграмі це можна відмітити ребром, що проходить з Р в Р; таке ребро звичайно називають петлею (рис 1.7); графи що не містять петель називатимемо простими.

Багато уваги приділяється в теорії графів вивченню різного роду ланцюгів; під ланцюгом розуміється послідовність ребер, що йдуть один за одним. Так наприклад на рис. 1.5 один із способів потрапити з Р в R описується ланцюгом Р >Q>R довжини 2; аналогічно, P>S>Q>T>S>R є ланцюг довжини 5. По очевидним міркуванням ланцюг виду Q>S>T>Q називається циклом. Граф, у якому будь-які 2 вершини з'єднані ланцюгом називається зв'язковим графом.

1.3 Основні означення теорії графів

Теорія графів - математична дисципліна , створена зусиллями математиків, тому її виклад містить у собі і необхідні строгі визначення. Отже, приступимо до організованого та чіткого введення основних понять цієї теорії.

Означення 1. Графом називається скінченна сукупність точок, які називаються вершинами графа, і попарно з'єднують деякі з цих вершин ліній, званих ребрами або дугами графа (рис. 2.1)

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

Надалі вершини графа ми будемо позначати латинськими літерами A, B, C, D. Іноді граф в цілому будемо позначати однією великою літерою.

Означення 2. Вершини графа, які не належать жодному ребру, називають ізольованими.



Означення 3. Граф, що складається лише з ізольованих графів, називається нуль-графом (рис. 2.2).

Означення 4. Граф, в якому кожна пара вершин з'єднана ребром, називається повним.

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

Означення 6. Граф, степінь всіх k вершин якого однакові, називається однорідним графом степеня k (рис. 2.3 - граф 4 степеня).

Означення 7. Доповненням даного графа називається граф, що складається з всіх ребер і їх кінців, які необхідно додати до вихідного графа, щоб отримати повний граф.

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

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

Означення 10. Шляхом від A до X називається послідовність ребер, що веде від A до X, така, що кожні два сусідніх ребра мають загальну вершину, і ніяке ребро не зустрічається більше одного разу.

Означення 11. Циклом називається шлях, в якому співпадають початкова і кінцева точка. На рис. 2.1 послідовність ребер AFEDFBCA являє собою цикл.

Означення 12. Простим циклом називається цикл, що не проходить через одну з вершин графа більше одного разу. На рис. 2.1 послідовність ребер ACBFEDA являє собою простий цикл.

Означення 13. Довжиною шляху, що прокладений у циклі, називається число ребер цього шляху.

Означення 14. Дві вершини A и B у графі називаються зв'язними (незв'язними), якщо в ньому існує (не існує) шлях, що веде з A в B.

Означення 15. Граф називається зв'язним, якщо кожні дві його вершини зв'язні; якщо ж в графі знайдеться хоча б одна пара незв'язних вершин, то граф називається незв'язним. На рис. 2.5 зображений граф, що складається з 4 зв'язних елементів, один з яких представляє собою ізольовану вершину.

Означення 16. Деревом називається зв'язний граф, який не містить циклів. Тривимірною моделлю графа-дерева служить, наприклад, справжнє дерево з його хитромудро розгалуженою кроною; ріка та її притоки також утворюють дерево, але вже плоске - на поверхні землі. Для того, щоб побудувати дерево, виберемо деяку вершину виберемо деяку вершину А₀. З А₀ проведемо ребра в сусідні вершини А₁, А₂,…, з них проведемо ребра до їх сусідів А₁₁, А₁₂,…, А₂₁, А₂₂,… і так далі (рис. 2.6)

Означення 17. Незв'язний граф, що складається виключно з дерев, називається лісом (не містить циклів).

Означення 18. Дерево, всі n вершин якого мають номери от 1 до n, називають деревом с пронумерованими вершинами.

Отже, ми розглянули основні визначення теорії графів, без яких було б неможливо доказ теорем, а, отже і рішення задач.

Розділ 2

2.1 Графи і логічні задачі

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

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

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

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

Задача № 1.1

Розмовляють троє друзів: Білокуров, Чорнов і Рудов. Брюнет сказав Білокурову: «От що цікаво, що один з нас білявий, інший брюнет, третій рудий, але у жодного колір волосся не відповідає прізвищу». Якого кольору волосся у кожного з трьох друзів?

Розв'язання. Побудуємо граф відношення, заданого в умові задачі. Для цього перш за все, виділимо множину прізвищ М і множину кольорів волосся К, елементи яких позначимо точками. Точки множини М назвемо буквами Б, Ч і Р ( Білокуров, Чорнов і Рудов ); точки другої множини - б, бр, р (білявий, брюнет, рудий). Точці однієї множини відповідає точка з другого і їх можна об'єднати суцільною лінією, а якщо не відповідає - штриховою. Умова задачі вказує лише на невідповідності, тому спочатку має виникнути граф зображений на рис. 1.

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



Принцип розв'язання задачі простий. Якщо якась точка виявляється з'єднаною з двома точками другої множини штриховими лініями, то з третьою точкою її необхідно з'єднати суцільною лінією. Саме тому граф на рис. 1 доповнюється суцільними лініями, що з'єднують точки Б і р, Р і бр (рис. 2). Далі залишається з'єднати суцільною лінією точку Ч і точку б, так як точка Ч з'єднана з точкою бр штриховою лінією, а точка р вже «зайнята» (рис. 3). Таким чином на графі цього рисунку автоматично можна прочитати відповідь: Білокуров - рудий, Чорнов - білявий, Рудов - брюнет. За таким же принципом можна розв'язати наступну задачу.

Задача № 1.2

Для Вані, Колі і Михайлика спекли пироги: один з капустою, другий з пирогом, третій - з яблуками. Михайлик не любить пиріг з яблуками і не їсть з капустою. Іванко не любить пиріг з капустою. Хто який пиріг їсть?

Множину хлопчиків назвемо Х, а множину пирогів - П. Точки множини Х позначимо: Ваня - В, Коля - К, а Михайлик - М, точки множини П позначимо: пиріг з капустою - к, пиріг з рисом - р, а пиріг з яблуками - я. Виходячи з умови, за логікою попередньої задачі розв'язком до цієї є граф, який виглядає таким чином. З нього робимо висновок, що: Коля їсть пиріг з капустою, Ваня - з яблуками, Михайлик - з рисом.



Наведені задачі можна успішно розв'язати і за допомогою таблиць. Такий спосіб чи його модифікації рекомендуються і розбираються в багатьох науково-популярних книгах і педагогічних посібниках. Можна, проте, вказати класи задач, в яких застосування графів, зображених точками і відрізками, виявляється більш зручним і виправданим. Використання в розв'язках методу таблиць типу турнірних таблиць чи їх узагальнень змушує важливу частину міркування проводити «усно». При цьому неодноразово приходиться повертатися до умови задачі, до проміжних результатів, багато чого пам'ятати і в потрібний момент користуватися отриманою інформацією. До такого типу задач відносяться задачі з трьома чи більшою кількістю множин розглянутих об'єктів.

Задача № 1.3

Три товариші - Іван, Дмитро і Степан - викладають різноманітні предмети (хімію, біологію і фізику) в школах Москви, Ленінграду і Києва. І відомо:

1. Іван працює не в Москві, а Дмитро не в Ленінграді;

2. Москвич викладає не фізику;

3. Той, хто працює в Ленінграді, викладає хімію;

4. Дмитро викладає не біологію.

Який предмет і в якому місті викладає кожен з товаришів?

Розв'язання. Виділяємо 3 множини: Множина імен, множина предметів і множина міст. Елемент кожної з множин на рис. 5 заданий своєю точкою (букви на малюнку - перші букви відповідних слів). Якщо дві різні множини характеризують ознаки різних людей, то з'єднуємо такі точки штриховою лінією. Якщо ж дві точки з різних множин відповідають признакам однієї людини, то такі точки будемо з'єднувати суцільними лініями. Істотно, що за умовою задачі для кожної точки будь-якої множини в кожній з інших множин знайдеться одна і тільки одна точка, що їй відповідає. Таким чином, граф на рис. 5 містить всі задані в умові елементи множин і відношень між ними. Задача на мові графів зводиться до знаходження трьох «суцільних» трикутників з вершинами в різних множинах.

Розглянемо граф на рис. 5. Напрошується штриховий відрізок ХД. Дійсно, Л відповідає Х і одночасно, Л не відповідає Д, тобто Х не може відповідати Д. І так, використовується такого роду задач операція на графі: якщо у трикутника з вершинами в трьох різних множинах одна сторона суцільна, друга - штрихова, то третя повинна бути штриховою. З умови задачі слідує правомірність ще однієї операції на графі: якщо якась точка з'єднана штриховими відрізками з двома точками в другій множині, то її потрібно з'єднати з третьою точкою цієї множини суцільним відрізком. Так проводиться суцільний відрізок ДФ. Далі проводиться штриховий відрізок ДМ (в трикутнику ДФМ сторона ДФ суцільна, а ФМ - штрихова), ДК суцільним (ДМ і ДЛ штрихові). Тепер з'єднаємо точки Ф і К суцільним відрізком. Якщо у трикутнику з вершинами в різних множинах дві сторони суцільні, то третя також буде суцільною. Знайдений перший «суцільний» трикутник ДФК. Так не повертаючись до тексту задачі, керуючись лише очевидними на графі, що описаний вище, ми знаходимо розв'язок (рис. 6).

Відмітимо послідовність, в якій проводились відрізки: ХД, ДФ, ДМ, ДК, ФК, МС, ИЛ, ХИ, БМ, БС. Вершини кожного з трьох отриманих «суцільних» трикутників визначають відповідь задачі: Іван викладає хімію в Ленінграді, Дмитро - фізику в Києві і Степан - біологію в Москві.

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

Задача № 1.4

Маша, Ліда, Женя і Катя вміють грати на різних інструментах (віолончелі, роялі, гітарі і скрипці), але кожна тільки на одному. Вони ж володіють різними іноземними мовами (англійським, французьким, німецьким і іспанським), але кожна тільки одним. Відомо:

1. Дівчина, яка грає на гітарі, говорить іспанською

2. Ліда не грає ні на скрипці, ні на віолончелі і не знає англійської

3. Маша не грає ні на скрипці, ні на віолончелі і не знає англійської

4. Дівчина, яка говорить німецькою, не грає на віолончелі

5. Женя знає французьку, але не грає на скрипці.

Хто на якому інструменті грає і яку іноземну мову знає?

Умові задачі відповідає граф, зображений на рис. 7. Позначення і принцип розв'язку тут такий же як і у задачі 3. Проведемо послідовно наступні суцільні відрізки: КС, ВЖ, ВФ, АК (рис. 8). Тим самим утворюється два суцільних трикутника ЖВФ і КСА. Проводимо ще суцільний відрізок РН. Тепер впевнюємось, що умови задачі не забезпечують однозначного вибору третьої точки для кожної з пар РН і ГИ. Можливі наступні варіанти «суцільних» трикутників: МГИ і ЛРН чи

ЛГИ і МРН. Таким чином, задача має два розв'язки.

Розв'язок задач за допомогою графів можна порівнювати з розв'язком задач методом рівнянь: після складання рівняння ми забуваємо на короткий час умову задачі. Ця особливість методу зберігається при розгляді і інших логічних задач, які передбачають аналіз декількох можливостей. Ось приклад:

Задача № 1.5

Чотири спортсменки Аня, Валя, Галя і Даша зайняли перші 4 місця в змаганнях по гімнастиці , при чому жодні дві з них не ділили між собою ці місця. На питання, яке місце зайняла кожна з них, троє з вболівальників виказали припущення:

1. Аня - ІІ місце, Даша - ІІІ місце

2. Аня - І місце, Валя - ІІ місце

3. Галя - ІІ місце, Даша - ІV місце

Виявилось, що кожен вболівальник один раз помилився, а інший раз вказав правильно. Яке місце зайняла кожна з спортсменок?

Розв'язок.

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

Припустимо, наприклад, що Валя зайняла ІІ місце, тоді невірним має бути припущення: «Аня - ІІ місце», «Аня - І місце», «Галя - ІІ місце». Відрізки, що відповідають помилковому припущенню, будемо перекреслювати (рис. 10). У такому випадку Даша займе ІІІ і ІV місця, що за умовою задачі неможливо. Отже, припущення, що Валя зайняла ІІ місце, невірне; вірним буде висловлення «Аня зайняла І місце» (рис. 11). Ну тоді перекреслюємо відрізки АІІ і ВІІ, залишаючи ДІІІ. Далі закреслюємо відрізок ДІV. Отже: Аня зайняла І місце, Даша - ІІІ, Галя - ІІ, Валя - ІV.

2.2 Елементи теорії графів у задачах

Задача № 2.1. Чорні і білі

На столі три однакових скриньки. В одній лежать дві білі кульки, у другій - дві чорні, третій - біла та чорна. На скриньках є написи: «ББ», «ЧЧ», «БЧ», але жоден напис не є правильним. Яку найменшу кількість кульок треба взяти, щоб дізнатися, в якій скриньці лежать які кульки?

Розв'язання. На рис. 12 зображено простір станів (відрізки показують можливі розміщення кульок у скриньках). Ясно, що в скриньці з написом БЧ знаходяться кульки одного кольору. Тому потрібно вийняти одну кульку з тієї урни. Можливі 2 варіанти: а) виймуть білу; б) виймуть чорну.

Розглянемо кожний випадок окремо:

а) Якщо зі скриньки з написом БЧ дістали білу кульку, то в ній знаходяться білі кульки. Отже у скриньці з написом ЧЧ не можуть знаходитись дві білі кульки. Таким чином, там знаходяться чорна і біла кульки. Тоді очевидно, що у скриньці з написом ББ - дві чорних кульки (рис. 13 а). Випадок б) розглядається аналогічно (рис. 13.б). Відповідь: треба взяти 1 кульку зі скриньками з написом БЧ.

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

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



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

Задача № 2.2 Про знайомства

У кімнаті 5 чоловік. Доведіть, що принаймні двоє з них мають однакове число знайомих серед даних п'яти. Знайомство - «симетричне» відношення, тобто якщо Вася знайомий з Іваном, то й Іван знайомий з Васею.

Поставимо у відповідність кожній людині, що знаходиться в кімнаті, вершину графа. А ребра відображатимуть знайомства. Для розв'язання задачі досить довести, що принаймні з двох вершин у графі вийде одне й те саме число ребер. Число знайомих у будь-кого з присутніх може бути 0,1,2,3,4. Однак, якщо є людина з нульовим числом знайомств, то немає людини з числом знайомств рівним чотирьом, і навпаки (рис. 15). Тому розглянемо 2 випадки:

1) У кімнаті є людина з чотирма знайомими (отже, в кімнаті немає людини, яка немає знайомих серед даних п'яти (рис. 15а).)

2) У кімнаті є людина, яка не має знайомих серед даних п'яти (рис. 15б).

У першому випадку кожен з присутніх у кімнаті може мати число знайомств рівне 1,2,3 або 4, оскільки присутніх п'ять. Отже принаймні двоє мають однакове число знайомих. Що й треба було довести.

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

Задача № 2.3 Про парні числа

Один цар видав указ: «У державі повинно бути непарне число міст, а з кожного міста має виходити непарне число доріг» (кожна дорога з'єднує 2 міста). Днями й ночами працювали архітектори над планом будівництва, але нічого у них не виходило. З'ясувати чи можна виконати наказ царя. Відповідь обгрунтувати.

Вказівка. Корисно спершу розв'язати задачу з невеликим числом міст і доріг. Наприклад, спробувати побудувати граф для п'яти міст і трьох доріг, що виходять з кожного міста. Отримаємо граф, степінь кожної вершини якого дорівнює 3. Отже, загальне число ребер такого графа ? . Це неможливо.

Розв'язання. Розглянемо загальний випадок. Припустимо, що указ вдалося виконати. Поставимо у відповідність кожному місту вершину графа, а кожній дорозі - ребро графа. Очевидно, що в такому графі кількість вершин непарна і кожна вершина непарна, оскільки з кожного міста вийде непарне число доріг. Позначимо через k - кількість міст у державі, а степені вершин - n₁, n₂, n₃,…,n_k, де k та всі n_і - непарні числа. Загальне число ребер у графі (доріг у державі). N дорівнює сумі степенів усіх вершин графа, поділеної на два (кожна дорога підраховується двічі). Тому - n₁ + n₂ + n₃ + n_k = N*2. А це можливо лише в тому випадку, коли кількість непарних складових n_і - парна, тобто k (кількість міст) - парна. Отримали суперечність. Отже неможливо побудувати граф з непарною кількістю непарних вершин і неможливо побудувати державу, описану в царському указі. У ході розв'язання задачі № 2.3 були отримані твердження.

1. У графі сума степенів усіх його вершин число парне і дорівнює подвоєному числу ребер графа.

2. Число непарних вершин будь-якого графа - парне.

2.3 Задачі на використання дерев

Задача № 2.4. Хуліганські витівки.

Бешкетники Вася, Петрик розірвали стінгазету, причому Петрик рвав кожний шматок на 3 частини, а Вася - на 5. При спробі зібрати стінгазету знайшли 1998 обривків. З'ясуйте чи всі обривки зібрані?

Розв'язання. Нехай Петрик узяв шматок газети. Вийшло три нових шматки (загальне число шматків збільшилося на 2 - інваріант його дій) (рис. 16а). Дії Васі мають варіант - 4; бере шматок газети, а повертає 5 (рис. 16б). Беручи частину газети (неважливо, хто починає), і Вася, і Петрик збільшують число її шматків на парну кількість, тому унаслідок усіх дій може вийти лише непарне число частин газети. Отже газета була зібрана неповністю.



Задача № 2.5. Про кількість тризначних чисел.

Складіть множину тризначних чисел, які можна скласти за допомогою цифр 5 і 2. Скільки таких чисел?

Розв'язання. Будь-яке розташування цифр 5 і 2 в тризначному числі підраховується за допомогою схеми (дерева)(рис. 17), де перший ярус - це розряд сотень, другий - десятків і третій - одиниць.

Відповідь: 222,225,252,255,522,525,552,555. Таких чисел 8.

Задача № 2.5. Задача про шлях.

У туристичному бюро складають маршрути подорожей для автотуристів, яку повинні виїхати з пункту S, відвідати пункти A, B, C, D не більше одного разу кожен, і знову повернутися до пункту S. Пункти і шосейні дороги, що сполучають їх між собою, представлені схемою на рис.18. Числа на рисунку вказують відстань між населеними пунктами по цих дорогах. Допоможіть скласти найекономічніший (найкоротший) шлях для бюро маршрут подорожей.

Розв'язання. Зверніть увагу, що кожні дві вершини графа шосейних доріг сполучені між собою ребром (рис. 18). Це - повний граф.

Починаючи з вершини S, послідовно «розшаровуємо» граф шляхів у дерево (рис. 19). Розставимо вздовж його ребер відстані між населеними пунктами, в кінці кожного маршруту запишемо суму цих відстаней по маршруту. З отриманих 24 маршрутів найкоротшими є SBACDS та SDCABS.

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

Задача № 2.6. Про кодування алфавіту.

Побудуйте дерево, за допомогою якого можна кодувати алфавіт з 16 літер.

Розв'язання. Розіб'ємо алфавіт на дві рівні частини. Одній групі (з номерами 1- 8) поставимо у відповідність 0, інший (з номерами 9 - 16) - 1. З кожною з груп зробимо так само. Процес продовжується доти, поки не отримаємо одного елементу групу (рис. 20). За допомогою отриманого чотириярусного дерева, пересуваючись знизу вгору (або навпаки), можна отримати код будь-якого з 16 символів.

Задача № 2.7. Про розбір арифметичного виразу.

Побудувати дерево розбору арифметичного виразу: .

Розв'язання. Арифметичні операції розташовується згідно з пріоритетом. Пріоритети операції такі: 1) для виразів без дужок найвищий пріоритет мають операції множення, ділення - дії другого ступеня, складання та віднімання мають нижчий пріоритет; 2) для виразів з дужками найвищий пріоритет мають вирази в дужках, далі пріоритети розташовуються як в 1). Арифметичні операції з однаковими пріоритетом графі розташовуються на одному ярусі (рис. 21).

дерево граф логічний

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

Література

Березина Л. Ю. Графы помогают решать логические задачи -- Математика в школе, 1972 - №2 с. 62-68

Єлісєєва О., Петров В., Графи працюють на нас - Математика в школі - 2005 - №5 с. 47-51.

Оре О. «Графы и их применения» -- М.: УРСС, 1963. -- 175 с.

Уилсон Р. « Введение в теорию графов » М., Мир, 1977

Харари Ф. «Теория графов» -- М.: УРСС, 2003. -- 300 с.

Размещено на Allbest.ru