Граф (структура от данни)
- Вижте пояснителната страница за други значения на Граф.
В компютърните науки, граф (мн. ч. Графи) е абстрактна структура от данни, имаща за цел да имплементира терминът граф от математиката.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/5/51/Directed_graph.svg/200px-Directed_graph.svg.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/a/a2/Directed.svg/200px-Directed.svg.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/4/41/Basic_terms_in_graph_theory_Bulgarian.png/200px-Basic_terms_in_graph_theory_Bulgarian.png)
Графът като структура от данни представлява връзките между отделните елементи на дадено множество. Всеки член на това множество се нарича връх, а връзката между два върха се нарича ребро. Честата употреба на графите в практиката е довела до задълбочени изследвания в теория на графите, в която са известни огромен брой задачи за графи и за повечето от тях има и добре известно решение.
Имплементацията на граф може да асоциира към всеки връх дадена стойност, като буквено-цифрово означение или дадена стойност(константа, капацитет, дължина и т.н.).
История
редактиранеПървата работа по теория на графите е статията на Ойлер за Кьонигсбергските мостове (1736). Тя обаче остава единствена в течение на 100 години. Интересът към този клон от математиката и към частния случай – дърветата, се възражда около средата на 19 век и е съсредоточен главно в Англия. Върху развитието на Теорията на графите оказват забележимо влияние естествените науки, тъй като тя има приложения в различни области – при изследването на електрическите вериги, моделите на кристалите, структурата на молекулите, в теорията на игрите и програмирането, в биологията и психологията и т.н.
Терминът е употребен най-напред в статия на Кьониг, а след това и в монографията му Theorie der endlichen und unendlichen Graphen („Теория на крайните и безкрайните графи“, 1936), но самият Кьониг го е заимствал от статия на Шур (1912), в която граф се нарича фигура, състояща се от няколко числа или точки, някои двойки от които са съединени помежду си.
Основни понятия
редактиранеДефиниция
редактиранеТермин от математиката, с който се означава наредена двойка G=(V,E), където
- V е множество от елементи, наречени върхове,
- E е множество от двучленни подмножества на V, т.е. E ⊆ V×V. Когато в тези двучленни подмножества няма наредба, т.е. формират ненаредени двойки, е прието да се наричат ребра или още ръбове на графа, а той от своя страна – неориентиран (ненасочен) граф. Когато тези двойки са наредени, елементите на Е се наричат дъги, а графът G – ориентиран (насочен) граф.
Връх
редактиранеВръх на граф (на английски език: vertex или node) – елементи, съвкупността от които, свързани в подмножества образуват елемент от наредената двойка репрезентирана от графа.
Ребро (Дъга)
редактиранеДъга (англ.: arc) за ориентиран граф, ребро (англ.: edge) за неориентиран – това е релация между два върха в графа. В общия случай, дъга (i, j) бележи дали има път от i-тия връх до j-ия, като i-ия се нарича опашка (англ: tail), а j-ия – глава на дъгата (англ.: head). Често дъгите са свързани и със съответна стойност за преход през тях, която се нарича тегло на дъгата (англ.: edge value).
Път
редактиранеПът в ориентиран (неориентиран) граф G(V,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). Ако даден граф има път от всеки връх до всеки друг – графът е свързан. С O(n) сложност, където n е броят на дъгите, може да се определи дали даден граф е свързан или не (DFS).
- Дължина на път е броят на ребрата, свързващи последователността от върхове в пътя. Този брой е равен на броят на върховете в пътя минус единица.
- Цена на път в претеглен граф, се нарича сумата от теглата на ребрата участващи в пътя.
- Цикъл (англ.: loop) в графа G е път, за който началният и крайният връх съвпадат.
- Прост цикъл – цикъл, в който няма повтарящи се възли.
- Хамилтонов цикъл – цикъл, който включва всички възли на графа точно по веднъж.
- Ойлеров цикъл – цикъл, който включва всички ребра на графа точно по веднъж.
Видове графи
редактиране- Ориентиран граф (англ.: directed graph) – Фир. 1 – ребрата са насочени, изобразяват се чрез стрелки. Две ребра, свързващи еднакви върхове, но различно ориентирани, за по-голяма прегледност се изобразяват с една двупосочна стрелка.
- Краен неориентиран граф (англ.: undirected graph) се нарича наредената двойка (V,E), където:
- V = {v1,v2,…,vn} е крайно множество от върхове
- E = {e1, e2, …,em} е крайно множество от неориентирани ребра.
- Претеглен(тегловен) (англ.:weighted graph) – на всяко ребро е присвоена някаква стойност – тегло.
- Мултиграф (англ.: multigraph) – възможно е повече от едно ребро да свързва два върха (при ориентиран граф – възможно е тези ребра, освен това, да са ориентирани еднакво).
- Регулярен граф – граф, при който всеки връх има равен брой съседни върхове, т.е. всички върхове на графа са от една и съща степен.
Алгоритми
редактиранеГрафовите алогоритми са значителна област на интерес в компютърните науки. Типични орерации от високо ниво, свързани с графите за намиране на път между два върха:
- Обхождане в дълбочина.
- Обхождане в ширина.
- Намиране на най-кратък път между два върха:
Видове представяния
редактиранеСъществуват много различни начини за представяне на граф в програмирането. Различните представяния имат различни свойства и кое точно трябва да бъде избрано, зависи от конкретния алгоритъм, който трябва да се приложи. Ето някои от най-често срещаните представяния на графи:
- Списък на ребрата – представя се, чрез списък от наредени двойки (vi, vj), където съществува ребро от vi до vj. Ако графът е претеглен, то вместо наредена двойка имаме наредена тройка, като третият ѝ елемент показва какво е теглото на даденото ребро.
- Списък на наследниците (англ.: Adjacency list) – в това представяне за всеки връх v се пази списък с върховете, към които сочат ребрата започващи от v. Тук отново, ако графът е претеглен, към всеки елемент от списъка с наследниците се добавя допълнително поле, показващо цената на реброто до него.
- Матрица на съседство (англ.: Adjacency matrix) – графът се представя като квадратна матрица g[N][N], в която, ако съществува ребро от vi до vj, то на позиция g[i][j] в матрицата е записано 1. Ако такова ребро не съществува, то в полето g[i][j] е записано 0. Ако графът е претеглен, в позиция g[i][j] се записва теглото на даденото ребро, а матрицата се нарича матрица на теглата. Ако между два върха в такава матрица не съществува път, то тогава се записва специална стойност, означаваща безкрайност.
- Матрица на инцидентност между върхове и ребра (англ.: Incidence matrix) – в този случай отново се използва матрица, само че с размери g[M][N], където М е броят на върховете, а N е броят на ребрата. Всеки стълб представя едно ребро, а всеки ред един връх. Тогава в стълба съответстващ на реброто (vi, vj) само и единствено на позиция i и на позиция j ще бъдат записани 1, а на останалите позиции в този стълб ще е записана 0. Ако реброто е примка т.е. е (vi, vi), то на позиция i се записва 2. Ако графът, който се представя е ориентиран и се иска да се предсрави ребро от vi до vj, то на позиция i се пише 1, а на позиция j съответно -1.
Следващата таблица предсвавя изчислителната сложност, нужна за извършването на дадени операции за даден вид представяне.
Списък на наследниците | Матрица на съседство | Матрица на инцидентност | |
---|---|---|---|
Заемано ространсво | |||
Добавяне на връх | |||
Добавяне на ребро | |||
Изтриване на връх | |||
Изтриване на ребро | |||
Забележки | При премахване на върхове или ребра, трябва да бъдат намерени всички ребра и върхове | Бавен при премахване/добавяне на върхове, защото цялата матрица трябва да се оразмери | Бавен при премахване и добавяне на ребра и върхове, защото цялата матрица трябва да се преоразмери/копира |
Операции
редактиранеОсновните операции свързани със структура от данни – граф G обикновено включват:
adjacent
(G, x, y): проверка дали има път от връх x до връх y.neighbors
(G, x): изкарва всички върхове y който осигуряват път между x и y.add
(G, x, y): добавя към G ребро(дъга) от x към y, ако все още не съществува.delete
(G, x, y): премахва реброто от x към y, ако съществува.get_node_value
(G, x): връща стойността асоциирана с върха x.set_node_value
(G, x, a): присвоява на върха x стойност a.
Към графи, в който са асоциирани стойности към ребрата, обикновено са включени следните команди(операции):
get_edge_value
(G, x, y): връща стойността на реброто (x,y).set_edge_value
(G, x, y, v): присвоява на дъгата (x,y) стойността v.
Основни приложения и задачи за графи[1]
редактиранеГрафите се използват за моделиране на много ситуации от реалността, а задачите върху графи моделират множество реални проблеми, които често се налага да бъдат решавани:
- Карта на град може да се моделира с ориентиран претеглен граф. На всяка улица се съпоставя ребро с дължина съответстваща на дължината на улицата и посока – посоката на движение. Ако улицата е двупосочна може да ѝ се съпоставят две ребра за двете посоки на движение. На всяко кръстовище се съпоставя връх. При такъв модел са е стествени задачи като търсене на най-кратък път между две кръстовища, проверка дали има път между две кръстовища, проверка за цикъл (дали можем да се завъртим и да се върнем на изходна позиция), търсене на път с минимален брой завои и т.н.
- Компютърна мрежа може да се моделира с неориентиран граф, чиито върхове съответстват на компютрите в мрежата, а ребрата съответстват на комуникационните канали между компютрите. На ребрата могат да се съпоставят различни числа, примерно капацитет на канала или скорост на обмена и др. Типични задачи при такива модели на компютърна мрежа са проверка за свързаност между два компютъра, проверка за двусвързаност между две точки (съществуване на двойно-подсигурен канал, който остава при отказ на който и да е компютър) и др. В частност Интернет може да се моделира като граф, в който се решават задачи за маршрутизация на пакети, които се моделират като задачи за графи.
- Речната с истема в даден регион може да се моделира с насочен претеглен граф, в който всяка река се състои от едно или няколко ребра, а всеки връх съответства на място, където две или повече реки се вливат една в друга. По ребрата могат да се съпоставят стойности, свързани с количеството вода, което преминава по тях. Естествени при този модел са задачи като изчисление на обемите вода, преминаващи през всеки връх и предвиждане на евентуални наводнения при увеличаване на количествата.
Вижте също
редактиранеИзточници
редактиране- MyCodeSchool – Data structures
- Светлин Наков, Веселин Колев и др., „Въведение в програмирането“, Фабер, 2009. ISBN 978-954-400-527-6.
- Иржи Седлачек, „Теория на графите“, „Наука и изкуство“, София, 1967
- Красимир Манев, „Увод в дискретната математика“, издателство КЛМН, София, 2003, ISBN 954-535-136-5
Вътрешни препратки
редактиране- ↑ Светлин Наков и колектив. Въведение в програмирането с Java. Фабер, 2009. ISBN 978-954-400-055-4. с. 653 – 662.