Теория на графите, тема 3.

Дървета

Както знаем, дървото е неориентиран, свързан, ацикличен граф, повече дефиниции за дърво има в Тема 1.
Гора е неориентиран, ацикличен граф. Както името подсказва, това е граф, съвкупност от отделни дървета.

Свойства за граф - дърво, покриващо дърво (Spanning tree)

Дефиниция: за граф G = (V, A), дърво на графа G, ще наричаме частичен граф $G^T \mbox{ = (V, T} \subset A)$, или иначе казано - покриващо дърво на G.

Дефиниция: Максимално дърво/гора на граф G ще наричаме разбиване на върховете на G в непресичащи се множества Vi, сформиращи подграфи Gi(Vi, Ai), такива, че съществува дърво GTiна графа Gi в което участват всичките върхове от Vi.

Твърдение: Максимална гора на произволен граф G с P компонента на свързаност има N - P ребра, където N е броят на върховете в G.

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

Алгоритъм за построяване на максимално дърво на граф: Даден е граф G = (V, A), търсим дърво на графа GT = (V, T). Избираме ребра, като ги оцветяваме в 2 цвята - син и червен. Син цвят значи, че не сме взели даденото ребро в T, червен - взели сме го. Оцветяваме в червено, като следим да не получим цикъл в червено оцветен. Нека графът GR е подграф на G съдържащ само оцветените в червено ребра. След като вече не можем да оцветим повече ребра в червено, без да създадем цикъл, то $G_R = G^T$.
Забележка: достатъчен ни е само 1 цвят, и то дори може и без него, просто вкарваме ребра в T като следим да не създадем цикъл в него, но цветовете са част от обясненията на Янев и затова го предавам така.

Твърдение: за дърво на граф GT = (V, T), и ребро u : $u \in T$ следва, че съществува единствен коцикъл, съдържащ u. По друг начин казано, като премахнем произволно ребро от едно дърво получаваме 2 дървета. Да отбележим, какво в нашия случай представлява коцикъл породен от ребро, нека реброто е u = (i,j), : това е разбиване на върховете на 2 множества едното множество е от върхове, от които, след премахването на u от T, все още има път до връх i, аналогично за другото множество - има път до връх j.
Доказателство:

Твърдение: за дърво на граф GT = (V, T), и ребро u : $u \notin T$ следва, че в $T\bigcup \{u\}$ съществува единствен цикъл с u.
Доказателство:

Важно свойство за матрица на инцидентност на Дърво

Твърдение: Нека G е ориентиран граф с N върха и N - 1 дъги, А е матрица на инцидентност на G и А` е получена от A след изтриване на произволен ред, тогава:
а) Ако G съдържа цикъл, detA` = 0;
б) G е дърво <=> |detA`| = 1;

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

Оптимално покриващо дърво

Дефиниция: GT = (V, T) е минимално (максимално) покриващо дърво (Minimal Spanning Tree - MST) е дърво на граф G, за което за всяко друго дърво на GT* = (V, T*) е в сила : $\sum c_u \le \sum c_v, \mbox{ \forall u \in T, \forall v \in T^* }$, където cu е теглото на реброто u.

Алгоритъм на Прим за построяване на МПД

Идеяата на този алгоритъм е един алчен (greedy) подход към проблема. Дървото, което строим, е с корен. Алгоритъмът започва с едно множество $T : T \subset V$ с един връх в него - коренът на бъдещото МПД, за който вземаме произволен връх от V, нека е връх 1. Нека с di бележим най-късия път от S до връх i, $i \notin S$.

(1)
\begin{align} d_i = \begin{cases} \min \mbox{l(1, i) } &\mbox{ for i} \notin S \mbox{ and } \exists (1, i) \in E \\ \inf & else\\ \end{cases}\\ \end{align}

d1 = 0;

Следва N - 1 пъти прилагане на следните действия:

  • намираме връх i, такъв че $i \notin S$, $d_i = min_{j \notin S}d_j$;
  • $\mbox{ S = S } \bigcup \{i\}$;
  • update на масива d, за всяко j ∉ S dj = min{dj , l(i, j)}, като l(i, j) = inf, ако такова ребро не е част от E.
  • ако $\|S\| = N$ край;
  • goto 1.

Твърдение - Теорема 1: Твърдението, че горният алгоритъм е верен, е свързано със следната теорема : Т е МПД <=> $\forall u \in T$ е в сила, че $w_u \le w_v, v \in \Theta^u$, където wi е теглото на реброто i, а $\Theta^u$ е коцикълът, към който принадлежи u.
Доказателство:

Сложност: Като цяло сложността на алгоритъма е O(N2), но за редки графи, може да се достигне до сложност O(MlogN) с помощта на приоритетна опашка (heap).

Алгоритъм на Крускал за построяване на МПД

Отново алгоритъмът е алчен. Нека дървото ни е GT = (V, T), на графа G = (V, E):

  1. Разделяме N-те върхове на графа в N отделни множества Si , i = 1 … N;
  2. Сортираме ребрата по намаляваща стойност на теглата им;
  3. N - 1 пъти избираме реброто u с най-малко тегло, за което $u \notin T$ и което свързва две отделни множества Si и Sj в ново множество $S_k = S_i \bigcup S_j$;

Твърдение: Дървото построено от алгоритъмът на Крускал е оптимално.

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

Сложност: За граф G с N върха и M дъги, сложността на сортирането е O(МlogМ), проверката дали дадени 2 множества Si и Sj са отделни е О(logN), тя се извършва N пъти, следователно общата сложност е O(NlogN + MlogM) [Наков 2005].

Теорема 2: T e МПД <=> за $\forall u \notin T$ е в сила, че $w_u \ge w_v$, $\forall v \in \delta^u$, където $\delta^u$ е цикъл, в който участва u.
Доказателство:

Съществува и втори вариант на алгоритъма на Крускал, без сортиране. Присъединяваме ребра към Т, докато не образуваме цикъл. Щом това стане, махаме най-тежкото ребро от цикъла. Сложността на този вариант е приблизително O(N2).

Задачи

Дефиниция: За граф G = (V, A), път L в G, тегла на реброто i e wi, то $infsection = \min_{e \in L}W_e$, $supsection = \max_{e \in L}W_e$
Задача 1: За граф G = (V, A), да се намери max infsection / min supsection, между върховете s и t.

Задача 2: За граф G = (V, A) се търси път L между върхове s и t, такъв че , ако Pst е множеството от пътища от s до t в G, то $L = min_{L \in P_{st}}\{supsection^L - infsection^L\}$. Простичко казано, търси се такъв път от s до t, че резликата между най-тежката дъга и най-леката дъга от пътя е минимална.

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