3
МІНІСТЕРСТВО НАУКИ І ОСВІТИ УКРАЇНИ
МАЛА АКАДЕМІЯ НАУК УКРАЇНИ
ЖИТОМИРСЬКЕ ТЕРИТОРІАЛЬНЕ ОБЄДНАННЯ
ВІДДІЛЕННЯ: МАТЕМАТИКИ
СЕКЦІЯ: ПРИКЛАДНА МАТЕМАТИКА
БАЗОВА ДИСЦИПЛІНА: МАТЕМАТИКА
РОЗВЯЗУВАННЯ ЗАДАЧ ЗА ДОПОМОГОЮ ГРАФІВ
2009 р.
Зміст
Вступ
Перша робота по теорії графів, що належить відомому швейцарському математику Л. Ейлеру, зявилася в 1736 р. Спочатку теорія графів здавалась досить незначним розділом математики, тому, що вона мала справу в основному з математичними розвагами і головоломками. Проте подальший розвиток математики і особливо її напрямків дав сильний поштовх до розвитку теорії графів. Вже в XIX сторіччі графи використовувалися при побудові схем електричних ланцюгів і молекулярних схем. З іншого боку, ця теорія широко застосовується в різноманітних практичних питаннях: при встановленні різного виду відповідностей, при вирішенні транспортних задач, задач про потоки в мережі нафтопроводів... Теорія графів тепер застосовується і в таких областях, як економіка, психологія і біологія. Математичні розваги і головоломки також залишаються частиною теорії графів, особливо якщо віднести до них знамениту проблему чотирьох фарб, що інтригує математиків і до цього дня.
У своїй роботові я розглядаю деякі прості питання відносно загальної теорії графів; я вибрав їх так, щоб дати деяке уявлення, з одного боку, про характер досліджень, які можна проводити за допомогою графів, і, з іншого боку, - про деякі конкретні завдання, які можна розвязувати такими методами.
Актуальність моєї роботи полягає у тому, що на даний момент теорія графів все ширше застосовується в різноманітних сферах нашої життєдіяльності. Зокрема, у фізиці: для побудови схем для розвязання задач, за допомогою графів значно спрощується розвязання задач з електротехніки. Архітектори використовують графи для найбільш раціонального розміщення обєктів і прокладання доріг на плані забудови населеного пункту. Біологи використовують графи для розвязання задач з генетики. Навіть на математичних заняттях учні та студенти використовують графи для розвязання геометричних та задач, та задач практичного змісту.
Вивчаючи теорію графів, я поставив перед собою мету: навчитись застосовувати графи, та складати задачі, тематика яких є актуальною в нинішньому суспільстві.
Також в моїй роботі представлений обширний словник термінів з теорії графів.
Задача про призначення на посаду
Нехай є кілька різних вакантних посад і група людей, які бажають їх зайняти, причому кожен із претендентів достатньо кваліфікований для кількох, але не для всіх наявних посад.
Чи можна кожному з цих людей надати одну з тих посад, які йому підходять?
Ми можемо знову проілюструвати цю задачу за допомогою деякого графа, що в даному випадку виглядає особливо. Як уже сказано, є певна група людей, яку ми позначимо як М і деяка множина посад, Р. Будуємо граф, проводячи ребра(м,р), що зєднує кожну людину м з тими посадами р, які він може зайняти. На цьому графі не буде ребер, що зєднують між собою дві вершини М чи Р, тому такий граф має вигляд: додаток 1
Завжди знайти підходяще місце для кожного претендента ми не можемо: для цього необхідно, щоб посад було не менше ніж претендентів. Але цього недостатньо.
Нехай, наприклад, група претендентів складається з двох столярів і людини, яка може працювати і столяром і сантехніком, і для них є чотири посади: одне місце столяра і три місця сантехніка. Тоді, очевидно, один столяр залишиться без роботи, хоча в даному випадку місць більше ніж претендентів, і хоча серед претендентів є люди що можуть працювати на двох посадах.
Припустимо, що загальна кількість претендентів - N. Для виконання задачі повинна виконуватись наступна умова:
Яку б групу із k чоловік, k=1,2,...,N, ми не взяли, повинно бути принаймні k посад, кожну з яких може займати хоча б один із наших претендентів.
Наприклад, якщо один з людей є столяром, а другий - одночасно і столяром і сантехніка і якщо є два місця сантехніка, то наша умова виконується при k=2, але не виконується при k=1, тому вказані люди не можуть одночасно влаштуватися на роботу.
Виділену умову ми коротко назвемо умовою різноманітності.
Висновок: вищенаведена задача може використовуватись працівниками служби зайнятості для правильного розміщення працівників на посади.
Інші формулювання
Ця задача, про встановлення на графі деякої відповідності між його вершинами, може мати і багато інших формулювань.
Припустимо, наприклад, що у нас є група із k хлопців і k дівчат. Дехто з них уже знайомі між собою, і виникає питання: в якому випадку можна розбити цих молодих людей не пари для танців так, щоб всі хлопці танцювали зі знайомими дівчатами?
Можна також змінити цю задачу: в маленькому селі є однакова кількість дорослих хлопців і дівчат; звичаєм не допускається, щоб хлопець одружувався на близькій родичці - сестрі, названій сестрі або двоюрідній сестрі. За якої умови для хлопця знайдеться наречена з цього села? Знову ми можемо розвязати цю задачу за допомогою дводольного графа - в цьому випадку його вершини будуть зєднані ребрами лише тоді, коли відповідні люди не є родичами.
А ось іще один варіант цієї задачі. В нашій школі є кілька гуртків: C1,C2,…,CN. Кожен із цих гуртків повинен мати старосту.
Для того щоб виключити перевантаження учнів, була поставлена умова, щоб жоден учень не був старостою більш, ніж одного гуртка. За якої умови це можливо?
Зрозуміло, що це можливо не завжди; якщо кількість гуртків в порівняно невеликій школі дужу велика, то це неможливо.
Щоб розвязати цю задачу, ми знову звернемось до дводольного графа.
В цьому випадку одна множина вершин графа складатиметься із N гуртків,
А інша множина вершин P - це множина всіх учнів школи. Ми проводимо ребро від гуртка С1 до учня р в тому випадку, якщо р є членом С1. При цьому умова різноманітності перетворюється в наступне: кожна група із k гуртків (при k = 1, 2,..., N) повинна включати щонайменше k різних учнів. Згідно вище вказаному - це та умова за якої гуртки можуть мати різних старост.
Якщо кількість гуртків занадто велика, не завжди легко довести справедливість умови різноманітності. Тому поставимо питання: Чи можна вказати яке-небудь просте правило формування гуртків, що гарантує можливість вибору для них різних старост?
Це дійсно можливо. Для того щоб показати, що ми маємо на увазі, припустимо, що кожен гурток складається принаймні з пяти учнів. Тоді на відповідному графі із кожної вершини множини С буде виходити принаймні 5 ребер. Для групи із k гуртків буде не менше 5k ребер, що виходять із відповідних вершин С до вершин із Р (додаток 2, де k = 4).
Тепер, якщо нам буде потрібно, щоб кожен учень брав участь не більше, ніж в пяти гуртках, це означатиме, що ребра від k гуртків повинні йти принаймні до k вершин із Р, і, відповідно, умова різноманітності буде виконана.
Ці думки є повністю загальними, тож ми можемо сформулювати наступний результат.
Потрібно, щоб в кожному гуртку брало участь принаймні t учнів і щоб, окрім того, жоден учень не брав участь більше ніж в t гуртках. Тоді завжди можна знайти для цих гуртків різних старост.
Висновок: ця задача допоможе керівникам дитячих закладів при організації гурткової роботи.
Спортивні змагання
У всіх змаганнях доводиться стикатися з питанням про те, яким чином обєднувати в пари окремих учасників. Іноді завдання виявляється простим: наприклад, якщо після кожного туру всі переможені вибувають із гри, то з учасників, що залишилися, утворюються нові пари, причому можливо, що один з них виявиться вільним від гри.
Це завдання дещо складніше у разі "кругового турніру", подібного до звичних шахових турнірів. Тут кожен з учасників повинен грати з кожним іншим, і важливо заздалегідь приготувати турнірну таблицю.
Цю ситуацію знову зручно змалювати за допомогою графа. Припустимо, що є N гравців, так що кожен з них грає N - 1 ігор з рештою учасників. Кожна гра як і раніше представляється ребром (A, B), що сполучає двох гравців, дві вершини A і В графа. Вся сукупність ігор представиться таким повним графом, що має N вершин, на додатку 3 зображений такий граф для N=6.
B кожному турі гравці якось обєднуються в пари. припустимо поки, що N парне, і це можна зробити. На графі таке обєднання в пари відповідає вибору ЅN несуміжних ребер, поодинці для кожної з N вершин. Для наступного туру можна вибрати нову множину ЅN ребер і так далі до тих пір, поки всі ігри не будуть зіграні. На додатку 3 ребра помічені таким чином: ті, на яких стоїть число 1, відносяться до пар, що зустрічаються в першому турі, ті на яких стоїть цифра 2 - до пар, що зустрічаються в другому турі, і так далі.
При великій кількості гравців фактичне складання такої таблиці для всіх турів відразу стає досить трудомістким, якщо не вказаний який-небудь систематичний метод. Багато довідників по проведенню турнірів містять просторові таблиці. Обєднання гравців в пари для різних кількостей гравців (N=6, 8, 10, 12 і т.д.). При складанні таблиці досить припускати як і раніше, що кількість гравців N парна. Якщо вона виявиться непарною, то завжди можна додати фіктивного гравця F, домовившись, що той, хто повинен грати з F, в цьому турі вільний від гри.
Опишемо простий і цілком загальний метод побудови турнірної таблиці для парної кількості гравців N. Позначимо гравців числами 1, 2,..., N і запишемо ці числа в їх природному порядку в першому рядку квадратної таблиці. B наступному рядку цієї таблиці ми хочемо поставити номери суперників цих гравців в першому турі матчу. Аналогічно в третьому рядку ми випишемо номери суперників тих же гравців 1,2..., N в другому турі і т, д. до тих пір, поки всі гравці не зіграють один з одним. Ясно, що наша таблиця має бути такою, щоб всі можливі пари гравців зустрілися в ній в точності по одному разу.
Спосіб зробити це показаний в таблиці на додатку 4.
Щоб встановити суперника j-го гравця в k-м турі, досить поглянути на перетин j-го стовпця і (k + 1) - го рядка цієї таблиці.
Таблиця влаштована таким чином.
У першому рядку, як вже було сказано, перераховані гравці від 1 до N; ці ж числа ми поставили і в першому стовпці. Тепер на N - 1, що залишилися, місць кожного рядка ми ставимо числа від 2 до N в циклічному порядку по вибуванню. Перші ЅN рядків починаються з парних чисел 2,4..., N і виглядають так:
Решта рядків починається з непарних чисел 3,5..., N - 1 і мають вигляд
Відмітимо, що в цій таблиці відсутнє число 1; з іншого боку, оскільки ніхто не грає проти самого себе, те число, що стоїть зверху стовпця, ніколи не повинне в цьому стовпці повторюватися. Ми усунемо обидва недоліки, якщо замінимо всі числа, що стоять на головній діагоналі, одиницями, як показано на додатку 4. Тепер кожен гравець знайде під своїм номером номери гравців, з якими він грає в різних турах. Наприклад, гравець 4 грає з гравцем N - 1 в першому турі, з гравцем 2 в другому турі, з гравцем 1 в третьому турі, з гравцем 6 в четвертому турі і так далі і, нарешті, з гравцем N - 3 в (N - 1) - му турі.
Висновок: розвязавши цю задачу, я зрозумів, що тепер організаторам спортивних змагань буде набагато простіше працювати, звісно, якщо вони прочитають подібний матеріал.
Задача про сполучення міст
Я хочу зупинитися на задачі про засоби сполучення, поставивши її спочатку формі питання про проведення доріг. Є декілька міст А, B, С,..., які потрібно зєднати між собою мережею шосейних або залізних доріг. Для кожної пари міст A, B відома вартість с(А, B) будівництва сполучаючої їх дороги. Завдання полягає в тому, щоб побудувати найдешевшу з можливих мереж доріг. Замість того, щоб говорити про мережу залізниць, можна було б говорити про електричні лінії, або про водопроводи, або про нафтопроводи і тому подібне
B тому окремому випадку, коли є всього три міста A, B, C, досить побудувати одну із ліній АВС, АСВ, ВАС, причому, якщо ВС - найдорожча лінія, то саме її і треба виключити, побудувавши дорогу ВАС.
Розглянемо тепер загальний випадок. Граф найбільш дешевої сполучаючої мережі має бути деревом, оскільки якби він містив цикл, можна було б видалити одну з ланок цього циклу і міста все ще залишилися б сполученими. Отже, для сполучення n міст потрібно побудувати n - 1 доріг.
Ми покажемо, що мережу мінімальної вартості можна побудувати, користуючись наступним простим правилом економічності. Перш за все, сполучаємо два міста з найбільш дешевою сполучаючою ланкою S1. На кожному з наступних кроків додаємо найдешевшу з ланок S1 при приєднанні якого до вже побудованих ребер не утворюється ніякого циклу; якщо є декілька ланок однієї і тієї ж вартості, вибираємо будь-яке з них.
Кожне дерево Т, побудоване таким чином, що ми називатимемо економічним деревом. Його вартість дорівнює сумі вартостей окремих ланок:
с(Т) = с(S1) + с(S2) +... + с(Sn-1).
Нам треба довести, що жодне інше дерево В, що сполучає ті ж вершини, не може виявитись дешевше за економічне дерево Т. Нехай В - найдешевше дерево, що сполучає наші вершини, а Т - будь-яке економічне дерево. Припустимо, що ребра S1, S2... економічного дерева Т занумеровані в тому порядку, в якому вони приєднувалися при побудові Т. Якщо найдешевше дерево В не збігається з Т, то Т має щонайменше одне ребро,що не належить В. Нехай S1= (A, В) - перше таке ребро, і нехай Р(А, В) - ланцюг графа В, що сполучає вершини A і B (додаток 5).
3
Якщо ребро S1 додати до В, то граф В+S1, міститиме цикл С= S1+Р(А, В), а оскільки Т не має циклів, то цикл С повинен містити принаймні одне ребро, що не належить Т. Видаливши це ребро S1 ми отримаємо дерево
В=В+S1 - S1
з тією ж кількістю вершин, що і В, причому його вартість дорівнює
C(В) =c(В) +с(S1) - с(S1)
Оскільки В має найменшу можливу вартість, то
с(S1) ?с(S1)
Але S1; було ланкою найменшої вартості, при додаванні якого до S1, S2..., Sn-1 не виходить циклів.
Оскільки при додаванні ребра S1 до цих ребер ми теж не отримаємо ніякого циклу, то
с(S1) = с(S1)
і, отже, В теж має мінімальну вартість:
c(В) = c(В).
Таким чином, ми знайшли інше дерево В мінімальної вартості, що має з економічним деревом Т на одне спільним ребро більше, ніж В. Ми можемо повторювати цю операцію до тих пір, поки остаточно не отримаємо сполучаюче дерево мінімальної вартості, яке співпадає з Т. Таким чином, Т, а також всі інші економічні дерева дійсно мають мінімальну вартість.
Висновок: такі задачі спростять роботу будь-якому планувальнику, допоможуть вберегти скарбницю певної держави від надлишкових витрат, знайшовши найдешевший варіант сполучення міст комунікаціями.
Знову спортивні змагання
Розвязуючи задачу про спортивні змагання, ми обєднували дві команди, скажімо А і C ребром АС у тому випадку, коли ці команди вже грали один з одним. Проте такий граф не дає відповіді на одне вельми суттєве питання: хто саме виграв гру?
Цей недолік легко може бути усунений. Якщо команда A виграла у C, домовимося ставити на ребрі АС стрілку, направлену від А до C. Припустимо, що нам відомі результати всіх вже зіграних ігор, і додамо до графа відповідні стрілки; хай при цьому вийде граф, зображений на додатку 6.
3
На цьому графові показано, що команда А виграла у C, команда F програла D, а В виграла всі ігри - з C, E, F і так далі
Граф G, на якому вказаний напрям кожного його ребра, називається орієнтованим графом. Такий граф, як ми бачили, може містити інформацію про результати змагання між командами або окремими гравцями. Навпаки, кожен орієнтований граф можна розглядати як геометричне представлення результатів деякого змагання. Додаток 7
3
Виникає питання: а що, якщо якась гра закінчилася внічию? Нічийні результати служать перешкодою при рахунку балів в будь-якому турнірі. Часто, наприклад при грі в теніс або в сквош, правила гри формулюються так, що нічийні результати взагалі неможливі. B інших іграх, таких, як гольф або футбол, гравці і команди, для того, щоб уникнути нічийного результату, грають додаткові тури.
Якщо ж нічийні результати неминучі, ми можемо відобразити їх на графі, залишаючи відповідні ребра неорієнтованими. При цьому ми отримаємо так званий змішаний граф, на якому є як орієнтовані, так і неорієнтовані ребра. Як ми побачимо далі, графи такого вигляду зустрічаються і в інших питаннях.
B якості прикладу змішаного графа розглянемо граф, зображений на додатку 7; на цьому графові вказані результати ігор чотирьох команд A, B, С і D; команда А виграла у В і С і зіграла внічию з D; В програла A, зіграла внічию із С і виграла у D; С програла A, виграла у D і зіграла внічию з B; D зіграла внічию з А і програла В і C.
Висновок: якщо на телебаченні дізнаються про такі задачі, то їм буде значно простіше зобразити результати певних ігор, а глядачам - зрозуміти хто виграв, хто програв, а хто зіграв внічию.
Односторонній рух
Карта будь-якої мережі доріг або вулиць дає нам дещо спеціальний, але наочний приклад графа. На сучасному плані міста мають бути показані не тільки відносне розташування вулиць і їх перетину, але також і те, на яких вулицях є двосторонній потік транспорту, а на яких односторонній рух, причому в останньому випадку: повинно бути вказано і напрям руху. При цьому знову виходить орієнтований або, частіше, змішаний граф, якщо односторонній рух встановлений не на всіх вулицях міста (додаток 8).
Втім, в попередньому випадку можна зробити граф орієнтованим за допомогою прийому, який часто використовується в теорії графів, полягає в заміні кожного неорієнтованого ребра двома орієнтованими ребрами, що сполучають ті ж самі вершини і що мають протилежні напрями.
При розгляді одностороннього руху в місті виникають питання, цікаві і для загальної теорії графів.
Припустимо, що в місті вирішено ввести нові правила руху, згідно з яким рух по кожній вулиці стає одностороннім. Це було б, звичайно, неприйнятно, якби виявилось, що при цьому не завжди можна проїхати з одного місця в інше.
Запитується, за якої умови вулиці міста можна орієнтувати так, щоб з будь-якого пункту можна було проїхати в будь-який інший, не порушуючи правил руху по вулицях.
Відповідне завдання на мові теорії графів формулюється таким чином: за якої умови ребра графа G можна орієнтувати так, щоб для будь-якої пари його вершин знайшлася та, що сполучає їх орієнтований ланцюг?
Ясно, що такий граф має бути звязним. Проте цього недостатньо.
Ребро S=(A, В) графа ми називатимемо звязуючим ребром, або перешийком, якщо воно є єдиним шляхом від A до B або назад.
Звязуюче ребро ділить всі вершини графа на дві множини: ті, в які можна прийти з A, не проходячи по ребру S, і ті, в які можна прийти з B, не проходячи по S. Граф в цьому випадку складається з двох частин G1 і G2i сполучених тільки ребром S (додаток 9).
На карті міста звязуюче ребро - єдина магістраль, що сполучає окремі частини міста. Воно може бути єдиним мостом через річку або єдиним залізничним тунелем. ясно, що якби на такій магістралі було встановлено односторонній рух, то з однієї частини міста в іншу не було б проїзду.
Раніше ми називали кінцевим ребpом таке ребро S - (А, В), один з кінців якого, наприклад A, не належить ніякому іншому ребру графа (додаток 10).
Таке ребро теж повинне розглядатися як звязуюче, оскільки, окрім S, немає шляху, який сполучає A з B.
Можна вважати, що граф G1 (додаток 9) наче "стягнутий" в одну вершину A. На плані міста кінцеве ребро відповідає глухому куту; на якому теж не можна встановити односторонній рух, не блокуючи цим вїзд в A або виїзді з A.
Якщо ребро S1= (А1, В1) Не є таким, що звязує, то знайдеться і інший шлях, що сполучає, А1 і В1 і що не проходить по S1 (додаток 11).
Тому таке ребро S1, називається циклічним ребром. Отже, на графі є ребра двох типів - циклічні і звязуючі.
Тепер ми можемо довести наступну теорему.
ТЕОРЕМА. ЯКЩО G - неорієнтований звязний граф, то завжди можна так орієнтувати циклічні ребра з G, залишивши звязуючі ребра неорієнтованими, щоб будь-яку пару вершин цього графа можна було зєднати орієнтованим ланцюгом.
Для плану міста це твердження можна сформулювати таким чином: якщо залишити двосторонній рух тільки на мостах (за умови, що даний міст є єдиним мостом через річку) і на глухих кутах, то на решті всіх вулиць можна встановити односторонній рух так, щоб транспорт забезпечував звязок всіх частин міста.
Ми можемо довести цю теорему; вказавши спосіб відповідного орієнтування графа. Почнемо з того, що виберемо в G довільне ребро S= (А,B). Якщо S - звязуюче ребро, воно залишиться двостороннім, і тоді можна буде перейти від В до А і назад уподовж S (додаток 12).
Якщо S - циклічне ребро, то воно входить в деякий цикл С і тоді на всіх ребрах циклу С можна встановити циклічну орієнтацію; ясно, що з будь-якої вершини G можна перейти до будь-якої іншої, прямуючи вказаним на ребрах напрямом (додаток 13).
Цей процес можна продовжити. Припустимо, що ми вже орієнтували деяку частину H даного графа так, що з будь-якої вершини графа H можна пройти в будь-яку іншу його вершину з дотриманням правил одностороннього руху. Оскільки граф G є звязним, то або N збігається з усім графом G, або знайдеться ребро S = (А, В), що "торкається" Н, тобто таке, що воно не належить H, але одна з його вершин, скажемо A, належить Н.
Якщо S - звязуюче ребро АВ, то, як ми вже умовилися, воно залишається двостороннім. Тоді для будь-якої вершини X графа H можна знайти орієнтований ланцюг R, що сполучає X з A, а значить (через ребро S), і з B. Назад, від вершини B через ребро S можна перейти до A, а потім - по орієнтованому ланцюгу Z - від А до X (додаток 14).
Приєднуючи S до H, ми отримаємо вже велику частину графа G, що має необхідну властивість.
Якщо ж ребро S = (А, B) є циклічним, воно належить деякому циклу С. Ми встановимо напрям на С від А до B і далі уподовж С до першої вершини D з С, що належить H (додаток 15)
Всі ці ребра ми приєднаємо до H. Нехай X - довільна вершина з Н, а Y - будь-яка вершина із С: можна знайти орієнтований ланцюг Р, що належить Н і що сполучає Х з A, а потім уподовж С пройти до вершини Y з С. Назад від Y можна пройти уздовж С до вершини D, а від неї - належним Н, орієнтованим ланцюгом Z - від D до X. Тому орієнтований граф, отриманий додаванням до Н вказаних ребер циклу С, також задовольняє необхідні умови: те, що від будь-якої з доданих вершин циклу С можна пройти до будь-якої іншої з цих вершин з дотриманням умов, повязаних з орієнтацією ребер, очевидно (додаток 15), продовжуючи цей процес, ми в кінці кінців орієнтуємо необхідним чином початковий граф G.
Встановлення на вулицях міста одностороннього руху дозволяє сильно збільшити швидкість руху транспорту; проте воно ставить справжні головоломки перед водієм, який хоче обїхати на машині незнайоме йому місто. Якщо на вулицях скрізь або частково встановлений односторонній рух, то завдання стає набагато складнішим, навіть якщо зроблено необхідне припущення про існування, принаймні одного орієнтованого ланцюга, що сполучає будь-яку пару вершин графа.
Загальна проблема така: яким способом можна рухатися по графові уздовж вказаних напрямів, щоб зрештою пройти по всіх його ребрах? Для цього, звичайно, треба мати хорошу память, а ще краще заздалегідь скласти нарис графа, утвореного мережею вулиць.
Ми відправляємося з деякої точки а0 по одній з вулиць, що виходять з неї. Проходячи перехрестя, ми позначаємо на малюнку, по якій вулиці ми сюди прийшли і на яку нову вулицю переходимо; для подальшого корисно відзначити також і інші вулиці, що виходять на це перехрестя, разом з їх напрямами. Через деякий час ми повернемося до одного з перехресть а1, на якому ми вже побували раніше (додаток 16).
Подивимося на план, складений нами заздалегідь, якщо ми вже обійшли всі вулиці міста, то наше завдання вирішене. B протилежному випадку знайдеться ще не пройдена вулиця (с, d). По припущенню, існує орієнтований ланцюг, сполучаючий а1 з с; ми підемо по ньому, а потім пройдемо вулицю (с, d) (зрозуміло, найзручніше починати з не пройдених раніше вулиць, що виходять з а1) Ясно, що, діючи і далі так само, ми врешті-решт обійдемо всі вулиці міста.
Висновок: якщо органи міського управління приймуть до уваги результат дослідження цієї задачі, то затори зникнуть з вулиць будь-якого міста.
Висновок
В моїй роботі описувались важливі методи, які можуть допомогти розвязати деякі життєві проблеми.
Вивчивши основи теорії графів, ознайомившись з розвязанням класичних задач, досліджено розвязання деяких задач за допомогою графів. Розглянуто, як можна використовувати задачі на практиці: прокладення комунікацій, розподіл посад між претендентами, складання турнірних таблиць, планування руху в містах...
Працюючи над роботою, я зрозумів, що дана тема є актуальною і перспективною в наш час.
Список використаної літератури
Барболин М.П. Головоломки и графы. Квант, 1975, №2
В.А. Носов. Комбинаторика и теория графов, МГТУ, 1999
Уилсон Р. Введение в теорию графов. М., Мир, 1977
Головина Л.И. Графы и их применения. Математика в школе, 1965,№ 3
Новиков Ф.А. Дискретная математика, 2001
Шедиви Я. Решение логических задач при помощи графов. - Математика в школе, 1967, № 6
Головина Л.И. і Яглом И.М., Индукция в геометрии, М., Физматгиз, 2000.
Словник термінів
Граф. Фігура, що складається з точок (вершин) і відрізків, що сполучають деякі з цих вершин. Сполучаючі відрізки можуть бути прямолінійними або криволінійними; вони називаються ребрами графа.
Дерево. Звязний граф, що не має циклів.
Многогранник. Тривимірне тіло, межа якого складається з плоских багатокутників.
Нульовий граф. Граф, що складається тільки з ізольованих вершин: граф, що не має ребер.
Ациклічний граф. Орієнтований граф, що не містить ніякого орієнтованого циклу.
Вершина графа. Або кінець якого-небудь ребра графа, або ізольована точка графа.
Гамільтонова лінія. Елементарний цикл, що проходить по всіх вершинах графа.
Грань багатокутного графа G. Частина площини, обмежена яким-небудь мінімальним циклом G або максимальним циклом C1 графа G; у останньому випадку це частина площини, що лежить поза С1; її називають також нескінченною гранню.
Степінь р(А) вершини A. Число ребер, що сходяться у вершині A. Для орієнтованого графа р(А) означає кількість ребер, що виходять, а р*(А) - кількість вхідних ребер у вершину A; в цьому випадку є два степені.
Ребро графа. Крива, що сполучає дві вершини графа і що не містить інших вершин.
Граф G*, подвійний багатокутному графові G. Багатокутний граф, кожна вершина якого відповідає певній грані графа G, а кожна грань - певній вершині графа G. Дві вершини графа G* сполучено ребром в тому і лише у тому випадку, коли відповідні грані графа G мають загальне ребро.
Дводольний граф. Граф, вершини якого можна розділити на дві непересічні множини так, що вершини однієї і тієї ж множини не сполучені між собою ребрами.
Додекаедр. Многогранник, обмежений 12 пятикутними гранями.
Доповнення G графа G. Граф G+ складається зі всіх ребер (і їх кінців), які необхідно додати до G для того, щоб вийшов повний граф.
Ізольована вершина. Вершина, з якої не виходитиме жодного ребра.
Плоский граф. Граф, якого можна накреслити на площині так, щоб його ребра перетиналися тільки в його вершинах.
Ізоморфні графи. Графи G1 і G2 ізоморфні, якщо між їх вершинами можна встановити таку взаємно однозначну відповідність, що пари вершин графа G1 в тому і лише в тому разі сполучені ребром, коли сполучені ребром відповідні пари вершин графа G2. У випадку орієнтованих графів ця відповідність повинна зберігати орієнтацію ребер.
Ікосаедр. Многогранник, обмежений 20 трикутними гранями.
Інцидентність ребра і вершини. Ребро називається інцидентним вершині, якщо вона є одним з його кінців.
Корінь дерева. Будь-яка вершина, яку ми вибираємо за початкову точку дерева.
Кратні ребра. Якщо дві вершини графа сполучено більш ніж одним ребром, то кожне таке ребро називається кратним.
Ліс. Граф. всі звязні компоненти якого є деревами (граф без циклів).
Максимальний цикл С1 многокутного графа G. Цикл, що оточує весь граф G.
Мінімальний цикл многокутного графа G. Цикл, утворений граничними ребрами одного з багатокутників, складових G.
Многокутний граф (многокутна мережа) - плоский граф. ребра якого утворюють безліч суміжних, не налягаючих один на одного многокутників.
Непарна вершина. Вершина, степінь якої непарний.
Зворотний граф G* для даного орієнтованого графа G. Граф G* виходить з G через зміну напрямів всіх його ребер.
Однорідний граф степеня r. Граф, степені всіх вершин якого однакові і рівні r
Октаедр. Многогранник, обмежений 8 трикутними гранями.
Орієнтований граф. Граф, на якому вказані напрями всіх його ребер.
Перешийок. Інший термін, для звязуючого ребра.
Петля. Ребро графа, обидва кінці якого збігаються.
Повний граф. Граф, будь-які дві вершини якого сполучено ребром. Повний граф, у якого n вершин, має
Ѕn(n - 1) ребер.
Правильний граф. Многокутний однорідний граф, такий, що подвійний до нього граф G* теж є однорідним.
Правильний многогранник. Многогранник, всі грані якого є рівними правильними многокутниками і в кожній вершині якого сходиться однакова кількість ребер.
Звязний граф. Граф, кожна вершина якого може бути сполучена деяким ланцюгом з будь-якою іншою його вершиною.
Звязуюче ребро. Ребро, видалення якого приводить до збільшення числа звязних компонентів графа.
Змішаний граф. Граф, на якому є як орієнтовані, так і неорієнтовані ребра.
Тетраедр. Многогранник, обмежений чотирма трикутними гранями.
Ланцюг. Лінія на графі, що не проходить ні по якому ребру більше одного разу.
Цикл. Замкнутий ланцюг.
Циклічне ребро. Ребро, що не є звязуючим.
Цикломатичне число графа G. Кількість ребер графа G мінус число його вершин плюс одиниця.
Парна вершина. Вершина, степінь якої парний.
Граф Ейлера. Граф, що містить ейлерову лінію.
Ейлерова Лінія. Ланцюг, що проходить по всіх ребрах графа в точності по одному разу.
Елементарний ланцюг. Ланцюг, що не проходить ні через одну зі своїх вершин більше одного разу.
Елементарний цикл. Цикл, що не проходить ні через одну зі своїх вершин більше одного разу.
| ! | Как писать курсовую работу Практические советы по написанию семестровых и курсовых работ. |
| ! | Схема написания курсовой Из каких частей состоит курсовик. С чего начать и как правильно закончить работу. |
| ! | Формулировка проблемы Описываем цель курсовой, что анализируем, разрабатываем, какого результата хотим добиться. |
| ! | План курсовой работы Нумерованным списком описывается порядок и структура будующей работы. |
| ! | Введение курсовой работы Что пишется в введении, какой объем вводной части? |
| ! | Задачи курсовой работы Правильно начинать любую работу с постановки задач, описания того что необходимо сделать. |
| ! | Источники информации Какими источниками следует пользоваться. Почему не стоит доверять бесплатно скачанным работа. |
| ! | Заключение курсовой работы Подведение итогов проведенных мероприятий, достигнута ли цель, решена ли проблема. |
| ! | Оригинальность текстов Каким образом можно повысить оригинальность текстов чтобы пройти проверку антиплагиатом. |
| ! | Оформление курсовика Требования и методические рекомендации по оформлению работы по ГОСТ. |
| → | Разновидности курсовых Какие курсовые бывают в чем их особенности и принципиальные отличия. |
| → | Отличие курсового проекта от работы Чем принципиально отличается по структуре и подходу разработка курсового проекта. |
| → | Типичные недостатки На что чаще всего обращают внимание преподаватели и какие ошибки допускают студенты. |
| → | Защита курсовой работы Как подготовиться к защите курсовой работы и как ее провести. |
| → | Доклад на защиту Как подготовить доклад чтобы он был не скучным, интересным и информативным для преподавателя. |
| → | Оценка курсовой работы Каким образом преподаватели оценивают качества подготовленного курсовика. |
| Курсовая работа | Деятельность Движения Харе Кришна в свете трансформационных процессов современности |
| Курсовая работа | Маркетинговая деятельность предприятия (на примере ООО СФ "Контакт Плюс") |
| Курсовая работа | Политический маркетинг |
| Курсовая работа | Создание и внедрение мембранного аппарата |
| Курсовая работа | Социальные услуги |
| Курсовая работа | Педагогические условия нравственного воспитания младших школьников |
| Курсовая работа | Деятельность социального педагога по решению проблемы злоупотребления алкоголем среди школьников |
| Курсовая работа | Карибский кризис |
| Курсовая работа | Сахарный диабет |
| Курсовая работа | Разработка оптимизированных систем аспирации процессов переработки и дробления руд в цехе среднего и мелкого дробления Стойленского ГОКа |