Історія інформатика

Теорiя Графів 

 Пітер Деннінг казав , що до  фундаментальних питань інформатики відноситься наступне питання: «Що може бути ефективно автоматизовано?»  Вивчення теорії алгоритмів сфокусовано на пошуку відповідей на фундаментальні питання про те, що можна обчислити і яка кількість ресурсів необхідно для цих обчислень. Для відповіді на перше питання в теорії обчислюваності розглядаються обчислювальні завдання, які вирішуються на різних теоретичних моделях обчислень. Друге питання присвячений теорії обчислювальної складності; в цій теорії аналізуються витрати часу і пам'яті різних алгоритмів при вирішенні безлічі обчислювальних задач.  Одні з найважливіших алгоритмів є алгоритми роботи з графами, до них відносяться - Пошук в глибину, Пошук в ширину, Алгоритм Дейкстри.

Що таке графи?

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

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

Щоб зрозуміти як працюють алгоритми над графами розглянемо одну з перших завдань яка і дала поштовх до розвитку теорії графів.
 З давніх-давен середи жителів Кенігсберга була поширена така загадка: як пройти по всіх міських мостах через річку , не проходячи за жодним з них двічі?Багато хто намагався вирішити це завдання як теоретично, так і практично, під час прогулянок. Втім, довести або спростувати можливість існування такого маршруту ніхто не міг.
 В 1736 завдання про семи мостах зацікавила видатного математика, Леонарда Ейлера, про що він написав у листі італійському математику і інженеру Джованні Джакобо Маринони  від 13 березня 1736 року. У цьому листі Ейлер призводить правило, користуючись яким, легко визначити, чи можна пройти по всіх мостах, не проходячи двічі по жодному з них. Відповідь на задачу була "не можна".

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

                                                    Пошук в ширину 

 Алгоритм можна розуміти як процес "підпалювання" графа: на нульовому кроці підпалюємо тільки вершину S. На кожному наступному кроці вогонь з кожної вже палаючої вершини перекидається на всіх її сусідів; тобто за одну ітерацію алгоритму відбувається розширення "кільця вогню" в ширину на одиницю.

Більш строго це можна представити таким чином. Створимо чергу queue, в яку будуть міститися палаючі вершини, а також заведемо булевский масив  visit [], в якому для кожної вершини будемо відзначати, горить вона вже чи ні .

Спочатку в чергу поміщається тільки вершина S,  visit [S] = true, а для всіх інших вершин  visit [] = false. Потім алгоритм являє собою цикл: поки черга не порожня, дістати з її голови одну вершину, переглянути всі ребра, що виходять з цієї вершини, і якщо якісь з переглянутих вершин ще не горять, то підпалити їх і помістити в кінець черги.

                                                Пошук в глубину

  Алгоритм переглядає кожне ребро один раз, і виконує для кожної вершини константне число дій. Позначаючи число вершин як N, а ребер - як R, отримуємо, що час роботи - O (N + R).

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

                                                    Алгоритм Дейкстри

  Дамо 1-й вершині мітку рівну 0, тому як ця вершина - джерело. Іншим вершин дамо мітки рівні нескінченності.

 

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

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

Розглянемо алгоритм на прикладі графа вище беремо мінімальну вершину тут я взяв вершину 2 ,оскільки з неї немає шляху помічаемо їі як відвіданну,беремо наступну вершину з мінімальною вагою тут це буде точка 5 з вагою 10 ,з неї є ще   шлях до вершини 4 з вагою 30 ,

а також  шлях до вершини 3 з вагою 10 .Наступним нашим кроком ми відвідаємо вершину 3 и запишемо туди  вагу 10. Далі відвідаемо вершину 4 з вагою 30.На цьому наш обход завершаетьс

                                                                Дерева

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

 Ліс - впорядкована множина впорядкованих дерев.

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