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

 

Міністерство освіти і науки, молоді та спорту України

Сумський державний  педагогічний університет імені  А.С. Макаренка

 

 

Кафедра математики

 

Мандій  Яна Анатоліївна

 

 

ДИПЛОМНА  РОБОТА

ГРАФИ ТА ЇХ ЗАСТОСУВАННЯ

 

Напрям  підготовки 0402 Фізико-математичні науки

Спеціальність 7.04020101 Математика*

Освітньо-кваліфікаційний  рівень «Спеціаліст»

 

 

 

 

 

Науковий керівник – 

доктор фізико-математичних

наук, професор

Лиман Федір  Миколайович

 

 

 

 

Суми – 2012

 

Зміст

ВСТУП 4

РОЗДІЛ 1. ЗАГАЛЬНІ ВІДОМОСТІ ПРО ТЕОРІЮ ГРАФІВ 8

1.1. Що таке граф? 8

1.1.1. Задача про кенігсберзькі мости 9

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

1.2. Основні  способи задання графів 19

1.2.1. Задання  графа за допомогою матриці  інцидентності та списку ребер 19

1.2.2. Задання  графа за допомогою матриці  суміжності 22

1.3. Ізоморфізм  графів 24

1.4. Планарність  графів 28

1.4.1. Застосування  теореми Ейлера до деяких завдань 31

1.4.2. Критерії  планарності 34

1.5. Одна задача  про плоскі графи 38

1.6. Ейлерові  графи 41

1.7. Маршрути  та зв′язність у графах 46

1.8. Дерева  та ліси 53

РОЗДІЛ 2. ОРІЄНТОВАНІ  ГРАФИ ТА РОЗФАРБУВАННЯ ГРАФІВ 57

2.1. Орієнтовані  графи 57

2.1.1. Модель  орграфа 57

2.1.2. Маршрути  в орграфах 60

2.1.3. Турніри 63

2.2. Розфарбування  графів 65

2.2.1. Хроматичне  число графа 65

2.2.2.  Гіпотеза  чотирьох фарб та теорема про  п’ять фарб для 67

планарних графів 67

РОЗДІЛ 3. ЗАСТОСУВАННЯ ТЕОРІЇ ГРАФІВ В ОКРЕМИХ ГАЛУЗЯХ  НАУКИ 71

3.1. Фізика 71

3.2. Хімія 77

3. 3. Біологія  і психологія 80

3.4. Інформатика 81

3.4.1. Програмування 82

3.4.2. Графи  як об’єкти обробки інформації 83

3.5. Математика 88

РОЗДІЛ 4. ГРАФИ  В ШКІЛЬНОМУ КУРСІ МАТЕМАТИКИ 97

4.1. Аналіз  навчальних програм з теми  дослідження 97

4.1.1. Програма  спеціального курсу «Прикладна  математика для учнів 8-11 класів  з поглибленим вивченням математики» 97

4.1.2. факультативна  програма з математики «Економіка  в задачах математики» 98

4.1.3. Програма  розвитку творчого мислення  учнів  (Шахи, інтелектуальні ігри. Основи  математичної логіки. Інтегрований  курс навчання.) 98

4.2. Факультативне  заняття з теорії графів для  учнів  11  класу на тему: «Граф.  Розв’язування задач за допомогою  графа» 99

ВИСНОВКИ 106

СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ 108

ДОДАТКИ 111

 

 

ВСТУП

 

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

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

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

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

Отже, практична цінність теорії графів безперечна.

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

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

Об’єктом  дослідження  є теорія графів.

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

Методи: теоретичний аналіз навчальної і науково-методичної літератури з даної теми.

Завдання:

1. Аналіз навчальної, науково-методичної та періодичної  літератури з теми дослідження;
2. Дослідження основних означень та теорем теорії графів.
3. З᾿ясування області застосування теорії графів.

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

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

В математиці  теорія графів розглядається як одна із віток топології; безпосереднє відношення має також  до алгебри і до теорії графів.

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

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

Дослідженням теорії графів займалися багато науковців сучасності, серед них: кандидат фізико-математичних наук, професор Р.М. Трохимчук, доктор фізико-математичних наук, професор Сущанський В.І., кандидат фізико-математичних наук,  доцент  Шевченко В.П., кандидат фізико-математичних наук Зиков А. А., кандидат фізико-математичних наук Берж К., кандидат фізико-математичних наук Оре О. та інші.

 

 

 

РОЗДІЛ 1. ЗАГАЛЬНІ ВІДОМОСТІ ПРО ТЕОРІЮ ГРАФІВ

 

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

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

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

 

1. Що таке граф?

 

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

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

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

Задача 1.1.

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

 що кожен знав тільки  двох запрошених.

 Розв′язання:

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

                                                  Рис.1.1.          

  

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

На рис. 2 показаний граф з чотирма вершинами та шістьма  ребрами, а 

 на рис. 3 зображено  граф з п′ятьма вершинами та  двома ребрами.

Рис.2

 

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

1. Задача про кенігсберзькі мости

 

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

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

Батьком теорії графів (так  само як і топології) є Ейлер (1707-1782рр.), який в 1736 році розв’язав досить відому в ті часи задачу, яка називалась «проблемою кенігсберзьких мостів». В  місті Кенігсберг було два острови, з’єднаних сімома містками з берегами річки Преголя і один з одним  таким чином, як показано на рис. 1.1. [28, c.13-14].

Рис. 1.1.

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

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

Для доведення того, що дана задача не має розв’язку, Ейлер позначив кожну частину суходолу точкою (вершиною), а кожен міст – лінією (ребром), яка з’єднує відповідні точки. Отримали «граф».  Цей граф показаний на рис.1.2, де точки  позначені тими ж буквами, що і частини суходолу на рис.1.1.

Рис. 1.2.

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

Відштовхуючись від цього  частинного випадку, Ейлер узагальнив постановку задачі і знайшов критерій існування обходу (спеціального маршруту) у даному графі, а саме граф повинен  бути зв’язним і кожна його вершина  повинна бути інцидентною парній кількості ребер. Граф, показаний  на рис.1.2, зв’язний, але не кожна  його вершина інцидентна парній кількості ребер [29, c. 16].