Елементи теорії графів та математичне програмування. Шляхи та цикли

Навчальне видання

Ююкін Микола Олексійович

ЛР №. Підписано до друку

Уч. Вид. арк., .

Воронезький державний технічний університет

394026 Воронеж, просп. 14

ДОВІДНИК МАГНІТНОГО ДИСКУ

Кафедра вищої математикита фізико-математичного моделювання

Н.А. Ююкін

ДИСКРЕТНА МАТЕМАТИКА Частина 1. Елементи теорії графів

Навчальний посібник

Н.А. Ююкін

ДИСКРЕТНА МАТЕМАТИКА Частина 1. Елементи теорії графів

Навчальний посібник

Воронеж 2004

ВСТУП

Цей посібник може бути використаний у курсі “Дискретна математика” студентами ВДТУ, які навчаються за спеціальностями:

090102 - Комп'ютерна безпека;

090105 - Комплексне забезпечення інформаційної безпеки автоматизованих систем;

090106 - Інформаційна безпекателекомунікаційних систем.

Дисципліна “Дискретна математика” забезпечує набуття знань та умінь відповідно до державного, загальноосвітнього стандарту, і при цьому сприяє отриманню фундаментальної освіти, формуванню світогляду та розвитку логічного мислення

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

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

в орграфах; аналіз графа ланцюга Маркова; алгоритми пошуку найкоротших шляхів у графах; задача пошуку гамільтонова циклу

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

Метою курсу є формування у студентів теоретичних знань, практичних умінь і навичок у галузі моделювання процесів та явищ у природознавстві та техні-

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

Досягнення цієї мети служать такі:

вивчити максимально широке коло понять теорії графів;

отримати навички вирішення навчальних та практичних завдань;

опанувати методи оптимізації;

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

Дисципліна “Дискретна математика” належить до прикладних математичних дисциплін. Вона грунтується на знаннях, набутих студентами щодо дисциплін “Алгебра” і “ Математична логіката теорія алгоритмів”. Знання та навички, отримані щодо дисципліни “Дискретна математика” використовуються щодо загальнопрофесійнихта спеціальних дисциплін.

1. ОСНОВНІ ПОНЯТТЯ ТЕОРІЇ ГРАФІВ.

1.1. Завдання теорії графів.

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

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

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

Виникало питання: чи можна вийшовши з дому, повернутися назад, проходячи по кожному мосту рівно один раз?

Друге завдання. Завдання про три будинки та три колодязі. Є три будинки та три колодязі.

Потрібно провести від кожного будинку до кожної криниці стежку так, щоб стежки не перетиналися. Завдання було

вирішена Понтрягіним і незалежно від нього Куратовським у

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

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

1.2. Основні визначення.

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

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

Ственни геометричні властивостіребер (довжина, кривизна), а також взаємне розташуваннявершин на площині.

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

Кажуть, що ребро (u,v) з'єднує вершини iv, а дуга (u,v) починається у вершині і закінчується у вершині, при цьому називається початком, а – кінцем цієї дуги.

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

Граф, без петель та кратних ребер, називається простим . Простий граф називається повним, якщо для будь-якої пари його вершин існує ребро (дуга), що їх з'єднує. Повний граф, що має n вершин позначається через Kn. Наприклад, це графи

Граф, що складається з однієї ізольованої вершини (K 1 ), називається тривіальним.

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

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

1.3. Ступінь вершин графа.

Ступенем (валентністю) (позначення d (v) або deg (v)) вершини простого графа G називається число ребер або дуг інцидентних даної вершині. При підрахунку валентності вершин псевдографа слід враховувати кожну петлю двічі.

Якщо ступеня всіх вершин н-графа рівніk, то граф називається регулярним (однорідним)ступеня k. Якщо ступінь вершини дорівнює0, то вона є ізольованою. Якщо ступінь вершини дорівнює1, то вершина називається кінцевою (висячою, тупиковою).

Для орграфа число дуг, що виходять з вершини v нази-

ється напівступенем результату				(v), а вхідних-напівстепі-

нью заходу d			(v), При цьому справедливе співвідношення d(v) =

	(v) +	(v).

Теорема Ейлера: Сума ступенів вершин графа дорівнює

подвоєної кількості ребер, тобто.

d (vi)



			(v)

Де n – число вершин; m – число

ребер (дуг). Дане твердження доводиться тим, що з підрахунку суми ступенів вершин кожне ребро враховується двічі - одного кінця ребра й у другого.

1.4. Ізоморфізм графів.

Граф називається позначеним (або перенумерованим), якщо його вершини відрізняються один від одного якими-

мітками (номерами). Граф вважається повністю заданим у строгому значенні, якщо нумерація його вершин та ребер фіксована. При цьому графи G1 і G2 називаються рівними (позначення G1 = G2), якщо їх безліч вершин і ребер збігаються. Два графи або псевдографи G 1 = (V 1 ,E 1 ) і G 2 = (V 2 ,E 2 ) називають-

	ізоморфними (позначення G	якщо існують

	взаємно однозначне відображення: 1)	: V 1V 2
: E 1 E 2 такі, що для будь-яких двох вершин, v у графі
	справедливе співвідношення ((u, v)) ((u), (v)).

	Два простих графа (без петель та кратних ребер) G 1		та G 2

виявляються ізоморфними, якщо існують взаємно одно-

значне відображення

: V 1V 2

Таке що

(u, v) ((u), (v)).

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

Рефлексивність -

G 1,

причому бієкція

є тотожною функцією.

Симетричність.

з бієкцією

Транзитивність.

G 1G 2

бієкцією

1, а

з бієкцією

то G G

з бієкцією

2 (1) .

ВОЛОДИМИРСЬКИЙ ДЕРЖАВНИЙ ПЕДАГОГІЧНИЙ УНІВЕРСИТЕТ

РЕФЕРАТ

«ТЕОРІЯ ГРАФІВ»

Виконала:

Зудіна Т.В.

Володимир 2001

1. Введення

2. Історія виникнення теорії графів

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

4. Основні теореми теорії графів

5. Завдання застосування теорії графів

6. Застосування теорії графів у шкільному курсіматематики

7. Додаток теорії графів у різних областяхнауки та техніки

8. Останні досягненнятеорії графів

§1. ІСТОРІЯ ВИНИКНЕННЯ ТЕОРІЇ ГРАФІВ.

Родоначальником теорії графів прийнято вважати математику Леонарда Ейлера (1707-1783). Історію виникнення цієї теорії можна простежити з листування великого вченого. Ось переклад латинського тексту, який узятий з листа Ейлера до італійського математика та інженера Маріноні, відправленого з Петербурга 13 березня 1736 [див. стор 41-42]:

"Колись мені було запропоновано завдання про острів, розташований у місті Кенігсберзі і оточений річкою, через яку перекинуто сім мостів. Запитується, чи може хтось безперервно обійти їх, проходячи тільки одного разу через кожен міст. І тут же мені було повідомлено, що ніхто ще досі не міг це зробити, але ніхто й не довів, що це неможливо… Питання це, хоч і банальне, здалося мені, однак, вартим уваги тим, що для його вирішення недостатні ні геометрія, ні алгебра, ні комбінаторне мистецтво… Після довгих роздумів я знайшов легке правило, засноване на цілком переконливому доказі, за допомогою якого можна у всіх завданнях такого роду відразу ж визначити, чи може бути здійснений такий обхід через будь-яке число і як завгодно розташованих мостів або не може. Кенігсберзькі мости розташовані так, що їх можна представити на наступному малюнку[Рис.1] , на якому A позначає острів, а B , C іD – частини континенту, відокремлені друг від друга рукавами річки. Сім мостів позначені літерами a , b , c , d , e , f , g ".

(МАЛЮНОК 1.1)

З приводу виявленого ним способу вирішувати завдання подібного роду Ейлер писав [див. стор 102-104]:

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

Тож чи можна обійти Кенігсберзькі мости, проходячи лише один раз через кожен із цих мостів? Щоб знайти відповідь, продовжимо листа Ейлера до Мариноні:

"Питання полягає в тому, щоб визначити, чи можна обійти всі ці сім мостів, проходячи через кожен тільки один раз, чи не можна. Моє правило призводить до наступного рішенняцього питання. Насамперед, потрібно дивитися, скільки є ділянок, розділених водою, – таких, які не мають іншого переходу з одного на інший, окрім як через міст. У даному прикладітаких ділянок чотири – A , B , C , D . Далі потрібно розрізняти, чи є кількість мостів, які ведуть до цих окремих ділянок, парних чи непарних. Так, у нашому випадку до ділянки A ведуть п'ять мостів, а до інших – по три мости, тобто число мостів, що ведуть до окремих ділянок, непарне, а цього вже достатньо для вирішення завдання. Коли це визначено, застосовуємо таке правило: якби кількість мостів, які ведуть до кожного окремій ділянці, було парним, то тоді обхід, про який йде мова, був би можливим, і в той же час можна було б почати цей обхід з будь-якої ділянки. Якщо ж із цих чисел два були б непарні, бо тільки одне бути непарним не може, то і тоді міг би відбутися перехід, як це наказано, але тільки початок обходу неодмінно має бути взято від однієї з тих ділянок, до яких веде не парне числомостів. Якби, нарешті, було більше двох ділянок, до яких веде непарна кількість мостів, то тоді такий рух взагалі неможливий… якщо можна було привести тут інші, більш серйозні завдання, цей метод міг би принести ще більшу користь і їм не слід було б нехтувати. .

Обгрунтування вищенаведеного правила можна знайти у листі Л. Ейлера до свого друга Елер від 3 квітня того ж року. Ми перекажемо нижче уривок із цього листа.

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

Історія з мостами міста Кенігсберг має сучасне продовження. Відкриємо, наприклад, шкільний підручник з математики за редакцією Н.Я. Віленкіна для шостого класу. У ньому на сторінці 98 у рубриці розвитку уважності та кмітливості ми знайдемо завдання, що має безпосереднє відношення до тієї, яку колись вирішував Ейлер.

Завдання № 569. На озері є сім островів, які з'єднані між собою так, як показано на малюнку 1.2. На який острів повинен доставити мандрівників катер, щоб вони могли пройти по кожному мосту і лише один раз? Чому не можна доставити мандрівників на острів A ?

(МАЛУНОК 1.2)

Рішення.Оскільки це завдання подібне до завдання про Кенігсберзьких мостах, то при її вирішенні ми також скористаємося правилом Ейлера. В результаті отримаємо наступну відповідь: катер повинен доставити мандрівників на острів Eабо Fщоб вони змогли пройти по кожному мосту один раз. З того ж правила Ейлера випливає неможливість необхідного обходу, якщо він розпочнеться з острова A .

На закінчення зазначимо, що завдання про Кенігсберзькі мости і подібні до неї завдання разом із сукупністю методів їх дослідження становлять дуже важливе значення. практичному відношенніРозділ математики, званий теорією графів. Перша робота про графи належала Л. Ейлер і з'явилася в 1736 році. Надалі над графами працювали Кеніг (1774–1833), Гамільтон (1805–1865), із сучасних математиків – К. Берж, О. Оре, А. Зиков.

§2. ОСНОВНІ ТЕОРЕМИ ТЕОРІЇ ГРАФІВ

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

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

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

(МАЛУНОК 2.1)

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

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

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

Позначення: O " - Граф з вершинами, що не має ребер (рис. 2.2).

(МАЛУНОК 2.2)

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

Позначення: U " – граф, що складається з nвершин і ребер, що з'єднують різні пари цих вершин. Такий граф можна уявити як n-кутник, в якому проведено всі діагоналі (рис. 2.3).

(МАЛУНОК 2.3)

Визначення 2.05. ступенем вершининазивається число ребер, яким належить вершина.

Позначення: p (A) – ступінь вершини A . Наприклад, малюнку 2.1: p (A)=2, p (B)=2, p (C)=2, p (D)=1, p (E)=1.

Визначення 2.06.Граф, ступеня всіх kвершин якого однакові, називається однорідним графом ступеня k .

На малюнку 2.4 та 2.5 зображені однорідні графи другого та третього ступеня.

(МАЛУНОК 2.4 та 2.5)

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

На малюнку 2.6 зображено вихідний граф G , що складається з чотирьох вершин та трьох відрізків, а на малюнку 2.7 – доповнення даного графа – граф G " .

(МАЛУНОК 2.6 та 2.7)

Ми бачимо, що малюнку 2.5 ребра ACі BDперетинаються в точці, яка не є вершиною графа. Але трапляються випадки, коли цей граф необхідно подати на площині у такому вигляді, щоб його ребра перетиналися лише у вершинах (це питання буде розглянуто докладно далі, у параграфі 5).

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

Наприклад, малюнку 2.8 показаний плоский граф, ізоморфний (рівний) графу малюнку 2.5. Проте, зауважимо, що кожен граф є плоским, хоча зворотне твердження правильне, т. е. будь-який плоский граф можна у звичайному вигляді.

(МАЛУНОК 2.8)

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

Тема графів – це цікава, корисна та лякаюча тема. Теорія графів - "Жах студента". Алгоритми на графах - приголомшливий розум людей, які їх відкрили.

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

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

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

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

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

Напевно, ви читали підручники і бачили такий запис G(V,E) або щось схоже. Так ось, V — це якийсь один об'єкт із безлічі об'єктів. У нашому випадку безліч об'єктів — це міста, отже, V — це якесь певне місто. Так як об'єкти не обов'язково міста, а слово об'єкт може заплутати, то такий об'єкт із множини можна називати точкою, пунктом, якось ще, але найчастіше його називають вершиною графа і позначають буквою V.
У програмуванні це зазвичай стовпець або рядок двовимірного масиву, де масив називається або матрицею суміжності або матрицею інцендентності.

У літературі, в інтернеті і взагалі скрізь, де щось написано про графи, ви зустрічатимете такі поняття, як дуги та ребра. На цьому малюнку зображено ребра графа. Тобто. це три ребра Е1, Е2 та Е3.

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

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

Ви часто зустрічатимете поняття суміжності та інцендентності. На малюнку червоним кольором відмічені два ребра, які йдуть в одну точку. Такі ребра, як і вищеописані вершини, також називаються суміжними.

Багато чого не описано, але ця частина інформації може бути комусь допоможе.

МУНІЦИПАЛЬНЕ АВТОНОМНЕ ЗАГАЛЬНООСВІТНИЙ ЗАКЛАД СЕРЕДНЯ ЗАГАЛЬНООСВІТНЯ ШКОЛА № 2

Підготував

Легкокінець Владислав, учень 10А класу

Практичне застосуванняТеорії Графів

Керівник

Л.І. Носкова, учитель математики

ст.Брюховецька

2011 р.

1.Введение………………………………………………………………………….………….3

2.Історія виникнення теорії графів………………………………………….………..4

3.Основні визначення та теореми теорії графів……………………………….………6

4.Завдання, що вирішуються за допомогою графів……………………………..……………………..8

4.1 Знамениті завдання………………………………….………………………...8

4.2 Декілька цікавих завдань………………………………….……………..9

5. Застосування графів у різних галузях життя людей……………………………...11

6.Рішення задач……………………………………………………………………………...12

7. Висновок………………….…………………………………………………………….13

8. Список літератури………….……………………………………………………………14

9.Додаток…………………………………………………………………….…………15

Вступ

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

Рішення багатьох життєвих завданьвимагає довгих обчислень, інколи ж і ці обчислення не приносять успіху. У цьому полягає проблема дослідження. Виникає питання: чи не можна для їх вирішення знайти просте, раціональне, коротке та витончене рішення. Чи спрощується вирішення завдань, якщо використовувати графи? Це визначило тему мого дослідження: «Практичне застосування теорії графів»

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

Гіпотеза дослідження.Метод графів дуже важливий і широко застосовується у різних галузях науки та життєдіяльності людини.

Завдання дослідження:

1.Вивчити літературу та ресурси мережі Інтернет з цієї проблеми.

2. Перевірити ефективність методу графів під час вирішення практичних завдань.

3. Зробити висновок.

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

У роботі використовуються наступні методи: спостереження, пошук, добір, аналіз.

Історія виникнення теорії графів

Родоначальником теорії графів прийнято вважати математику Леонарда Ейлера (1707-1783). Історію виникнення цієї теорії можна простежити з листування великого вченого. Ось переклад латинського тексту, взятого з листа Ейлера до італійського математика та інженера Мариноні, відправленого з Петербурга 13 березня 1736 року.

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

[Додаток рис.1]Постає питання, чи може хтось безперервно обійти їх, проходячи тільки одного разу через кожен міст. І тут мені було повідомлено, що ніхто ще досі не міг це зробити, але ніхто і не довів, що це неможливо. Питання це, хоч і банальне, здалося мені, проте, вартим уваги тим, що для його вирішення недостатні ні геометрія, ні алгебра, ні комбінаторне мистецтво. Після довгих роздумів я знайшов легке правило, засноване на цілком переконливому доказі, за допомогою якого можна у всіх завданнях такого роду відразу визначити, чи може бути здійснений такий обхід через яке завгодно число і як завгодно розташованих мостів чи не може. Кенігсберзькі мости розташовані так, що їх можна представити на наступному малюнку [Додаток рис.2], де A позначає острів, а B ,C іD – частини континенту, відокремлені друг від друга рукавами річки

З приводу виявленого ним способу вирішувати завдання подібного роду Ейлер писав:

"Питання полягає в тому, щоб визначити, чи можна обійти всі ці сім мостів, проходячи через кожен лише один раз, чи не можна. Моє правило призводить до наступного вирішення цього питання. Насамперед, потрібно дивитися, скільки є ділянок, розділених водою, – таких , у яких немає іншого переходу з одного на інший, крім як через міст.У цьому прикладі таких ділянок чотири - A, B, C, D. Далі потрібно розрізняти, чи є число мостів, які ведуть до цих окремих ділянок, парних або непарних. Так, у нашому випадку до ділянки A ведуть п'ять мостів, а до решти – по три мости, тобто число мостів, що ведуть до окремих ділянок, непарне, а цього вже достатньо для вирішення задачі. Якби число мостів, що ведуть до кожної окремої ділянки, було парним, то тоді обхід, про який йдеться, був би можливий, і в той же час можна було б почати цей обхід з будь-якої ділянки. би непарні, бо тільки одне бути н четним не може, то й тоді міг би відбутися перехід, як це наказано, але тільки початок обходу неодмінно має бути взято від однієї з двох ділянок, до яких веде непарне число мостів. Якби, нарешті, було більше двох ділянок, до яких веде непарна кількість мостів, то тоді такий рух взагалі неможливий… якщо можна було привести тут інші, більш серйозні завдання, цей метод міг би принести ще більшу користь і їм не слід було б нехтувати. .

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

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

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

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

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

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

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

Позначення: O "- граф з вершинами, що не має ребер

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

Позначення: U " – граф, що складається з n вершин і ребер, що з'єднують різні пари цих вершин. Такий граф можна подати як n-кутник, в якому проведені всі діагоналі

Визначення 5.Ступінню вершини називається число ребер, яким належить вершина.

Визначення 6.Граф, ступеня всіх k вершин якого однакові, називається однорідним графом ступеня .

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

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

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

Поняття плоского графа та грані графа застосовується при вирішенні завдань на "правильне" розфарбовування різних карт.

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

Визначення 11.Цикломназивається шлях, у якому збігаються початкова і кінцева точка.

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

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

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

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

Визначення 16.Деревомназивається зв'язковий граф, що не містить циклів.

Тривимірною моделлю графа-дерева служить, наприклад, справжнє дерево з його хитромудро розгалуженою кроною; річка та її притоки також утворюють дерево, але вже пласке – на поверхні землі.

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

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

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

Завдання розв'язувані за допомогою графів

Відомі завдання

Завдання комівояжера

Завдання комівояжера є одним із знаменитих завдань теорії комбінаторики. Вона була поставлена в 1934 році, і про неї обламували зуби найкращі математики.

Постановка завдання така.
Комівояжер (бродячий торговець) повинен вийти з першого міста, відвідати по разу у невідомому порядку міста 2,1,3..n і повернутися до першого міста. Відстань між містами відома. У якому порядку слід обходити міста, щоб замкнутий шлях (тур) комівояжера був найкоротшим?

Метод вирішення завдання комівояжера

Жадібний алгоритм "Йди в найближче (до якого ще не входило) місто".
"Жадібним" цей алгоритм названий тому, що на останніх кроках доводиться жорстоко розплачуватися за жадібність.
Розглянемо для прикладу мережу на малюнку [Додаток рис.3], що становить вузький ромб. Нехай комівояжер стартує з міста 1. Алгоритм “йди в найближче місто” виведе його до міста 2, потім 3, потім 4; на останньому кроці доведеться платити за жадібність, повертаючись довгою діагоналі ромба. В результаті вийде не найкоротший, а найдовший тур.

Завдання про Кенігсберзькі мости.

Завдання формулюється в такий спосіб.
Місто Кенігсберг розташоване на берегах річки Прегель та двох островах. Різні частини міста були з'єднані сімома мостами. У неділю городяни здійснювали прогулянки містом. Питання: чи можна здійснити прогулянку таким чином, щоб, вийшовши з дому, повернутися назад, пройшовши точно один раз по кожному мосту.
Мости через річку Прегель розташовані як на малюнку[Додаток Рис.1].

Розглянемо граф, який відповідає схемі мостів [Додаток рис.2].

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

Декілька цікавих завдань

1. "Маршрути".

Завдання 1

Як ви пам'ятаєте, мисливець за мертвими душамиЧичиков побував у відомих поміщиків одного разу в кожного. Він відвідував їх у такому порядку: Манилова, Коробочку, Ноздрьова, Собакевича, Плюшкіна, Тентетникова, генерала Бетрищева, Півня, Констанжолго, полковника Кошкарьова. Знайдено схему, на якій Чичиков накидав взаємне розташування маєтків і путівців, що з'єднують їх. Встановіть, який маєток комусь належить, якщо жодної з доріг Чичиків не проїжджав більше одного разу [Додаток рис.4].

Рішення:

За схемою доріг видно, що подорож Чичиков почав з маєтку Е, а закінчив маєтком О. Зауважуємо, що в маєтки В і С ведуть лише дві дороги, тому цими дорогами Чичиков повинен був проїхати. Зазначимо їх жирною лінією. Визначено ділянки маршруту, що проходять через А: АС та АВ. Дорогами АЕ, АК та АМ Чичиков не їздив. Перекреслимо їх. Зазначимо жирною лінією ЕD; перекреслимо DK. Перекреслимо МО та МН; відзначимо жирною лінією MF; перекреслимо FO; відзначимо жирною лінією FH, НК та КО. Знайдемо єдино можливий за даної умови маршрут. І отримуємо: маєток Е – належить Манілову, D – Коробочці, С – Ноздрьову, А – Собакевичу, В – Плюшкіну, М – Тентетникову, F – Бетрищеву, Н – Півню, К – Констанжолго, Про – Кошкареву [Додаток рис.5].

Завдання 2

На малюнку зображено схему місцевості [Додаток рис.6].

Пересуватися можна лише у напрямку стрілок. У кожному пункті можна бути не більше одного разу. Скільки способами можна потрапити з пункту 1 до пункту 9? Який маршрут найкоротший і який найдовший.

Рішення:

Послідовно "розшаровуємо" схему в дерево, починаючи з вершини 1 [Додаток рис.7]. Отримаємо дерево. Число можливих способіввлучення з 1 до 9 дорівнює числу "висячих" вершин дерева (їх 14). Очевидно, найкоротший шлях-1-5-9; найдовший - 1-2-3-6-5-7-8-9.

2 "Групи, знайомства"

Завдання 1

Учасники музичного фестивалю обмінялися конвертами з адресами. Доведіть, що:

а) всього було передано парне число конвертів;

б) число учасників, які обмінялися конвертами непарне число разів, парно.

Рішення: Нехай учасники фестивалю А1, А2, А3. . . , А n – вершини графа, а ребра з'єднують пари вершин, що зображають хлопців, які обмінялися конвертами [Додаток рис.8]

Рішення:

а) ступінь кожної вершини А i показує кількість конвертів, які передав учасник А i своїм знайомим. Загальне числопереданих конвертів N дорівнює сумі ступенів усіх вершин графа N = степ. А 1+степ. А 2 + +. . . + Степ. А n –1 + степ. А n, N = 2p, де p - Число ребер графа, тобто. N – парне. Отже, було передано парне число конвертів;

б) рівності N = степ. А 1+степ. А 2 + +. . . + Степ. А n –1 + степ. А n сума непарних доданків має бути парною, а це може бути тільки в тому випадку, якщо число непарних доданків парне. І це означає, що кількість учасників, обмінялися конвертами непарне число раз, парне.

Завдання 2

Якось Андрій, Борис, Володя, Даша та Галя домовилися ввечері піти у кіно. Вибір кінотеатру та сеансу вони вирішили узгодити телефоном. Було також вирішено, що якщо з кимось зателефонувати не вдасться, то похід у кіно скасовується. Увечері біля кінотеатру зібралися не всі, тож відвідування кіно зірвалося. Наступного дня почали з'ясовувати, хто комусь дзвонив. Виявилося, що Андрій дзвонив Борису та Володі, Володя дзвонив Борису та Даші, Борис дзвонив Андрію та Даші, Даша дзвонила Андрію та Володі, а Галя дзвонила Андрію, Володі та Борису. Хто не зумів зателефонувати і тому не прийшов на зустріч?

Рішення:

Намалюємо п'ять точок та позначимо їх літерами А, Б, В, Г, Д. Це перші літери імен. З'єднаємо ті точки, які відповідають іменам хлопців, що зізвонилися.

[Додаток рис.9]

З малюнка видно, що кожен із хлопців – Андрій, Борис та Володя – зателефонували з усіма іншими. Тому ці хлопці й дійшли кінотеатру. А Галя та Даша не зуміли зателефонувати між собою (точки Г і Д не з'єднані відрізком) і тому відповідно до домовленості в кіно не прийшли.

Застосування графів у різних сферах життя людей

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

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

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

Молекулярні графи та дерева: [Додаток рис.10]а, б - мультиграфи соотв. етилену та формальдегіду; в-мовляв. ізомерів пентану (дерева 4, 5 ізоморфні дереву 2).

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

Білкові мережі

Білкові мережі - групи фізично взаємодіючих білків, які функціонують у клітині спільно та скоординовано, контролюючи взаємопов'язані процеси, що відбуваються в організмі [Додаток рис. 11].

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

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

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

Приклад генеалогічного дерева моєї родини [Додаток рис.12].

Ще один приклад. На малюнку показано біблійне генеалогічне дерево [Додаток рис.13].

Розв'язання задач

1.Транспортне завдання. Нехай у місті Краснодарі знаходиться база з сировиною, яку потрібно розвести по містах Кримськ, Темрюк, Слов'янськ-на-Кубані та Тимашевську одним заїздом, витративши при цьому якнайменше часу та палива і повернувшись назад до Краснодара.

Рішення:

Для початку складемо граф усіх можливих шляхівпроїзду [Додаток рис.14]з огляду на реальні дороги між даними населеними пунктами та відстань між ними. Для вирішення цього завдання нам потрібно буде скласти ще один граф, деревоподібний [Додаток рис.15].

Для зручності рішення позначаємо міста цифрами: Краснодар – 1, Кримськ – 2, Темрюк – 3, Слов'янськ – 4, Тимашевськ – 5.

У результаті вийшло 24 рішення, але нам потрібні лише найкоротші шляхи. З усіх рішень задовольняють лише два, це 350 км.

Подібно до цього можна і, я думаю, потрібно розраховувати реальні перевезення з одного населеного пункту до інших.

Логічне завдання на переливання.У відрі 8 л води і є дві каструлі ємністю 5 і 3 л. потрібно відлити в п'ятилітрову каструлю 4 л води та залишити у відрі 4 л, тобто розлити воду порівну у відро та велику каструлю.

Рішення:

Ситуацію у кожен момент можна описати трьома числами [Додаток рис.16].

В результаті отримуємо два рішення: одне в 7 ходів, інше в 8 ходів.

Висновок

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

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

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

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

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

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

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

Література

Берж До.Теорія графів та її застосування. -M.: ІІЛ, 1962.

Кемені Дж., Снелл Дж., Томпсон Дж.Введення у кінцеву математику. -M.: ІІЛ, 1963.

Оре О.Графи та їх застосування. -M.: Світ, 1965.

Харарі Ф.Теорія графів. -M.: Світ, 1973.

Зиков А.А.Теорія кінцевих графів. -Новосибірськ: Наука, 1969.

Березіна Л.Ю.Графи та їх застосування. -M.: Просвітництво, 1979. -144 с.

"Соросівський освітній журнал" №11 1996 (ст. "Плоскі графи");

Гарднер М. "Математичні дозвілля", М. "Світ", 1972 (глава 35);

Олехник С. Н., Нестеренко Ю. В., Потапов М. К. "Старовинні цікаві завдання", М. "Наука", 1988 (частина 2, розділ 8; додаток 4);

додаток

Рис. 6

Рис. 7

Рис. 8

ридання

додаток

Рис. 14

ридання

додаток

Основні поняття теорії графів.

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

Історія виникнення теорії графів.

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

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

Д.Кеніг, запропонував називати такі схеми "графами" та систематично вивчати їх властивості.

У абсолютно різних дисциплінахдоводиться використати аналогічні теореми; так, поняття "матриці інциденцій", запроваджене Кірхгофом для вивчення електричних ланцюгів, було залучено А. Пуанкаре до топології при створенні його "analysis situs"; поняття "точки зчленування", з давніх-давен відоме в соціології, згодом з'явилося в електроніці; всі приклади такого роду перерахувати неможливо. Щоб можна було застосовувати теорію графів у таких різноманітних областях, вона повинна бути в вищого ступеняабстрактної та формалізованої.

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

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

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

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

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

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

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

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

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

Завдання про кенігсберзькі мости

Батьком теорії графів (так само як і топології) є Ейлер (1707-1782), який вирішив в 1736 широко відоме на той час завдання, що називалася проблемою кенігсберзьких мостів.

У місті Кенігсберзі було два острови, з'єднані сімома мостами з берегами річки Преголя і один з одним так, як показано на малюнку.

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

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

Вклад Ейлера у вирішення цього завдання полягає в тому, що він довів неможливість такого маршруту.

Малюнок 1. Парк у місті Кенігсберзі, 1736 р.

Малюнок 2. Граф до завдання про кенігсберзькі мости

Для доказу, що завдання немає рішення, Ейлер позначив кожну частину суші точкою (вершиною), кожен міст - лінією (ребром), що з'єднує відповідні точки.

Вийшов «граф». Цей граф показаний малюнку 2., де точки відзначені тими самими літерами, як і частини суші.

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

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

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

Електричні ланцюги

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

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

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

Малюнок 3. Мережа N, відповідний їй граф G.

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

Хімічні ізомери

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

Він прагнув перерахувати ізомери граничних (насичених) вуглеводнів З n Н 2 n + 2 з цим числом n атомів вуглецю; малюнок 4.

Малюнок 4.

У соціальній психології.

У 1936 р. психолог Курт Лев ін висловив припущення, що «життєвий простір» індивідуума можна уявити за допомогою планарної картки 1).

На такій карті області представляють різні типидіяльності людини, наприклад, те, що він робить на роботі, вдома, або його хобі.

Малюнок 5. Карта та відповідний їй граф.

Наголосимо, що К.Лев ін фактично мав справу з графами, як це видно із малюнка 5.

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

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

Теоретично організацій

Графи можуть бути представлені не тільки у суворій класичній формі. Так життєвий цикл компанії І. Адізеса представлений наступною формою.

Малюнок 6. Життєвий циклкомпанії

Функціональна організаційна структура побудована за принципом розподілу функцій всередині організації та створення наскрізних підструктур з управління функціями.

Виробничі підрозділи

Рис. Функціональна організаційна структура

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

Такою теорією стала "Теорія графів".

Основні поняття теорії графів

Почнемо з визначення, однозначного визначення теорія графів немає, нижче представлені три визначення, але є інші.

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

Теорія графів- Розділ математики, особливість якого - геометричний підхід до вивчення об'єктів

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