Дослідницька робота "Теорія графів. Застосування на практиці"
Про матеріал
Дослідницька робота "Теорія графів. Застосування на практиці". На даний момент теорія графів все ширше застосовується в різноманітних сферах нашої життєдіяльності. Зокрема, метод графів використовують в прикладній математиці, мистецтві, спорті, соціології, техніці, медицині, транспорті, екології, фінансах, кібернетиці, будівництві, біології, хімії, фізиці. Тому актуальність теми обумовлена популярністю графів і пов'язаних з ними методів досліджень.
Світ кривих значно різноманітніший і багатший, ніж світ точок, але тільки математики XX століття зуміли оволодіти його багатством.(Вінер Н.)Актуальність. Народившись при розв'язуванні головоломок і цікавих ігор, теорія графів стала нині простим, доступним і потужним засобом вирішення питань, що відносяться до широкого кола проблем. На даний момент теорія графів все ширше застосовується в різноманітних сферах нашої життєдіяльності. Зокрема, метод графів використовують в прикладній математиці, мистецтві, спорті, соціології, техніці, медицині, транспорті, екології, фінансах, кібернетиці, будівництві, біології, хімії, фізиці. Тому актуальність теми обумовлена популярністю графів і пов'язаних з ними методів досліджень.
Об’єктом дослідження є процес використання теорії графів. Метою даної роботи є ознайомлення з історією виникнення графів, введення основних означень та показ практичної цінності теорії графів для розв’язування прикладних задач. Предметом дослідження є сукупність теоретичних, методичних і практичних аспектів понять теорії графів та їх практичне використання. Методи дослідження: 1. Експериментальний метод.2. Спостереження.3. Математичне моделювання. Рано чи пізно всяка правильна математична ідея знайде своє застосування в тій чи іншій справі(О. М. Крилов)Очікувані результати дослідження теорії графів — це рішення складних задач у різних сферах, шляхом моделювання реальних систем як абстрактних об'єктів (вершин і ребер), що дозволяє знаходити оптимальні маршрути, аналізувати зв'зки, класифікувати структури.
Теорія графів — розділ математики, що вивчає властивості графів. Наочно граф можна уявити як геометричну конфігурацію, яка складається з точок (вершини) сполучених лініями (ребрами). Точки - вершини графа. Лінії - ребра графа. Граф із 5 вершинами та 6 ребрами (розміщення учнів за партами)Графи привертають увагу своєю естетикою і магією. В теорії графів прихована маса витончених комбінаторних проблем, що варті уваги найдосвідченіших математиків. Ф. ХараріВершини Ребра
Роком зародження теорії графів можна вважати 1736 рік, коли швейцарський математик Леонард Ейлер опублікував в Санкт-Петербурзькій академії наук роботу, присвячену семи мостам міста Кенігсберг (нинішній Калінінград). Місто розділене річкою Прегель на чотири частини, які з’єднувалися сімома мостами. Мости через річку Прегель розташовані як зображено на малюнку. Питання полягає в тому, чи можна, прогулюючись по мосту, пройти через кожен міст точно по одному разу і повернутися назад.
Якщо степінь всіх вершин парна, то можна обійти всі вершини графа без повторень, також можна обійти всі вершини, якщо на графі тільки 2 непарні вершини, якщо ж непарних вершин більше, то обійти всі вершини графа не вдасться. У перекладі на мову задачі "одним розчерком" це звучить так: якщо на малюнку всі точки парні, то такий малюнок можна намалювати однією лінією, не відриваючи олівця від паперу і не проводячи двічі по одній лінії; якщо на малюнку 2 непарні точки (якщо є одна непарна точка, то обов'язково є і друга), то такий малюнок також можна намалювати одним розчерком, причому слід починати з однієї непарної точки і закінчувати в інший непарній точці; якщо ж непарних точок більше двох, то намалювати такий малюнок одним розчерком не вдасться . Розв’язання задачі Ейлера. В кенігсбергзькому графі виявилося, що всі чотири "суші" мали непарну кількість мостів (3 або 5). А це означає, що проходження без повторів неможливе.
Три сусідки посперечалися і викопали кожна по колодязю. Вирішили прокласти стежки до кожного колодязя, але таким чином, щоб не зустрічатися одна з одною. Чи можна зробити так, щоб стежки не перетиналися?Така задача має важливе практичне значення при побудові залізниць. Відповідь на цю задачу запропонував математик Куратовський у 1930 році. Задача про три колодязіГраф планарний тоді і тільки тоді, коли він не містить підграфів, гомеоморфних повному графу з п'яти вершин (K5) або графу «будинки і колодязі» (K3,3). Тобто в ньому немає включень (K5) або (K3,3). Теорема Понтрягина — Куратовского
Задача про три колодязіЗгідно з теорією графів, ця ситуація описується повним двочастковим графом K3,3 (де 3 вершини — це будинки сусідок, а інші 3 вершини — колодязі). Щоб кожна з трьох сусідок мала власну стежку до кожного з трьох колодязів, потрібно прокласти 9 стежок. За теоремою Куратовського, граф K3,3 є непланарним. Це означає, що його неможливо накреслити на площині (папері або рівній ділянці землі) так, щоб його ребра (стежки) не перетиналися. Мінімальна кількість перетинів для такого графа на площині завжди дорівнює одному. Висновок: На звичайній рівній ділянці землі прокласти такі стежки без перетинів неможливо. Задача має розв'язок лише у випадку, якщо поверхня не є плоскою (наприклад, якщо прокласти одну стежку через міст або тунель, або якщо сусіди живуть на поверхні у формі тора (бублика).
ЗАДАЧА «ПРО ЧОТИРИ ФАРБИ»Чи можна зафарбувати карту світу використовуючи лише 4 фарби так, щоб жодні дві сусідні країни не зафарбовувались одним кольором. Допускається зафарбовування одним кольором лише коли вони межують одна з одною лише однією точкою. У 1976 році Аппель і Хейкі опублікували рішення задачі про чотири фарби, яке базувалося на переборі варіантів за допомогою комп'ютера.
ЗАДАЧА «ПРО ЧОТИРИ ФАРБИ»Припустимо, столиці країн є вершинами графа і мають колір, що відповідає кольору країни, як показано на рис. У цьому разі маємо граф, суміжні вершини якого будуть мати відмінний колір. До того ж кількість кольорів вершин має бути мінімальною, а граф отриманий на основі карти, буде планарним. Виходить, що будь-який планарний граф має хроматичне число, що не перевищує чотири. Чотири фарби буде достатньо, щоб розфарбувати вершини планарного графа у різні кольори. Хроматичне число графа ꭗ(G) – найменша кількість кольорів у які можна розфарбувати його вершини, щоб суміжні вершини, з’єднані одним ребром, були різного кольору. Дві вершини вважаються суміжними, якщо між ними існує ребро.
Повний графзастосування в геометрії: визначення кількості діагоналей в многокутнику. Пояснення через графи: Вершини та Ребра: Уявімо многокутник з n вершинами. Кожну вершину можна розглядати як вершину графа, а кожне ребро графа як відрізок, що з'єднує дві вершини. Повний Граф Kn: Якщо з'єднати всі можливі пари вершин многокутника, ми отримаємо Повний граф. Кількість ребер у повному графі з n вершинами становить. Сторони Многокутника: Серед цих ребер є n сторін самого многокутника. Діагоналі: Діагоналі — це всі ребра повного графа, які не є сторонами многокутника. Формула: отже, кількість діагоналей D дорівнює загальній кількості ребер у повному графі мінус кількість сторін:
Задача комівояжера. Задача комівояжера (Traveling Salesman Problem, TSP) застосовується дляоптимізації маршрутів у логістиці, навігаторах ,плануванні доставок, роботі дронів (БПЛА), у мікрочипах. Пошук найкоротших шляхів на графіКомівояжер (бродячий торговець) повинен вийти з першого міста, відвідати по одному разу в невідомому порядку міста 1, 2, 3, ..., n і повернутися в перше місто. Відстані між містами відомі. У якому порядку слід обходити міста, щоб замкнутий шлях (тур) комівояжера був найкоротшим?
Складання розкладу іспитів. Нехай учні здають іспити і обирають предмети за вибором. Треба скласти розклад іспитів так, щоб кількість днів була найменша і щоб не виникла колізія – два іспити в один день. Розв’язання: Нехай вершини графа – предмети, а фарби – дні іспита. Побудуємо граф, в якому вешинам поставимо у відповідність предмети. {5940675 A-B579-460 E-94 D1-54222 C63 F5 DA}АBCDEFГанна***Іван***Оксана***Дмитро***АBCDEF
Граф є математичною моделлю найрізноманітних об’єктів, явищ і процесів, що досліджуються і використовуються в науці і практиці. Використання графів дозволяє наочно візуалізувати складні дані (діаграми, схеми, графіки), полегшуючи їх розуміння та аналіз у бізнесі, науці й освіті, що підвищує ефективність комунікації, сприяє швидкому прийняттю рішень та є основою для створення візуального контенту, від мистецтва до промислового дизайну, завдяки різним типам графіки (растрова, векторна, 3 D). Теорія графів — це універсальна мова опису світу. Вона: дає можливість знаходити найкоротші шляхи, оптимальні рішення, передбачати розвиток систем. Висновки
Андерсон Д. А. Дискретна математика і комбінаторика. М.: Вильямс, 2003. – 960 с. Бондаренко М. Ф., Білоус Н. В., Руткас А. Г. Комп’ютерна дискретна математика: Підручник. - Харків, 2004. - 480 с. Вікіпедія Граф (математика) Кузьменко І. М. "Теорія графів" (КПІ ім. Ігоря Сікорського): Електронний посібник Попов В. М. Дидактика математики: проблеми і дослідження // 2004, Вип.21. Слепкань З.І. Методика навчання математики // К. Зодіак-ЕКО, 2000, 512 с. Джерела інформації