Топ-100
Back

ⓘ Граф, структура от данни. В компютърните науки, граф е абстрактна структура от данни, имаща за цел да имплементира терминът граф от математиката. Графът като ст ..




Граф (структура от данни)
                                     

ⓘ Граф (структура от данни)

В компютърните науки, граф е абстрактна структура от данни, имаща за цел да имплементира терминът граф от математиката.

Графът като структура от данни представлява връзките между отделните елементи на дадено множество. Всеки член на това множество се нарича връх, а връзката между два върха се нарича ребро. Честата употреба на графите в практиката е довела до задълбочени изследвания в теория на графите, в която са известни огромен брой задачи за графи и за повечето от тях има и добре известно решение.

Имплементацията на граф може да асоциира към всеки връх дадена стойност, като буквено-цифрово означение или дадена стойност.

                                     

1. История

Първата работа по теория на графите е статията на Ойлер за Кьонигсбергските мостове 1736. Тя обаче остава единствена в течение на 100 години. Интересът към този клон от математиката и към частния случай - дърветата, се възражда около средата на 19 век и е съсредоточен главно в Англия. Върху развитието на Теорията на графите оказват забележимо влияние естествените науки, тъй като тя има приложения в различни области – при изследването на електрическите вериги, моделите на кристалите, структурата на молекулите, в теорията на игрите и програмирането, в биологията и психологията и т.н. Терминът е употребен най-напред в статия на Кьониг, а след това и в монографията му Theorie der endlichen und unendlichen Graphen "Теория на крайните и безкрайните графи", 1936, но самият Кьониг го е заимствал от статия на Шур 1912, в която граф се нарича фигура, състояща се от няколко числа или точки, някои двойки от които са съединени помежду си.

                                     

2.1. Основни понятия Дефиниция

Термин от математиката, с който се означава наредена двойка G=V,E, където

  • E е множество от двучленни подмножества на V, т.е. E ⊆ V×V. Когато в тези двучленни подмножества няма наредба, т.е. формират ненаредени двойки, е прието да се наричат ребра или още ръбове на графа, а той от своя страна – неориентиран ненасочен граф. Когато тези двойки са наредени, елементите на се наричат дъги, а графът G – ориентиран насочен граф.
  • V е множество от елементи, наречени върхове,
                                     

2.2. Основни понятия Ребро Дъга

Дъга англ.: arc за ориентиран граф, ребро англ.: edge за неориентиран – това е релация между два върха в графа. В общия случай, дъга i, j бележи дали има път от i-тия връх до j-ия, като i-ия се нарича опашка англ: tail, а j-ия – глава на дъгата англ.: head. Често дъгите са свързани и със съответна стойност за преход през тях, която се нарича тегло на дъгата англ.: edge value.

                                     

2.3. Основни понятия Път

Път в ориентиран неориентиран граф GV,A се нарича последователност от върхове v1, v2, … vk, такива че за всяко i = 1, 2… k-1 е в сила vi,vi+1∈A. Върховете v1 и vk се наричат краища на пътя. Ако v1 = vk, то има цикъл. Ако няма повтаряне на върхове в даден път в частност цикъл, тогава пътят е прост за всяко i≠j 1≤i,j≤k следва vi≠vj). Ако даден граф има път от всеки връх до всеки друг – графът е свързан. С On сложност, където n е броят на дъгите, може да се определи дали даден граф е свързан или не DFS.

  • Дължина на път е броят на ребрата, свързващи последователността от върхове в пътя. Този брой е равен на броят на върховете в пътя минус единица.
  • Цикъл англ.: loop в графа G е път, за който началният и крайният връх съвпадат.
  • Прост цикъл – цикъл, в който няма повтарящи се възли.
  • Цена на път в претеглен граф, се нарича сумата от теглата на ребрата участващи в пътя.
  • Ойлеров цикъл – цикъл, който включва всички ребра на графа точно по веднъж.
  • Хамилтонов цикъл – цикъл, който включва всички възли на графа точно по веднъж.


                                     

3. Видове графи

  • Краен неориентиран граф англ.: undirected graph се нарича наредената двойка V,E, където
  • E = {e1, e2, …,em} е крайно множество от неориентирани ребра.
  • V = {v1,v2,…,vn} е крайно множество от върхове
  • Ориентиран граф англ.: directed graph – Фир. 1 – ребрата са насочени, изобразяват се чрез стрелки. Две ребра, свързващи еднакви върхове, но различно ориентирани, за по-голяма прегледност се изобразяват с една двупосочна стрелка.
  • Мултиграф англ.: multigraph – възможно е повече от едно ребро да свързва два върха.
  • Претеглентегловен англ.:weighted graph – на всяко ребро е присвоена някаква стойност – тегло.
  • Регулярен граф – граф, при който всеки връх има равен брой съседни върхове, т.е. всички върхове на графа са от една и съща степен.
                                     

4. Алгоритми

Графовите алогоритми са значителна област на интерес в компютърните науки. Типични орерации от високо ниво, свързани с графите за намиране на път между два върха:

  • Намиране на най-кратък път между два върха
  • Алгоритъм на Дейкстра.
  • Обхождане в дълбочина.
  • Обхождане в ширина.
  • Алгоритъм на Флойдна английски език: Floyd–Warshall algorithm.
  • Алгоритъм на Белман-Форд.
                                     

5. Видове представяния

Съществуват много различни начини за представяне на граф в програмирането. Различните представяния имат различни свойства и кое точно трябва да бъде избрано, зависи от конкретния алгоритъм, който трябва да се приложи. Ето някои от най-често срещаните представяния на графи:

  • Матрица на съседство англ.: Adjacency matrix – графът се представя като квадратна матрица g, където М е броят на върховете, а N е броят на ребрата. Всеки стълб представя едно ребро, а всеки ред един връх. Тогава в стълба съответстващ на реброто vi, vj само и единствено на позиция i и на позиция j ще бъдат записани 1, на останалите позиции в този стълб ще е записана 0. Ако реброто е примка т.е. е vi, vi, то на позиция i се записва 2. Ако графът, който се представя е ориентиран и се иска да се предсрави ребро от vi до vj, то на позиция i се пише 1, на позиция j съответно -1.
  • Списък на наследниците англ.: Adjacency list – в това представяне за всеки връх v се пази списък с върховете, към които сочат ребрата започващи от v. Тук отново, ако графът е претеглен, към всеки елемент от списъка с наследниците се добавя допълнително поле, показващо цената на реброто до него.
  • Списък на ребрата – представя се, чрез списък от наредени двойки vi, vj, където съществува ребро от vi до vj. Ако графът е претеглен, то вместо наредена двойка имаме наредена тройка, като третият ѝ елемент показва какво е теглото на даденото ребро.

Следващата таблица предсвавя изчислителната сложност, нужна за извършването на дадени операции за даден вид представяне.



                                     

6. Операции

Основните операции свързани със структура от данни – граф G обикнивенно включват:

  • get_node_value G, x: връща стойността асоциирана с върха x.
  • adjacent G, x, y: проверка дали има път от връх x до връх y.
  • delete G, x, y: премахва реброто от x към y, ако съществува.
  • neighbors G, x: изкарва всички върхове y който осигуряват път между x и y.
  • set_node_value G, x, a: присвоява на върха x стойност a.
  • add G, x, y: добавя към G ребродъга от x към y, ако все още не съществува.

Към графи, в който са асоциирани стойности към ребрата, обикновено са включени следните командиоперации:

  • set_edge_value G, x, y, v: присвоява на дъгата x, y стойността v.
  • get_edge_value G, x, y: връща стойността на реброто x, y.
                                     

7. Основни приложения и задачи за графи

Графите се използват за моделиране на много ситуации от реалността, а задачите върху графи моделират множество реални проблеми, които често се налага да бъдат решавани:

  • Карта на град може да се моделира с ориентиран претеглен граф. На всяка улица се съпоставя ребро с дължина съответстваща на дължината на улицата и посока – посоката на движение. Ако улицата е двупосочна може да ѝ се съпоставят две ребра за двете посоки на движение. На всяко кръстовище се съпоставя връх. При такъв модел са е стествени задачи като търсене на най-кратък път между две кръстовища, проверка дали има път между две кръстовища, проверка за цикъл дали можем да се завъртим и да се върнем на изходна позиция, търсене на път с минимален брой завои и т.н.
  • Компютърна мрежа може да се моделира с неориентиран граф, чиито върхове съответстват на компютрите в мрежата, а ребрата съответстват на комуникационните канали между компютрите. На ребрата могат да се съпоставят различни числа, примерно капацитет на канала или скорост на обмена и др. Типични задачи при такива модели на компютърна мрежа са проверка за свързаност между два компютъра, проверка за двусвързаност между две точки съществуване на двойно-подсигурен канал, който остава при отказ на който и да е компютър и др. В частност Интернет може да се моделира като граф, в който се решават задачи за маршрутизация на пакети, които се моделират като задачи за графи.
  • Речната с истема в даден регион може да се моделира с насочен претеглен граф, в който всяка река се състои от едно или няколко ребра, а всеки връх съответства на място, където две или повече реки се вливат една в друга. По ребрата могат да се съпоставят стойности, свързани с количеството вода, което преминава по тях. Естествени при този модел са задачи като изчисление на обемите вода, преминаващи през всеки връх и предвиждане на евентуални наводнения при увеличаване на количествата.
                                     

8. Източници

  • Красимир Манев, "Увод в дискретната математика", издателство КЛМН, София, 2003, ISBN 954-535-136-5
  • Иржи Седлачек, "Теория на графите", "Наука и изкуство", София, 1967
  • Светлин Наков, Веселин Колев и др., "Въведение в програмирането", Фабер, 2009. ISBN 978-954-400-527-6.
  • MyCodeSchool - Data structures