Дослідницька робота "Теорія графів. Застосування на практиці"

Демешина Тетяна 6 листопада 39 Відгуки відсутні

Про матеріал

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

Теорія графів. Застосування на практиціДослідницька робота. Роботу виконали: Сорокопуд Софія Рубана Дар’я Костриба Діана Філоненко Дар’я. Керівник: Демешина Т. А.

Номер слайду 2

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

Номер слайду 3

Об’єктом дослідження є процес використання теорії графів. Метою даної роботи є ознайомлення з історією виникнення графів, введення основних означень та показ практичної цінності теорії графів для розв’язування прикладних задач. Предметом дослідження є сукупність теоретичних, методичних і практичних аспектів понять теорії графів та їх практичне використання. Методи дослідження: 1. Експериментальний метод.2. Спостереження.3. Математичне моделювання. Рано чи пізно всяка правильна математична ідея знайде своє застосування в тій чи іншій справі(О. М. Крилов)Очікувані результати дослідження теорії графів — це рішення складних задач у різних сферах, шляхом моделювання реальних систем як абстрактних об'єктів (вершин і ребер), що дозволяє знаходити оптимальні маршрути, аналізувати зв'зки, класифікувати структури. 

Номер слайду 4

Теорія графів — розділ математики, що вивчає властивості графів. Наочно граф можна уявити як геометричну конфігурацію, яка складається з точок (вершини) сполучених лініями (ребрами). Точки - вершини графа. Лінії - ребра графа. Граф із 5 вершинами та 6 ребрами (розміщення учнів за партами)Графи привертають увагу своєю естетикою і магією. В теорії графів прихована маса витончених комбінаторних проблем, що варті уваги найдосвідченіших математиків. Ф. ХараріВершини Ребра

Номер слайду 5

Графи є істотним елементом математичних моделей в найрізноманітніших галузях науки і практики. Карта зоряного неба. Схеми авіаліній. Найдосконаліший мозок іржавіє без дії.   Шерлок Холмс

Номер слайду 6

Приклади графів. Мережі доріг України

Номер слайду 7

Генеалогічне дерево Рюриковичів. Тисячі шляхів ведуть до помилки, але лише один - до істини.  (Жан-Жак Руссо)Приклади графів

Номер слайду 8

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

Номер слайду 9

Степінь вершин графа. Математика — це не цифри, рівняння, обчислення чи алгоритми: це розуміння (З. Дайсон)

Номер слайду 10

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

Номер слайду 11

Якщо степінь всіх вершин парна, то можна обійти всі вершини графа без повторень, також можна обійти всі вершини, якщо на графі тільки 2 непарні вершини, якщо ж непарних вершин більше, то обійти всі вершини графа не вдасться. У перекладі на мову задачі "одним розчерком" це звучить так: якщо на малюнку всі точки парні, то такий малюнок можна намалювати однією лінією, не відриваючи олівця від паперу і не проводячи двічі по одній лінії; якщо на малюнку 2 непарні точки (якщо є одна непарна точка, то обов'язково є і друга), то такий малюнок також можна намалювати одним розчерком, причому слід починати з однієї непарної точки і закінчувати в інший непарній точці; якщо ж непарних точок більше двох, то намалювати такий малюнок одним розчерком не вдасться . Розв’язання задачі Ейлера. В кенігсбергзькому графі виявилося, що всі чотири "суші" мали непарну кількість мостів (3 або 5). А це означає, що проходження без повторів неможливе.

Номер слайду 12

Три сусідки посперечалися і викопали кожна по колодязю. Вирішили прокласти стежки до кожного колодязя, але таким чином, щоб не зустрічатися одна з одною. Чи можна зробити так, щоб стежки не перетиналися?Така задача має важливе практичне значення при побудові залізниць. Відповідь на цю задачу запропонував математик Куратовський у 1930 році. Задача про три колодязіГраф планарний тоді і тільки тоді, коли він не містить підграфів, гомеоморфних повному графу з п'яти вершин (K5) або графу «будинки і колодязі» (K3,3). Тобто в ньому немає включень (K5) або (K3,3). Теорема Понтрягина — Куратовского

Номер слайду 13

Задача про три колодязіЗгідно з теорією графів, ця ситуація описується повним двочастковим графом K3,3 (де 3 вершини — це будинки сусідок, а інші 3 вершини — колодязі). Щоб кожна з трьох сусідок мала власну стежку до кожного з трьох колодязів, потрібно прокласти 9 стежок. За теоремою Куратовського, граф K3,3 є непланарним. Це означає, що його неможливо накреслити на площині (папері або рівній ділянці землі) так, щоб його ребра (стежки) не перетиналися. Мінімальна кількість перетинів для такого графа на площині завжди дорівнює одному. Висновок: На звичайній рівній ділянці землі прокласти такі стежки без перетинів неможливо. Задача має розв'язок лише у випадку, якщо поверхня не є плоскою (наприклад, якщо прокласти одну стежку через міст або тунель, або якщо сусіди живуть на поверхні у формі тора (бублика).

Номер слайду 14

ЗАДАЧА «ПРО ЧОТИРИ ФАРБИ»Чи можна зафарбувати карту світу використовуючи лише 4 фарби так, щоб жодні дві сусідні країни не зафарбовувались одним кольором. Допускається зафарбовування одним кольором лише коли вони межують одна з одною лише однією точкою. У 1976 році Аппель і Хейкі опублікували рішення задачі про чотири фарби, яке базувалося на переборі варіантів за допомогою комп'ютера.

Номер слайду 15

ЗАДАЧА «ПРО ЧОТИРИ ФАРБИ»Припустимо, столиці країн є вершинами графа і мають колір, що відповідає кольору країни, як показано на рис. У цьому разі маємо граф, суміжні вершини якого будуть мати відмінний колір. До того ж кількість кольорів вершин має бути мінімальною, а граф отриманий на основі карти, буде планарним. Виходить, що будь-який планарний граф має хроматичне число, що не перевищує чотири. Чотири фарби буде достатньо, щоб розфарбувати вершини планарного графа у різні кольори. Хроматичне число графа ꭗ(G) – найменша кількість кольорів у які можна розфарбувати його вершини, щоб суміжні вершини, з’єднані одним ребром, були різного кольору. Дві вершини вважаються суміжними, якщо між ними існує ребро.

Номер слайду 16

3. Якщо у повного графа n вершин, то всього сполучень (ребер) - n(n-1)/2 2. Якщо у повного графа вершин n, то з кожної вершини виходить сполучень (ребер) n-1.1. У повного графа кожна вершина сполучена ребром з кожною вершиною, крім самої себе. Повний графзастосування в геометрії

Номер слайду 17

Повний графзастосування в геометрії: визначення кількості діагоналей в многокутнику. Пояснення через графи: Вершини та Ребра: Уявімо многокутник з n вершинами. Кожну вершину можна розглядати як вершину графа, а кожне ребро графа як відрізок, що з'єднує дві вершини. Повний Граф Kn: Якщо з'єднати всі можливі пари вершин многокутника, ми отримаємо Повний граф. Кількість ребер у повному графі з n вершинами становить. Сторони Многокутника: Серед цих ребер є n сторін самого многокутника. Діагоналі: Діагоналі — це всі ребра повного графа, які не є сторонами многокутника. Формула: отже, кількість діагоналей D дорівнює загальній кількості ребер у повному графі мінус кількість сторін:

Номер слайду 18

Задача комівояжера. Задача комівояжера (Traveling Salesman Problem, TSP) застосовується дляоптимізації маршрутів у логістиці, навігаторах ,плануванні доставок, роботі дронів (БПЛА), у мікрочипах.  Пошук найкоротших шляхів на графіКомівояжер (бродячий торговець) повинен вийти з першого міста, відвідати по одному разу в невідомому порядку міста 1, 2, 3, ..., n і повернутися в перше місто. Відстані між містами відомі. У якому порядку слід обходити міста, щоб замкнутий шлях (тур) комівояжера був найкоротшим?

Номер слайду 19

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

Номер слайду 20

Побудуємо можливі маршрути: гамільтонів граф. Всього маршрутів 6:1-2-3-4-11-2-4-3-11-3-2-4-11-3-4-2-11-4-2-3-11-4-3-2-1 Оскільки, маршрути попарно рівні за довжиною, то всього маршрутів:6 : 2=31-2-3-4-1=7+15+9+12=431-2-4-3-1=7+6+9+5=271-3-2-4-1=5+15+6+12=38

Номер слайду 21

Складання розкладу іспитів. Нехай учні здають іспити і обирають предмети за вибором. Треба скласти розклад іспитів так, щоб кількість днів була найменша і щоб не виникла колізія – два іспити в один день. Розв’язання: Нехай вершини графа – предмети, а фарби – дні іспита. Побудуємо граф, в якому вешинам поставимо у відповідність предмети. {5940675 A-B579-460 E-94 D1-54222 C63 F5 DA}АBCDEFГанна***Іван***Оксана***Дмитро***АBCDEF

Номер слайду 22

Граф є математичною моделлю найрізноманітних об’єктів, явищ і процесів, що досліджуються і використовуються в науці і практиці. Використання графів дозволяє наочно візуалізувати складні дані (діаграми, схеми, графіки), полегшуючи їх розуміння та аналіз у бізнесі, науці й освіті, що підвищує ефективність комунікації, сприяє швидкому прийняттю рішень та є основою для створення візуального контенту, від мистецтва до промислового дизайну, завдяки різним типам графіки (растрова, векторна, 3 D). Теорія графів — це універсальна мова опису світу. Вона: дає можливість знаходити найкоротші шляхи, оптимальні рішення, передбачати розвиток систем. Висновки

Номер слайду 23

Андерсон Д. А. Дискретна математика і комбінаторика. М.: Вильямс, 2003. – 960 с. Бондаренко М. Ф., Білоус Н. В., Руткас А. Г. Комп’ютерна дискретна математика: Підручник. - Харків, 2004. - 480 с. Вікіпедія Граф (математика) Кузьменко І. М. "Теорія графів" (КПІ ім. Ігоря Сікорського): Електронний посібник Попов В. М. Дидактика математики: проблеми і дослідження // 2004, Вип.21. Слепкань З.І. Методика навчання математики // К. Зодіак-ЕКО, 2000, 512 с. Джерела інформації

В прямому ефірі
Інтернет-конференція: ШІ та цифрові інструменти для організації навчання в умовах блекаутів