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

Вижте пояснителната страница за други значения на Граф.

---

Фиг. 1 – Ориентиран граф

Граф с 3 върха и 3 ребра

Пример за графи, използвани в графовата база от данни Neo4j

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

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

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

История

Първата работа по теория на графите е статията на Ойлер за Кьонигсбергските мостове (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) – възможно е повече от едно ребро да свързва два върха (при ориентиран граф – възможно е тези ребра, освен това, да са ориентирани еднакво).
• Регулярен граф – граф, при който всеки връх има равен брой съседни върхове, т.е. всички върхове на графа са от една и съща степен.

Алгоритми

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

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

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

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

• Списък на ребрата – представя се, чрез списък от наредени двойки (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.

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

	Списък на наследниците	Матрица на съседство	Матрица на инцидентност
Заемано ространсво	$O(|V|+|E|)$	$O(|V|^{2})$	$O(|V|\cdot |E|)$
Добавяне на връх	$O(1)$	$O(|V|^{2})$	$O(|V|\cdot |E|)$
Добавяне на ребро	$O(1)$	$O(1)$	$O(|V|\cdot |E|)$
Изтриване на връх	$O(|E|)$	$O(|V|^{2})$	$O(|V|\cdot |E|)$
Изтриване на ребро	$O(|E|)$	$O(1)$	$O(|V|\cdot |E|)$
Забележки	При премахване на върхове или ребра, трябва да бъдат намерени всички ребра и върхове	Бавен при премахване/добавяне на върхове, защото цялата матрица трябва да се оразмери	Бавен при премахване и добавяне на ребра и върхове, защото цялата матрица трябва да се преоразмери/копира

Операции

Основните операции свързани със структура от данни – граф 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.

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

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

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

Вижте също

• Теория на графите
• Граф (математика)
• Структура от данни
  • Дърво (структура от данни)
  • Стек (структура от данни)
  • Списък (абстрактен тип данни)

Източници

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

Външни препратки

• My Code School Архив на оригинала от 2015-05-02 в Wayback Machine.
• Увод в теория на графите
• ((en)) Въведение в програмирането
• Програмиране=++Алгоритми