Основни понятия

Основни понятия

Що е то, Граф

Да дефинираме малко думички:
връх на граф (на английски vertex или node) - както е със състоянията в КДА (Краен Детерминистичен Автомат), така и графите ще обхождаме от връх към връх.

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

Граф G ще наричаме наредената двойка (V, A), където V е крайно множеството от върховете на графа, а А - крайно множество от дъги. Графите като цяло най-често биват разделяни в два вида - ориентирани и неориентирани. При ориентираните графи е от значение наредбата в наредената двойка върхове, която определя дадена дъга, докато при неориентирания дъгите (i,j) и (j,i) са еквивалентни. Често се казва че в неориентирания случай имаме ребра, а не дъги.

път в ориентиран (неориентиран) граф G(V,A) се нарича последователност от върхове v1, v2, … vk, такива че за всяко i = 1, 2… k-1 е в сила $(v_i , v_{i+1}) \in A$. Върховете v1 и vk се наричат краища на пътя. Ако v1 = vk, то казваме че има цикъл. Ако няма повтаряне на върхове в даден път (в частност цикъл), тогава пътят е прост ( за всяко $i \ne j \mbox{ } (1 \le i,j \le k)$ следва $v_i \ne v_j$). Ако за даден граф имаме приятното качество, че има път от всеки връх до всеки друг, казваме че графът е свързан. С O(n) сложност, където n е броят на дъгите, може да се определи дали даден граф е свързан или не (DFS).

верига ще наричаме нещо, което адски много прилича на път, но не е път. Това е редица от дъги e1, e2… ek, за които е в сила правилото - две дъги са съседни във веригата <=> същите две дъги са съседни и в графа. Верига можем да запишем и чрез поредицата от върхове, от които излизат/влизат дъгите. Ето един пример за верига в граф, която не е път - веригата 1, 2, 3, 4:

gt1_1.png

Мултиграф ще наричаме граф в, който може да има повече от една дъга, за дадена наредена двойка върхове.

Примка (на английски loop) ще наричаме дъги от вида - (i, i).

Степен За всеки връх ще дефинираме оценка степен по следния начин:
степента на входа на връх j (in degree) е броя на ребрата (i, j) oт А, за i oт V.
степента на изхода на връх j (up degree) е броя на ребрата (j, i) oт А, за i oт V.
степен на върха j е сбора на степента му на изход и на степента му на вход.
Ако степента на даден връх е 0, ще наричаме този връх изолиран.
За връх в неориентиран граф степен на вход, степен на изход и степен на връх са едно и също число.

Наследници и предшественици на връх. За даден връх i ще казваме, че връх j му е наследник тогава и само тогава, когато $\exists (i,j) \in A$. Аналогично за върхът i, предшественик ще наричаме връх k, за който i е наследник. Множеството от наследници на даден връх i ще бележим с Гi, а множеството от предшественици - Г-1 i.

Подграф на даден граф G (V, A) ще наричаме граф G` (V` , A`), такъв че $V` \subset V$ и
за всяко ребро (i, j) от A` имаме $i \in V` \cap j \in V`$.

Индуциран подграф на даден граф G (V, A) е за $X : X \subset V$, подграф G- = (X, A(X)).

Частичен граф на даден граф G (V, A) е за $Y : Y \subset A$, граф G= = (V, Y).

Клика (английски clique) ще наричаме граф или подграф, в който има ребро между всеки два върха. По начало, задачите за търсене на клики в граф са NP-пълни, примери са "Търсене на максимална клика в граф по брой на върховете в нея", "Търсене на клика с дължина К" и др. Примери за клика с 3 върха е произволен триъгълник, ето пример за клика с 6 върха.

tg1_2.png

Двуделен граф или bipartite graph ще наричаме специален граф със следното свойство:

  • Върховете на графа могат да бъдат разделени на две непресичащи се множества $V = X_1 \bigcup X_2$
  • Всички дъги в графа свързват връх от X1 с връх от X2 $\forall (i,j) \in A \Rightarrow i \in X_1 \bigcap j \in X_2$ или $i \in X_2 \bigcap j \in X_1$. Както ще видим, двуделните графи са много важни за теорията на графите. Съществуват цял клас задачи свързани само със двуделни графи, алгоритмите за които са изключително интересни и нетривиални.
tg1_bipartite.png

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

  • Свързан граф с N върха и N - 1 ребра (става дума за неориентиран граф)
  • Граф в който между всеки 2 върха съществува единствен път
  • Максимално ацикличен граф (каквото и ребро да добавим към него ще получим цикъл)
  • Минимално свързан граф (което и ребро да отстраним, графът вече няма да е свързан).
  • Рекурентна дефиниция:
      • Всеки връх сам по себе си е дърво.
      • Ако към дърво прибавим връх, който е свързан с точно едно ребро към някой от вече съществуващите върхове, отново ще се получи дърво.
      • Няма други дървета
tg1_tree.png

Като цяло в теория на графите ще разглеждаме ориентирани графи. Ако става дума за неориентиран граф, това ще бъде изрично споменато. Освен това графите, на които ще се спрем, по подразбиране няма да имат примки и няма да са мултиграфи.

Представяне на граф

След като вече знаем какво представлява понятието граф и какви графи ще са интересни за предмета, време е да помислим и за представянето им, било на лист, било в паметта на компютъра.

Матрица на инцидентност

Един от основните начини е чрез матрица на инцидентност връх - дъга. Нека имаме граф G = (V, A), където броят на върховете е някакво естествено число n (|V| = n) , а на дъгите m, отново естествено (|A| = m). Дефинираме матрица АМ (бележим с М за да се различава от множеството от дъги на графа - А), с размерност [n x m], където за всеки елемент a[i][k] имаме три възможни стойности
- a[i][k] = -1 ако i-тият връх е край(tail) на k-тата дъга;
- a[i][k] = 1 ако i-тият връх начало(head) на k-тата дъга;
- a[i][k] = 0 ако i-тият връх не участва в k-тата дъга;

Пример, пълен граф с три върха:

A B C
1 1 -1 0
2 0 1 -1
3 -1 0 1

Опитайте се да познаете как изглежда графът.

Унимодулярност. Квадратната матрица АМ наричаме унимодулярна, ако детерминантата й има стойност 1 или -1.
Матрица АМ ще наричаме абсолютно унимодулярна, ако произволна нейна квадратна подматрица е унимодулярна или с детерминанта 0.

Теорема 1. Ако АМ е матрица на инцидентност от тип връх - дъга, то АМ е абсолютно унимодулярна.

Доказателство:

Теорема 2. Необходимо и достатъчно условие един граф да е двуделен е да не съдържа цикли с нечетна дължина.
Доказателство:

Теорема 3. Матрица на инцидентност на неориентиран граф е абсолютно унимодулярна <=> графът е двуделен.

Дефиниция Характеристичен вектор м от типа {0, 0, 1, -1, 0… } с брой на елементите mi, i = 1… N, равен на броя на ребрата в графа, където за m[i] е в сила :

  1. m[i] = 1 ako сме избрали i-тата дъга без да обръщаме посоката й.
  2. m[i] = -1 ako сме избрали дъгата i, но с обратна посока.
  3. mi = 0 ако въобще не е взета тази дъга.

Този вектор дефинира подмножество на ребрата в граф и може да се използва по следния начин:
Цикъл, в граф G(V,A) с 5 върха и 5 дъги, представен в характеристичен вектор м = {0, 1, -1, 1, 1}:

gt1_cycle.png

Твърдение Нека АМ е матрица на инцидентност на граф G(V,A). Тогава, за произволен м, представящ цикъл, е в сила $A\mu \equiv 0(mod 2)$. Или по друг начин казано, за всеки цикъл, степента на върховете е четна. Като пример за размисъл по твърдението може да се вземе прочутата задача на Ойлер за Кьонингсбергските мостове.

Коцикъл ще наричаме, ако разбием множеството V на 2 подмножества X и X- и вземем дъгите свързващи елементи от
X- и X. С W+(X) ще бележим дъгите излизащи от X, а с W-(X) дъгите излизащи от X-. Тогава коцикъл е $W(X) = W^+(X)\bigcup W^-(X)$, или както ще го наричаме по-късно при работа с потоци отсичащо множество. Множеството от всички дъги в двуделен граф образува коцикъл.

Tвърдение Нека $\pi$ е характеристичен вектор на Х, и $\theta$ е вектор с елементи a[i] = 1 ако i-тата дъга e oт W+(X), -1 aко е от W-(X) и 0 иначе. Тогава е в сила : $\theta \equiv \pi A(mod 2)$.

Плюсове и минуси:

(+)

  • Тази форма е удобна за математически доказателства.

(-)

  • Повечето алгоритми не могат да се възползват от тази форма.
  • Заема n*m място. Тоест, n*n*n място в най-лошия случай. Пълен граф с 1000 върха - 1000000000 (~4 Гигабайта в програма, използваща тип int) клетки. На всичкото отгоре съвсем малка част от матрицата реално се използва - почти всичко са нули.

Матрица на достижимост

Дефиниция За графи с тегла на ребрата: матрица на достижимост на графа G(V, A) ще наричаме матрицата D такава, че за всяка двойка върхове i и j, от 1 до N, dij = k тогава и само тогава, когато $\exists (i,j) \in A$ и теглото на дъгата (i,j) е k (l(i,j) = k). За графи без тегла взимаме l(i,j) = 1, за$\forall (i,j) \in A.$.
Пример, пълен граф с три върха:

A B C
A 0 -1 1
B 1 0 -1
C -1 1 0

Плюсове и минуси:

(+)

  • Ако в изпълнението на даден алгоритъм често се налага да се отговаря на въпроса "Има ли дъга от връх i do j?", матрицата на достижимост е просто задължителна. Сложността на изпълнението на въпросната проверка със матрица на достижимост е O(1) (тоест константна, просто се гледа какво пише на тази позиция в масива).

(-)

  • Ако се търси отговор на въпроси от типа "колко е степента на изход/вход на даден връх", или да обходите всички съседи на даден връх (било наслецници или предшественици), матрицата на достижимост съвсем не е оптималният подход, тъй като и в най-добрия случай дава сложност O(N) (линейна по броя на върховете в графа). Например, за граф с 1000 върха и пет ребра всяка проверка колко съседа има даден връх ще отнема 1000 операции.
  • Не е подходяща за много големи графи. 1000 ребра - 1000000 клетки (4 Мегабайта). 10000 ребра - 100000000 клетки (~400 Мегабайта при разумна реализация).

Списък на наследниците

По името е ясно какво представлява - за всеки връх i от графа G в списъка на наследниците ще се пазят непосредствените наследници на i.
Най-популярната реализация на този подход е с динамично променящи размера си структури. В C++ STL може да се използват vector и map. Най-често използваните структури от данни за целта са свързани списъци и асоциативни масиви. В много езици масивите по подразбиране са с променлива дължина.
Използва се един масив от масиви с размер n. За всеки връх има масив с нужната големина, в който се пази колко и кои върхове са свързани чрез ребро с него.

tg1_example1.png
връх наследници
1 2, 3
2 4, 5
3 2, 5
4
5

В случай на граф с тегла на ребрата се използва структура от данни, която да държи както номера на наследника, така и теглото на реброто. В C++ STL има предефиниран тип pair, който да държи два елемента, но може да се направи и специална структура за ребро.

Плюсове и минуси:

(+)

  • Като цяло отговаря на въпросите, на които матрицата на достижимост не успя да ни отговори особено ефективно.
  • Сложността на откриването на степента на изход на даден връх i е O(1)
  • Сложността на обхождане на съседите на връх - O(k), където k е степента на изхода на i.
  • Заема малко място: n + m. За граф с 10000 върха и 60000 ребра ще са нужни 70000 клетки, т.е. по-малко от 300 Килобайта памет. Забележете, че за произволен граф1 това е най-малкото количество памет, което въобще може да бъде достатъчно.

(-)

  • Ако търсим дали има дъга $(i,j) \in A$ със списък на наследниците, това с най-елементарната реализация ще ни струва O(m) действия. При използване на по-качествени структури от данни, които поддържат масивите сортирани, това може да се сведе до O(log(m)), а с хеширане и до O(1), амортизирано. Но това е предмет на друга дисциплина.

В Заключение Това е едно от най-често използваните представяния на граф и предоставя най-добрия компромис между бързодействие и използвана памет.

Списък на бащите

Списъкът на бащите е полезен начин за линейно по памет представяне на дървета в паметта. Реализира се чрез едномерен масив, нека да е на име prev, в който prev[i] е предшественикът на i-тия връх по пътя от корена до i.

tg1_example2.png
-1 -1 1 1 2 3 3

При тази реализация броенето често започва от едно, вместо от нула, защото е по-удобно за определени алгоритми. Ако ребрата имат тегла, използва се pair.
Ако дървото е двоично(всеки връх е баща или на два, или на нула други), може да се изхитрим още - въобще да не пишем ребрата никъде, защото те всички се получават по тривиален начин. В двоично дърво бащата на връх $i$ винаги е връх $[\cfrac{i}{2}]$ при индексиране от 1. Това се използва при реализиране на приоритетни опашки, индексни дървета и други структури от данни. Естествено, това може да се генерализира за дървета с разклонение (N или 0), т.е. N-ични дървета, но те се използват рядко.

Плюсове и Минуси

(+)

  • Заема n памет, поради което много големи дървета могат да се записват по този начин. 1 000 000 върха - 4 мегабайта.

(-)

  • Недостатъкът на тази реализация е, че работи само за дървета.

Списък на ребрата

Точно това, което звучи. Рядко се използва, защото в повечето случаи ни трябват и върховете за нещо.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License