Embedded Files
Трішки історії
Трішки історії
Виникнення теорії графів — задача про кенігсберзькі мости
Теорія графів “відкривалася” незалежно багато разів.
Найперша згадка про теорію графів зустрічається в роботах Леонардо Ейлера, який у 1736 році розв'язав задачу про кенігсберзькі мости. М. Кенігсберг було розташоване на берегах річки Преголя, рукави якої ділили місто на чотири частини, в тому числі й два острови — Кнайпгоф і Ломзе, що поєднувалися сімома мостами. Задача полягала в пошуку маршруту проходження всіх чотирьох частин суші, який мав починатися на довільній з них, закінчуватися на ній же та по одному разу проходити кожен міст. Проте всі спроби знайти маршрут були невдалими. Щоб довести неможливість існування такого маршруту, Ейлер позначив кожну частину суші точкою (вершиною, або вузлом), а кожен міст — лінією (ребром), що з'єднує відповідні точки, і одержав “граф” . Твердження про неіснування маршруту рівносильно неможливості спеціальним чином обійти граф. Виходячи з цього конкретного випадку, Ейлер узагальнив постановку задачі та знайшов критерій існування обходу. Пізніше елементи теорії графів з’явилися в таких природничих науках, як географія, фізика, хімія, електротехніка. Взагалі, графи застосовні в усіх галузях, де є елементи й зв'язки між ними, тому теорія графів є актуальним прикладним розділом математики.
Розділ математики
Розділ математики
Теорія графів - це один із розділів математики, що дає змогу формалізувати взаємозв'язки між різноманітними видами інформації, організувати абстрактне їх представлення.
Даний розділ дозволяє ознайомлюватися з оптимізаційними методами розв'язування алгоритмічних задач, тобто з такими, які дають змогу знайти розв'язок задачі за найменшу кількість ітерацій. Це можливо виконати за рахунок відкидання на кожному проміжному кроці виконання алгоритму «неперспективних» варіантів, тобто таких, які у жодному разі не приведуть до шуканого результату.
Знаючи різні методи розв'язування задач і коректно використовуючи їх під час побудови алгоритмів, можна значно скоротити час виконання цих алгоритмів.
Чи користувалися раніше графами?
Пошук у мережі, де сама мережа схематично зображена - є графом.
Структурах даних представлена деревом, теж є різновидом графа.
А також це можуть бути такі прості і зрозумілі приклади: представлення шляхів між окремими населеними пунктами, фінансові взаємовідносини між різними банками (грошові позики або борги), аудиторії та предмети, які можуть у них викладатися, тощо.
Основні поняття
Основні поняття
Графом називається сукупність точок (вершин) і ліній (ребер), що їх з’єднують.
Можна також ще сказати, що графом називається сукупність точок і ліній, в якій кінці кожної лінії належать множині точок.
Якщо ребро з’єднує дві вершини, то кажуть, що воно інцидентне цим вершинам, а вершини, які з’єднані таким ребром, називаються суміжними.
Якщо кінці ребра належать одній вершині, то таке ребро називається петлею. На малюнку ребро а є петлею.
•Вершини, які не належать кінцям жодного з ребер у графі, називаються ізольованими. Прикладом ізольованої вершини на малюнку 8, а є вершина А.
•Граф, який складається лише з ізольованих вершин, називається нуль-графом (мал. б).
До речі, а чи може в графі існувати ребро без вершин?
Граф, у якому будь-яка пара вершин з’єднана ребрами, називається повним
Якщо всі вершини і ребра графа знаходяться в одній площині, то він називається плоским (а), у протилежному випадку - просторовим
Степенем вершини будемо називати число ребер, яким належить ця вершина. Або ще можна сказати, що степенем вершини називається кількість ребер, інцидентних даній вершині.
Позначається степінь вершини а як Р(а).
Наприклад, вершина А (мал. а) має степінь 3, а вершина В - степінь 1:
Р(А) = 3 Р(В) = 1.
Ще теорія
Ще теорія
Основні поняття теорії графів.pptx – копія.pptxЗавдання 1
Завдання 1
Зобразіть за допомогою графа договірні відносини між підприємствами А, Б, В, Г, Д, Е, якщо до розглянутого моменту:
підприємство А встановило договірні відносини з усіма іншими підприємствами;
Б встановило з Г і Д;
В встановило з усіма підприємствами, крім підприємства Е.
Скільки вершин і скільки ребер має отриманий граф?
6 вершин та 10 ребер
Завдання 2
Завдання 2
Серед семи країн встановлені економічні відносини, причому кожна країна має економічні договори з кожною іншою країною. Зобразіть у вигляді графа результат встановлених економічних відносин. Скільки ребер має отриманий граф?
Практична робота
Практична робота
Практична робота "Основні поняття теорії графів" у двох варіантах
Page updated
Google Sites
Report abuse