6 Графови
У 18. веку, око 1735. године, појавио се тзв. проблем Кенигсбершких мостова, у руском (тада пруском) граду Калињинграду, односно тадашњем Кенигсбергу. Град је раздвојен реком Прегел (сада Прегоља) и при проласку кроз град на средини реке формирана су два мања острва (Кант и Октобар), а после проласка кроз град река се раздваја на два дела, на Стару Прегољу и Нову Прегољу. Та острва и одговарајуће обале били су спојени са 7 мостова као што је приказано на слици
Питање које се постављало тада јесте да ли се свих 7 мостова може обићи у једној шетњи, тако да се сваки мост пређе само једном. Овај проблем је привукао пажњу швајцарског математичара Леонарда Ојлера када се налазио на дужности главног председавајућег на Катедри за математику Санкт Петербуршке Академије наука. Августа 1735. године, Ојлер је овај проблем систематски и математички прво изложио Санкт Петербуршкој Академији, да би га затим решио 1736. године, доказујући да такав пут није могуће реализовати, а такође је у истом раду (Euler 1741) дао и опште решење проблема за произвољан број “копна” и произвољан број “мостова”.
Приликом решава ња проблема, Ојлер је направио скицу која је одговарала тадашњој конфигурацији мостова и реке у Кенигсбергу која је приказана на слици.
Ојлер је са \(A\), \(B\), \(C\), \(D\) означио копна, а са \(a\), \(b\), \(c\), \(d\), \(e\), \(f\) мостове који их спајају. Мостове је разматрао и као одговарајуће прелазе са једног копна на друго, тако да је прелаз са копна А на копно B означио са \(AB\), а ако би требало после преласка са копна А на копно B прећи на копно D, цео пут био би означен са ABD и представљао би прелазак 2 моста и присуство на 3 копна у том случају. На основу тога, Ојлер је закључио да би прелазак преко свих 7 Кенигсбершких мостова у овом проблему захтевао, према уведеним ознакама, 8 великих слова за копна која се у том случају узимају у обзир. У свом раду Ојлер даље развија доказ проблема, описујући ситуацију са појединачним копнима: на пример, ако би се мост \(a\) прешао једанпут, копно \(А\) би према томе било на почетку пута или на крају, односно појавило би се само једанпут. У случају да се мостови \(a\), \(b\), \(c\) и \(d\) прелазе једанпут, \(A\) би се појавило тачно два пута, независно од тога да ли је на почетку или на крају пута. Тако да ако уочимо 5 мостова који воде ка копну \(A\), на основу претходног долазимо до закључка да ће се копно \(A\) појавити тачно 3 пута за ту путању (при чему ће се сваки од мостова прелазити тачно једанпут).
Ојлер је уопштио ово тврђење, тако да гласи: уколико је број мостова било који непаран број, и ако се тај број увећа за 1, тада је број појављивања за \(A\) једнак половини датог броја. Разматрајући одговарајуће ситуације за преостале случајеве, копна \(B\), \(C\) и \(D\) морају да се појаве 2 пута, с обзиром на то да према сваком од њих воде по 3 моста. Према томе, за 7 Кенигсбершких мостова, имамо следеће: 3 појављивања за \(A\) и по 2 појављивања за \(B\), \(C\), \(D\), што у збиру даје број 9. Међутим, на почетку свог рада, Ојлер је показао да за 7 мостова мора да постоји само 8 појављивања копна, тј. 8 великих слова, што је контрадикција са чињеницом да их има 9. Према томе, није могуће прећи свих 7 Кенигсбершких мостова тачно једанпут. Овде треба приметити да је начин на који је Ојлер решио проблем, представљајући га апстрактно, помоћу линија и слова, био потпуно нов начин размишљања у то време, тако да се Ојлеров рад сматра почетком модерне теорије графова.
Све до четрдесетих година 19. века, теорија графова је углавном била скуп неповезаних, веома интересантних проблема, а мање целовита математичка теорија. Објављивање Конигове монографије 1936. године (König 1936) покренуло је заснивање теорије графова као самосталне математичке дисциплине, а између осталог, те године је појам граф ушао у општу употребу (Biggs, Lloyd, and Wilson 1986). Касније, након Другог светског рата, општи развој математике и велики захтеви у применама подстакли су развој теорије графова. Више детаља о теорији графова и њеном развоју може се наћи у (Cvetković and Milić 1971).
Појам графа
Сваки граф се састоји од скупа чворова (енгл. vertex set) којим се представљају неки објекти и скупа грана (енгл. edge set) којим се представљају односи између тих објеката. У зависности од тога да ли је скуп чворова коначан или бесконачан, графови се могу поделити на коначне и бесконачне. У наставку ће бити разматрани само коначни графови који имају примену у анализи и изучавању реалних комплексних система. Са друге стране, у зависности од начина дефинисања скупа грана, постоје различите врсте графова чије су формалне дефиниције дате у наставку.
Граф \(G=(V,E)\) се састоји од коначног непразног скупа чворова \(V\) и скупа грана \(E\subseteq \left\{\{v_i,v_j\}: v_i,v_j\in V, v_i\neq v_j\right\}\).
Гране овако дефинисаног графа омогућавају представљање искључиво неоријентисаних (неусмерених) односа између елемената из скупа \(V\) јер се представљају преко неуређених парова чворова. Такође, није могуће присуство гране која спаја чвор са самим собом (петља). Због тога се овакав граф у литератури често назива прост граф или неоријентисан граф без петљи. Дефиниција простог графа се врло једноставно може проширити тако да је \(E\subseteq V \cup \left\{\{v_i,v_j\}\,:\, v_i,v_j\in V, v_i\neq v_j\right\}\) чиме се омогућава присуство гране облика \(e=v_i\) (где је \(v_i\in V\)) која чвор \(v_i\) спаја са самим собом. Такав граф се назива неоријентисан граф са петљама. У теорији графова и теорији комплексних мрежа најчешће се разматрају графови без петљи.
Број чворова графа \(G\), у ознаци \(|V|\) назива се ред графа, док се број грана у графу \(G\), одређен као \(|E|\) назива величина графа.
Код неоријентисаног графа два чвора \(v_i, v_j \in V\) су повезана граном ако је \(\{v_i,v_j\}\in E\). У том случају чворове \(v_i, v_j\) називамо крајњим тачкама гране \(\{v_i,v_j\}\). За грану \(e=\{v_i, v_j \} \in E\) кажемо да је инцидентна чворовима \(v_i\) и \(v_j\). Два чвора \(v_i, v_j\) су суседни чворови ако представљају крајње тачке исте гране, док су две гране суседне ако су инцидентне истом чвору.
Неоријентисан граф се може представити цртежом тако што чворове графа представимо тачкама у равни, а затим непрекидним линијама повежемо суседне чворове.
Пример
Цртеж графа \(G_N\) са скупом чворова \(\{v_1,v_2,v_3,v_4,v_5,v_6\}\) и скупом грана \(\{ \{v_1,v_2\}, \{v_1,v_3\},\{v_1,v_4\},\{v_2,v_3\},\{v_2,v_4\}, \{v_2,v_5\}, \{v_3,v_4\}, \{v_4,v_5\} \}\) приказан је на слици.
Степен и околина чвора
Степен чвора \(v_i\in V\) у ознаци \(k(v_i)\) представља број грана које су инцидентне са њим.
Чвор са степеном нула назива се изолован чвор. За граф у коме сви чворови имају степен \(k\) каже се да је \(k\)-регуларан.
Околина чвора \(v_i\) у ознаци \(N(v_i)\) представља скуп свих његових суседа, тј. \(N(v_i)=\{ v_j\,:\,\{v_i,v_j\} \in E \}\). У неоријентисаном графу без петљи важи \(k(v_i)=|N(v_i)|\).
Пример
На графу \(G_N\), приказаном на претходној слици, околина чвора \(v_3\) је \(N(v_3)=\{v_1,v_2,v_4\}\) и његов степен \(k(v_3)=3\), док је чвор \(v_6\) изолован чвор.
Теорема
У неоријентисаном графу \(G=(V,E)\) збир степена свих чворова једнак је двоструком броју грана, тј. важи: \[\sum_{v\in V} k(v) = 2|E|.\]
Доказ
Свака грана у неоријентисаном графу \(G=(V,E)\) поседује две крајње тачке, а самим тим увећава степен сваке од њих за један. То значи да свака грана укупну суму степена чворова увећава за 2 и она мора да буде једнака двоструком броју грана графа тј. \(2|E|\).
Теорема
У неоријентисаном графу \(G=(V,E)\) број чворова непарног степена је паран.
Доказ
Скуп чворова \(V\) графа \(G\) можемо поделити на два скупа: скуп чворова са парним степеном \(V_0\) и скуп чворова са непарним степеном \(V_1\) тако да је \(V=V_0\cup V_1\) и \(V_0\cap V_1=\emptyset\). Са једне стране, имамо да је укупан степен чворова из \(V_0\) паран број као збир парних бројева. Са друге стране, на основу теореме 1, имамо да је укупан степен свих чворова из \(V=V_0\cup V_1\) такође паран број. На основу тога следи да укупан степен чворова из \(V_1\) мора такође да буде паран број. Како су то чворови непарног степена, њихов укупан степен ће бити паран јер је њихов број паран.
Индуковани подграф
Граф \(G'=(V',E')\) је подграф графа \(G=(V,E)\) ако је \(V'\subseteq V\) и \(E'\subseteq E\). У овом случају \(G\) је надграф од \(G'\).
Индуковани подграф скупом чворова \(C\subseteq V\), у ознаци \(G_C=(C,E_C)\) је подграф графа \(G=(V,E)\) који се добија издвајањем подскупа чворова \(C\subseteq V\) и свих грана између њих тј. \(E_C = \{\{v_i,v_j\} \in E : v_i\in C, v_j\in C\}\).
Пример
У случају графа \(G_N\), из претходног примера, индуковани подграф скупом чворова \(C_1=\{v_1,v_3,v_4,v_5\}\) је граф \(G_{C_1}\) са скупом чворова \(C_1\) и скупом грана \(\left\{ \{v_1,v_3\},\{v_1,v_4\}, \{v_3,v_4\}, \{v_4,v_5\} \right\}.\) Цртеж подграфа \(G_{C_1}\) у оквиру графа \(G_N\) приказан је на слици.
Компоненте повезаности
Пут дужине \(k\) од чвора \(v_{i_0}\) до чвора \(v_{i_k}\) у графу \(G=(V,E)\) представља низ облика \[v_{i_0},e_{j_1},v_{i_1},e_{j_2},v_{i_2},e_{j_3},v_{i_3}\dots,v_{i_{k-1}}, e_{j_k},v_{i_k}\] где су \(v_{i_0}, v_{i_1},\dots v_{i_k} \in V\), \(e_{j_1}, e_{j_2},\dots e_{j_k} \in E\) и \(e_{j_t}=\{v_{i_{t-1}},v_{i_t}\}\).
Кажемо да пут пролази кроз чворове \(v_{i_0}, v_{i_1},\dots, v_{i_{k-1}}, v_{i_k}\) што је уједно и његов краћи запис.
Прост пут од \(v_{i_0}\) до \(v_{i_k}\) је пут у коме се сваки од чворова \(v_{i_1}, v_{i_2}\dots v_{i_{k-1}}\) јавља тачно једном.
Пут који пролази кроз све чворове графа тачно једном назива се Хамилтонов пут.
Пут који пролази кроз све гране графа тачно једном назива се Ојлеров пут.
Затворен пут је пут у коме је \(v_{i_0}=v_{i_k}\), тј. почиње и завршава се у истом чвору.
Затворен прост пут се још назива контура или циклус.
Затворен Хамилтонов пут се назива Хамилтонова контура и слично затворен Ојлеров пут се назива Ојлерова контура.
Два чвора \(v_i\) и \(v_j\) су повезана ако постоји пут од чвора \(v_i\) до чвора \(v_j\). Уз то се подразумева да је сваки чвор повезан са самим собом.
Граф \(G=(V,E)\) је повезан ако су свака два чвора из \(V\) повезана. У супротном, граф је неповезан и у њему се могу издвојити компоненте повезаности.
Компонента повезаности графа \(G\) је максималан повезан подграф графа \(G\), тј. \(G'\) је компонента повезаности графа \(G\) ако је \(G'\) повезан подграф од \(G\) и не постоји други повезан подграф графа \(G\) различит од \(G'\), који је надграф од \(G'\).
Пример
Пример графа који има три компоненте повезаности приказан је на слици.
Теорема
Сваки затворен пут непарне дужине садржи контуру непарне дужине.
Доказ
Доказаћемо тврђење индукцијом по дужини \(l\) затвореног пута. За \(l=1\) затворен пут представља петљу што је уједно контура непарне дужине. Претпоставимо да сваки затворен пут чија је дужина непарна и не већа од \(2k-1\) садржи контуру непарне дужине. Посматрајмо затворен пут \(v_{i_0}, v_{i_1}, \dots v_{2k+1}\), \(v_{i_0}=v_{i_k}\) дужине \(2k+1\). Ако се сваки од чворова појављује тачно једном, овај пут је по дефиницији истовремено и контура непарне дужине. У супротном, ако се неки чвор понавља, нека је \(v_{i_a}=v_{i_b}\), \(0\le a < b \le 2k+1\). Тада се затворени пут који разматрамо може поделити на два затворена пута: \(v_{i_0},\dots, v_{i_a}=v_{i_b},\dots, v_{2k+1}\) и \(v_{i_a},\dots, v_{i_b}\). Оба пута су затворена, а један од њих мора да буде непарне дужине, не веће од \(2k-1\) и на основу индуктивне хипотезе садржи контуру непарне дужине.Класе графова
Граф са \(n\) чворова у коме постоји грана између било која два различита чвора назива се комплетан граф (клика) и означава са \(K_n\). Комплемент комплетног графа \(K_n\) назива се празан граф и означава са \(N_n\).
Пример
Графови \(K_1, K_2, K_3, K_4\) и \(K_9\) приказани су на слици.
Комплетан бипартитни граф у ознаци \(K_{a,b}\) представља граф у коме је скуп чворова \(V\) унија два дисјунктна непразна подскупа \(V_1\) и \(V_2\), са \(a\) и \(b\) чворова респективно, а скуп грана садржи гране између свих парова чворова из различитих подскупова тј. \(E=\{ \{v_i, v_j\} : v_i\in V_1, v_j\in V_2\}\).
Ако је \(a=b\), тада сви чворови имају степен \(a\), односно граф \(K_{a,a}\) је \(a\)-регуларан.
За \(a=1\) граф \(K_{1,b}\) се назива звезда граф.
Било који подграф комплетног бипартитног графа назива се бипартитни граф.
Пример
Графови \(K_{4,3}, K_{3,3}, K_{1,4}\), као и један бипартитни граф, приказани су на слици.
Приметимо да је \(K_{1,1}=K_2\).
Теорема
Граф је бипартитни ако и само ако не садржи контуру непарне дужине.
Доказ
(\(\Rightarrow\)): Нека је \(G=(V,E)\) бипартитни граф. Доказаћемо да не садржи контуру непарне дужине. Како је \(G\) бипартитни, на основу дефиниције, његов скуп чворова \(V\) се може поделити на два скупа \(V_1\) и \(V_2\) тако да је \(V=V_1\cup V_2,\,\, V_1\cap V_2 =\emptyset\), a све гране \(e\in E\) су облика \(e=\{v_{i},v_{j}\},\,\, v_{i}\in V_1, v_{j}\in V_2\). Претпоставимо да у графу \(G\) постоји контура \(v_{i_1}, v_{i_2},\dots, v_{i_l}, v_{i_1}\) непарне дужине \(l\). Без губитка општости, претпоставимо да је \(v_{i_1}\in V_1\). Тада имамо да је \(v_{i_2}\in V_2, v_{i_3}\in V_1\), односно да је
\[v_{i_k} \in \begin{cases} V_1, & \text{ ако је $k$ непаран број, } \\ V_2, & \text{ ако је $k$ паран број.} \end{cases}\quad k=1,\dots l\] Како је \(l\) непаран број, имамо да је \(v_{i_l}\in V_1\) и да грана \(\{v_{i_l}, v_{i_1}\}\), која је део посматране контуре, повезује два чвора из скупа \(V_1\), што је у контрадикцији са претпоставком да је \(G\) бипартитни граф. Дакле, претпоставка да у графу \(G\) постоји контура непарне дужине је неодржива, чиме је доказано да граф \(G\) не садржи контуру непарне дужине.
(\(\Leftarrow\)): Претпоставимо сада да у графу \(G\) не постоји контура непарне дужине. Такође претпоставимо, без губитка општости, да је граф \(G=(V,E)\) повезан (у супротном можемо посматрати сваку његову компоненту повезаности). Доказаћемо да је \(G\) бипартитни граф. Нека је \(v\in V\) произвољан чвор. Поделимо скуп чворова \(V\) на два скупа, \(V_1\) који садржи чворове за које је најкраћи пут до чвора \(v\) непарне дужине и \(V_2\) који садржи чворове за које је најкраћи пут до чвора \(v\) парне дужине. Сада имамо да је \(v\in V_2\) и \(V_1\cap V_2= \emptyset\). Претпоставимо да су \(v_{i_1}\in V_1\) и \(v_{i_2}\in V_1\) суседни чворови. Тада постоји затворени пут \(\{v,\dots, v_{i_1},v_{i_2}\dots v\}\) непарне дужине (не обавезно прост). На основу претходне теореме, у графу \(G\) постоји и контура непарне дужине, што је у контрадикцији са полазном претпоставком да у графу \(G\) не постоји контура непарне дужине. Дакле, претпоставка да постоје суседни чворови у скупу \(V_1\) је неодржива. Слично, не постоје два суседна чвора у скупу \(V_2\). Коначно имамо да у графу \(G\) постоје само гране између чворова из \(V_1\) и \(V_2\), тј. да је граф \(G\) бипартитни граф.
Циклични граф са \(n\ge 3\) чворова у ознаци \(O_n\) je повезан граф у коме сваки чвор има степен 2. Дакле, \(O_n\) je \(2\)-регуларан.
Пример
На слици су приказани циклични графови \(O_n\) за \(3\le n \le 6\). Приметимо да је \(O_3=K_3\).
Оријентисан граф
Неоријентисаним графом можемо представити, на пример, једну мрежу сарадње истраживача у којој сваки истраживач представља чвор и повезан је граном са другим истраживачем ако су заједно објавили научни рад. Међутим, за представљање веб мреже где свака страница представља чвор, а гране представљају хиперлинкове између страница, неоријентисан граф често није погодан. Главни разлог је то што се може десити да страница А садржи хиперлинк до странице Б, док страница Б не садржи хиперлинк до странице А. У том случају потребно је назначити да постоји само грана од А до Б, али не и од Б до А, што се може постићи коришћењем уређених, уместо неуређених парова за гране графа.
Оријентисан граф \(G=(V,E)\) се састоји од коначног непразног скупа чворова \(V\) и скупа грана \(E\subseteq V \times V\).
Елементи скупа Е су уређени парови чворова и представљају усмерене гране. За грану \(e=(v_i, v_j)\in E\) чвор \(v_i\) представља почетни чвор, а \(v_j\) завршни чвор. Кажемо да је чвор \(v_i\) суседан ка чвору \(v_j\), односно да је чвор \(v_j\) суседан од чвора \(v_i\). На цртежу графа грани се додаје усмерење од \(v_i\) ка \(v_j\), најчешће једном стрелицом. Оријентисан граф може да садржи и грану облика \((v_i, v_i)\), тј. петљу.
Пример
Оријентисан граф \(G_O\) са скупом чворова \(\{v_1, v_2, v_3, v_4, v_5\}\) и скупом грана \(\{(v_1,v_2), (v_2,v_3), (v_3,v_1), (v_3,v_2), (v_3,v_3), (v_3,v_4), (v_4,v_1), (v_4,v_5), (v_5,v_1), (v_5,v_4) \}\) приказан је на слици.
Излазни степен чвора \(v_i\) у ознаци \(k^{+}(v_i)\) представља број грана којима је чвор \(v_i\) почетни чвор. Са друге стране, улазни степен чвора \(v_i\) у ознаци \(k^{-}(v_i)\) представља број грана којима је чвор \(v_i\) завршни чвор. Чвор чији је улазни степен нула назива се извор, док се чвор чији је излазни степен нула назива понор.
Теорема
У оријентисаном графу \(G=(V,E)\) важи: \[\sum_{v\in V}{k^{-}(v)}=\sum_{v\in V}{k^{+}(v)}=|E|.\]
Доказ
Свака грана \(e=(v_i,v_j)\) оријентисаног графа \(G=(V,E)\) увећава излазни степен почетног чвора \(v_i\) и улазни степен завршног чвора \(v_j\). Дакле, свака грана увећава истовремено суму излазних и суму улазних степена свих чворова за један.Усмерени пут дужине \(k\) од чвора \(v_{i_0}\) до чвора \(v_{i_k}\) у оријентисаном графу \(G=(V,E)\) представља низ облика \[v_{i_0},e_{j_1},v_{i_1},e_{j_2},v_{i_2},e_{j_3},v_{i_3}\dots,v_{i_{k-1}}, e_{j_k},v_{i_k}\] где су \(v_{i_0}, v_{i_1},\dots v_{i_k} \in V\), \(e_{j_1}, e_{j_2},\dots e_{j_k} \in E\) и \(e_{j_t}=(v_{i_{t-1}},v_{i_t})\).
Сваком усмереном графу можемо придружити одговарајући неоријентисан граф тако што све усмерене гране, изузев петљи, посматрамо као неусмерене гране. Носећи граф оријентисаног графа \(G=(V,E)\) је неоријентисан граф \(G^*=(V,E^*)\) где је \(E^*=\{\{v_i,v_j\}: (v_i,v_j)\in E, v_i\neq v_j\}\).
За оријентисан граф кажемо да је повезан ако је његов носећи граф повезан. Често се користи и термин слабо повезан јер нам ова особина не гарантује постојање усмереног пута између било која два чвора у графу. Насупрот томе, за оријентисан граф \(G=(V,E)\) кажемо да је јако повезан ако између било која два различита чвора у графу постоји усмерен пут који их повезује.
Уопштења појма графа
Кроз развој теорије графова уведена су различита уопштења графа као што су мултиграф, хиперграф, тежински граф итд.
Мултиграф \(G=(V,E,f)\) састоји се од скупа чворова \(V\), скупа грана Е и пресликавања \(f:E\rightarrow V\times V\) које свакој грани додељује њен почетни и крајњи чвор.
За разлику од неоријентисаног и оријентисаног графа, мултиграф може да садржи више различитих грана између два чвора. На пример, проблему Кенигсбершких мостова одговара управо један мултиграф.
Хиперграф \(G=(V,E)\) се састоји од скупа чворова \(V\) и скупа грана \(E\subseteq \mathcal{P}(V) \backslash \{\emptyset\}\). Дакле, једна грана хиперграфа може да повезује више чворова. За разлику од графова и мултиграфова, хиперграфови се тешко представљају цртежом, нарочито ако садрже већи број грана.
Пример
Хиперграф \(G_H\) сa чворовима \(\{v_1,v_2,v_3,v_4,v_5,v_6,v_7\}\) и гранама \(\{\{ v_1, v_2, v_3\},\{v_2, v_3\}, \{ v_3, v_5, v_6\}, \{ v_4\}\}\) приказан је на слици.
Сваки од наведених типова графова може се проширити у тежински граф, додавањем тежинске функције \(w:E\rightarrow R\) која свакој грани графа додељује реалан број који представља тежину грану.
Пример
Пример једонг тежинског графа са избором \(s\) и понором \(t\) приказан је на слици.
Овакви графови се јављају у различитим контекстима тако да тежине грана могу представљати трошкове, дужину, капацитет итд. Приликом решавања проблема најкраћег пута у графу или проблема трговачког путника, тежине грана се морају разматрати јер имају кључну улогу у одређивању решења, док се у проблему кластеровања могу, али и не морају разматрати. Више детаља о свим наведеним терминима, уопштењима појма графа, као и различитим проблемима у теорији графова може се наћи у (Cvetković and Milić 1971; Voloshin 2009; Anderson 2001).
Ојлерови и Хамилтонови графови
Материјали за ову тему се могу преузети овде.
Стабла
Материјали за ову тему се могу преузети овде.