Увод в графите

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

Формално определение и стандартни означения: Граф $G$ е наредена двойка от множество от елементи (наречени върхове) $V$ и (мулти)множество от (не)наредени двойки (наречени ребра) $E$ между тях. Накратко: $G(V,E)$. Броят върхове обикновено се бележи с $n$, а броят ребра с $m$.

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

Всеки граф трябва да има поне един връх. Възможно е множеството от ребрата да е празно. Такъв граф наричаме празен граф. Самите върхове обикновено номерираме последователно с числата $1,2,...,n$. Първо ще поговорим за два основни вида графи, които се получават в зависимост от това дали ребрата в графа имат ориентация или не.

ориентирани – както казахме ребрата могат да представляват наредени двойки (при тях редът има значение), т.е. връзката има посока. Например ако графът моделира йерархията във фирма е важно дали връзката е шеф-подчинен или подчинен-шеф. Представяме пример за такъв граф. Тази „картинка“ с кръгчета и насочени отсечки е стандартен начин за изобразяване на граф от човек. Множеството от върховете е $V=\{1,2,3,4,5\}$, а на ребрата - $E=\{(1,2),(1,3),(1,4),(2,5),(3,5)\}$. Забележете, че за всяка двойка в множеството $E$, на първо място седи върхът, от който излиза реброто, а на второ, върхът, в който влиза реброто. В случая графът може да моделира йерархията във фирма, като човекът под номер 1 е най-големият шеф, а например човекът под номер 5 има двама преки началници. Понеже графът е ориентиран, то би могло да съществува и реброто $(2,1) \ne (1,2)$. Но то няма смисъл, ако графът представя йерархията във фирма. Тогава може този граф да показва познанствата на хора (ако приемем, че познанството не е двустранно). Обърнете внимание, че един и същ граф може да изобразява различни неща.
неориентирани – ребрата в тези графи са ненаредени двойки. Забележете, че тук отсечките са ненасочени. Множеството от върховете е отново $V=\{1,2,3,4,5\}$, а $E=\{\{1,2\},\{1,3\},\{1,4\},\{2,5\},\{3,5\}\}$. Начина, по който означаваме ребрата с двуелементни множества е коректен по отношение на смисъла, че няма ориентация, но не е често срещан. Обикновено (и за сходство с ориентирания случай) ребрата отново се означават с кръгли скоби, като се уточнява, че говорим за неориентиран граф. Така че пак ще запишем $E=\{(1,2),(1,3),(2,4),(2,5),(3,5)\}$. Тук за двойките няма значение разположението на върховете, а само кои са.

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

Още един важен тип графи са мултиграфите. В определението ни за граф това присъства като възможност, защото е казано, че множеството $E$ може да е мултимножество. Всъщност това е разликата с обикновените графи - при мултиграфите е възможно да имаме ребра, които на практика не могат да се различат по свързаните върхове. Ето пример за ориентиран мултиграф. Имаме четири ребра $(1,2)$. Забележете, че множеството с върхове в определението е посочено само като множество, така че при върховете няма повторения, защото искаме да различаваме върховете по имената им.

Определение: Степен на връх $v$ в неориентиран граф наричаме броя на ребрата, които излизат от връх $v$, и означаваме с $d(v)$. Формално $d(v)=|\{u \mid (v,u) \in E\}|$ $=|\{u \mid (u,v) \in E\}|$. При ориентирани графи има две понятия за степен - полустепен на входа и полустепен на изхода. Полустепен на входа на връх $v$ наричаме броя влизащи ребра във върха и означаваме с $d^{-}(v)$, а полустепен на изхода наричаме броя излизащи ребра от върха и означаваме с $d^{+}(v)$. Математически: $d^{-}(v)=|\{u \mid (u,v) \in E\}|$ и $d^{+}(v)=|\{u \mid (v,u) \in E\}|$. В случая на ориентиран граф е прието степента на връх да е сумата от двете полустепени, т.е. $d(v)=d^{-}(v)+d^{+}(v)$.

Това понятие на повечето места се ползва за определението изолиран връх - връх $v$ е изолиран $\iff d(v)=0$, т.е. такъв връх не е свързан с други върхове от графа. Тук е момента да кажем, че това определение за изолиран връх пропуска един случай, в който също е удачно да се счита върха за изолиран. В графите има специални ребра наречени примки. Едно ребро е примка, когато е от вида $(v,v)$, т.е. свързва един и същ връх. Ако един връх има само ребра, които са примки, то той продължава да не е свързан с другите върхове. Затова определението за изолиран връх, което ние ще ползваме е следното: връх $v$ е изолиран $\iff |\{u \ne v \mid (u,v) \in E $ или $ (v,u) \in E\}|=0$. Също така ще отбележим, че понятието за степен на връх в неориентиран граф не е много точно, ако в графа може да има примки. Поради ред причини, всяка примка се брои два пъти в степента на съответния връх (за двата си края), т.е. в този случай степента на връх $v$ е $d(v)=|\{u \ne v \mid (v,u) \in E\}|+$ $2*|\{u=v \mid (v,u) \in E\}|$. За да се изяснят тези неща, е даден примерен неориентиран граф с две примки на връх 1 и една примка на връх 2, където за всеки връх е записана степента, като графът може да се променя, а степените се обновяват автоматично.

В много случаи един граф да е мултиграф и да има примки усложнява нещата и при много алгоритми се налагат специфични частни случаи. Затова в повечето задачи се работи с графи, които не са мултиграфи и нямат примки. Такива графи ще наричаме прости. Забележете, че като говорим за прост граф, може да става дума както за ориентиран, така и за неориентиран.

Определение: Един граф $G'(V',E')$ е подграф на $G(V,E)$ $\iff V' \subseteq V$ и $E' \subseteq E$.

Определение: Връх $u$ е съседен на връх $v$ в граф $G \iff (v,u) \in E$. Казваме още, че връх $v$ има за съсед връх $u$. Забележете, че в общия случай ако $u$ е съсед на $v$, то обратното не е задължително изпълнено. Обаче ако $G$ е неориентиран, тогава съседството е двустранно и казваме, че върховете $u$ и $v$ са съседни.

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

Определение: Път в граф наричаме алтернираща поредица от върхове и ребра: $v_1, e_1, v_2, e_2, ..., e_k, v_{k+1}$, където за всяко $1 \le i \le k: e_i=(v_i, v_{i+1})$. Един път представлява цикъл, когато $v_1=v_{k+1}$. Броят ребра $k$, които участват, се нарича дължина на пътя\цикъла. Възможно е път да е съставен само от един връх, така че минималната дължина на път е 0.

Когато не сме в мултиграф, то два върха еднозначно определят реброто между тях. Затова обикновено, когато говорим за път, разглеждаме само последователността от върховете на пътя. Същото важи и за цикли в графи, които не са мултиграфи. Една важна разновидност е така наречените прости пътища. Път е прост, когато всички върхове, които участват в него са различни. От това следва, че и ребрата не се повтарят. Този вид пътища са много важни, защото имат повече свойства и освен това винаги са краен брой. Аналогично имаме и понятие прост цикъл. При тях ще задължим освен върховете да са различни (с изключение на началния и крайния) и всички ребра да са различни. Тук е задължително да включим и ребрата, защото в неориентиран граф при ребро $(1,2)$, цикълът $1,2,1$ не се брои за прост, въпреки че не се повтарят върхове освен 1. Идеята на простия цикъл е да няма тривиални повторения, затова не броим минаването два пъти по едно и също неориентирано ребро за такъв цикъл. Следва интерактивен пример, където за зададени върхове се намира минимален по-дължина прост път, както и цикъл през началния връх.

Както казахме, простите пътища и цикли намират голямо приложение. Затова, когато говорим за пътища и цикли ще имаме предвид, че те са прости освен ако не е уточнено друго допълнително. В неориентиран граф, когато между два върха има път, казваме още, че те са свързани. Едно важно понятие, което ще трябва по-нататък:

Определение: Неориентиран граф $G$ наричаме свързан $\iff$ всеки два върха са свързани.

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

Последно ще разгледаме графи, които са много приложими на практика и често срещани в задачите с графи. Можем да добавим допълнителни описания за всяко ребро, например дължина, време и т.н. Такива графи наричаме претеглени графи. Формална дефиниция е, че добавяме теглова функция $f_w: E \to W$, където $W$ е множество от възможните стойности на теглата. Най-често се работи с естествени числа за тегла на ребрата. За показания пример, графът би бил записан така: $G(V,E,f_w)$, където $f_w$ е функция дефинирана само за следните стойности - $f_w((1,2))=1,$ $f_w((1,3))=2,$ $f_w((1,4))=3,$ $f_w((2,5))=1$ и $f_w((3,5))=2$.

Една от големите разлики в задачите с графи по информатика, в сравнение с тези по математика, е, че, обикновено, самите графи са дадени. Графичното представяне, макар да е много нагледно за хората, е крайно неудобно и нееднозначно за паметта на компютрите. Има разнообразни представяния, тук ще разгледаме най-приложимите от тях.

• матрица на съседство

  Това е едно от най-простите представяния и донякъде по традиция се започва с него, макар и следващото представяне да е най-популярното. Нека първо говорим за непретеглени прости графи. Както се вижда от името, самото представяне е всъщност една матрица с размери $n$x$n$, обикновено се бележи с $A$. Всяка клетка $A[u][v]$ има стойност 1 или 0 в зависимост от това дали имаме ребро $(u,v)$ или не. Когато разглеждаме мултиграфи, то представянето се разширява и във всяка клетка се пише по колко ребра има между съответните два върха - матрицата вече не е задължително булева. Предоставен е пример, където на графа могат да се добавят ребра (включително мултиребра) и да се наблюдава матрицата му на съседство:

  Начален пример

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

  Следва да кажем какви са предимствата на това представяне на графите. Едно от големите предимства, е че лесно се добавят и премахват ребра с константна сложност (...просто се достъпва и променя съответната клетка). Друго предимство пак в тази връзка е, че с константна сложност може да се отговаря на въпроса дали между два върха има ребро. Това представяне има сериозни недостатъци, затова често се избягва. Паметта, която трябва, дори и при малко ребра, винаги е от порядъка на $O(n^2)$. Докато много често графите имат ребра в порядъка само на $O(n)$. Също съществен недостатък е, че ни трябва линейно време (спрямо броя върхове), за да намерим всичките съседи на даден връх.

• списък на съседите

  Идеята на това представяне е за всеки връх да поддържаме списък на съседите му. Понеже обикновено върховете са номерирани с последователни числа от 1 до $n$, то всъщност цялото представяне е масив от списъци - по този начин константно достъпваме списъка на всеки връх. Ако сме в неориентиран граф, то за реброто $(u,v)$, ще сложим връх $v$ в списъка на $u$, както и обратното - връх $u$ в списъка на $v$. При претеглени графи освен да слагаме връх в списък, слагаме и теглото на всяко ребро, обикновено двете заедно като наредена двойка (връх, тегло). Следва интерактивен пример за списъка на съседите на граф.

  Начален пример

  Най-често се използва vector за списъците, така добавянето на ново ребро става с константна сложност. Предимство на това представяне е малката памет - $O(m)$ за запазване на графа, както и това, че можем директно да преглеждаме съседите на даден връх. Ако искаме да поддържаме и премахване на ребра или пък трябва да отговаряме на въпроси дали между два върха има ребро, е удачно вместо vector да използваме set или unordered_set.

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

  Тук поддържаме списък на ребрата (обикновено в задачите с графи, точно така се въвеждат данните за графа - като списък от ребрата му) чрез масив $edges$. Понеже за повечето алгоритми в графи трябва лесно да достъпим съседите на даден връх, към това представяне се добавят два помощни масива - $prev$ и $last$. Първият масив е с размерност броя ребра. Ако схематично имаме $edges[i]=(u,v)$, то $prev[i]$ съдържа индекса на предното ребро, което излиза от връх $u$. Вторият масив $last$ е с размерност броя върхове и $last[v]$ е всъщност индекса на последното ребро, което излиза от връх $v$ в списъка $edges$. За да стане по-ясно е показан интерактивен пример за ориентиран граф и съответната информация, която се записва.

  Начален пример

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

  Един детайл, който се вижда, е, че в началото попълваме $last$ масива с -1. Така можем да разпознаваме краят на списъка на всеки връх, защото за първото ребро, което въведем, $prev$ ще е -1. Това ни позволява и лесното обхождане на съседите на даден връх - като се движим по $prev$ връзките. Също може да се забележи, че не записваме началото на реброто в масива $edges$, а само краищата. Така се лишаваме от възможността по индекс на ребро да знаем върха, от който излиза, но от друга страна обикновено ни трябва само да обхождаме съседите на даден връх. Затова ни е достатъчно да пазим само краищата на ребрата, а така спестяваме и малко памет. При неориентиран граф нещата са малко по-сложни. Най-лесно е да слагаме всяко ребро по два пъти - за всяка посока. Така при въвеждане на ребрата можем да викаме два пъти функцията за добавяне на ребро: $add\_edge(x,y)$ и $add\_edge(y,x)$, като останалата част от кода остава без промяна.

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

Показаните сложности важат и при ориентирани графи, като единствено при тях намаля ползваната памет: за списъка на съседите - на $n+m$, а за списъка на ребрата на - $n+2m$. При списък на съседите са показани оптимални сложности за триене и търсене на ребра, които се постигат, ако се използва unordered_set за списъците, но тази константа е в средния случай (...в лошия случай може да стигне линейна сложност). Освен това в този случай, константата за добавянe също няма да е чиста, както ако се използва vector. Аналогичен е и случая за търсене на ребро при списък на ребрата, където в този случай би било удачно да имаме допълнителен unordered_set само за ребрата.

От таблицата се вижда, че най-добрите две представяния са първите две. Дори може да изглежда, че матрицата на съседство е най-добрата. На практика се работи най-вече с така наречените разредени графи. При тях ребрата не са от порядъка на $n^2$, а на $n$. Понеже тези графи могат да имат голям брой върхове, е неприложимо да се използва матрица на съседство с квадратна памет. Освен това в почти всички алгоритми е нужно бързо да се намират съседите на даден връх, което е бавна операция при матрицата на съседство. Затова като правило, ако имаме неголям брой върхове (например до 1000) и работим с графи, които имат ребра от порядъка на $n^2$, тогава е по-добре да се използва матрица на съседство. Във всички останали случаи се ползва списък на съседите. Остана да кажем какъв е смисълът от третото представяне. Всъщност голямо предимство при тях идва от това, че те не използват някакви по-тежки структури от данни, а само масиви. На практика се оказва, че при списъка на съседите голяма част от забавянето се получава от работата на векторите. Затова много пъти, отново в разредени графи, е по-бързо да се използва списък на ребрата. Техен недостатък е малко по-голямата памет, от която се нуждаят. Освен това макар и те да обхождат съседите един след друг, скаченето в масива на ребрата е по-бавно, отколкото в един вектор със самите съседи. Затова те са по-добри от списъка на съседите при по-малък брой ребра.

След подробното сравнение, заключението е, че в повечето случаи се ползва списък на съседите. Това е и представянето, с което обикновено ще показваме повечето алгоритми в графи. При графи с по-малък брой върхове, но много ребра се ползва матрица на съседство. Списък на ребрата, предвид малко по-сложното писане, се ползва изключително рядко, при сравнително разредени графи с много върхове, когато се опитваме да направим малка оптимизация на константата на даден алгоритъм.