Графи и представяне на графи

Graphs

Какво е граф?

Граф, накратко, е множество от обекти (наричани "върхове" на графа) и връзки между тях (наричани "ребра" в графа).

Както обектите, така и връзките между тях могат да бъдат много различни. В примера с Facebook върховете в графа са хората, докато ребрата са приятелствата. В Google Maps върховете са различните адреси/кръстовища/сгради докато ребрата са улиците. В Amazon върховете са предметите, които се предлагат, а ребрата между два предмета са хора, които са купили и двата.

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

Видове върхове и ребра

Какви са обектите, и какви са връзките между тях, обаче, може да са напълно различни неща в различни графи. Ако забелязахте, в примера с Facebook хората бяха върхове, докато в този с Amazon - бяха ребра. "Човек" обаче носи различен смисъл в двата случая. Докато във Facebook хората са основното, при Amazon предметите са основното - там хората просто носят информация за предметите (ако човек е купил два предмета, най-вероятно друг човек, който е купил един от тях може да иска и другия).

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

Примери за графи и приложение

Примери за на пръв поглед тотално различни неща, които могат да се представят като графи, има много. Ето няколко (включително тези, които вече разгледахме):

• Хора и приятелства между тях;
• Хора и любовни връзки между тях;
• Хора и роднински връзки между тях;
• Населени места и пътища между тях;
• Компютри и интернет кабели между тях;
• Водни резервоари, чешми, и тръби между тях;

Много често ще срещате задачи, за които представянето като граф първоначално не е толкова очевидно, но въпреки това много удобно:

• Числа и това дали едно число се дели на друго;
• Файлове, папки и коя папка съдържа даден файл или друга папка;
• Задачи (ангажименти), които трябва да свършите, зададени чрез своето начално и крайно време (приемайки, че не можете да вършите две задачи едновременно);
• Състояния на кубче на Рубик и възможни негови завъртания;
• Шахматна позиция и възможни ходове (и почти всякакви други стратегически игри);

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

В следствие на огромното си приложение в проблеми от реални живот (вижте края на темата), графите са често срещани и в състезателната информатика. Както ще се убедите и сами, огромен процент от задачите (между 30 и 60 процента), които ще срещнете, са някакъв вид граф. Затова и те са едно от най-основните неща, които си заслужава да научите добре.

Представяне в компютър

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

Друга причина (освен, че често е невъзможно) да представяме графите с числа, вместо с оригиналните обекти, е че така можем да спестим много памет. Нека разгледаме приятелствата във Facebook. Един начин би бил за всеки потребител да се пази масив от стрингове. В първата клетка от този масив би било името на потребителя, а във всяка следваща клетка името на някой от приятелите му. Това, обаче, би било сравнително неудобно, защото аз не съм единственият "Александър" в социалната мрежа. Също така, сред приятелите ми има повече от един "Иван".

Разбира се, бихме могли да пишем целите имена на потребителите, като така ползваме повече пространство. Дори приемайки, че така постигнем еднозначност (което със сигурност не е вярно, тъй като не съм единственият "Александър Георгиев" дори само сред състезателите по информатика, какво да говорим глобално), това пак не е приемлив начин за пазене на приятелствата.
Примерно аз имам над 700 "приятели" във Facebook, което значи, че името ми ще фигурира в над 700 такива масива. Имайки предвид, че то е дълго 19 символа, това прави 13,300 символа из разни масиви - само за мен и връзките ми с разни хора. Умножавайки това по 1,600,000,000 (броя активни потребители на социалната мрежа в момента на писането на статията), това прави над 20 терабайта информация само за това кой е приятел с кого. Които трябва да преровим всеки път, когато трябва да проверим дали човекът X е приятел с човека Y.

Нека сега разгледаме как биха стояли нещата, ако вместо имена, ползваме числа. На всеки потребител ще бъде дадено по едно число, играещо роля на уникален идентификатор (UID). Това е нещо като ЕГН, само че в световен мащаб :). Ако ползваме 32-битови числа за тези UID-та (които са достатъчни за сегашните под 2 милиарда потребители), това ще заема по едва 4 байта на човек. С тази проста оптимизация постигаме почти пет пъти подобрение - вече нужната информация е около четири терабайта, които (макар и трудно) бихме могли да съберем на харддиск.

Поуката е, ползвайте числа!

Малко терминология

Ето дефиниция на най-основните термини за графи.

Връх

"Връх" ("node" или "vertex" на английски) е обект, който представлява някакъв интерес за нас.

Ребро

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

Път

!	В много случаи ще се интересуваме от пътища, в които няма повтарящ се връх. Такъв път се нарича прост път.

"Път" ("path" или "chain" на английски) в граф представлява последователност от едно или повече ребра, които свързват два върха. Например, за да стигнете от София до Варна, обикновено минавате през редица други населени места (да кажем Велико Търново). Така, макар и да няма директно ребро между София и Варна, съществува път между тях (да кажем ползвайки ребрата София -> Ботевград -> Велико Търново -> Шумен -> Варна). Забележете, че пътят може да бъде съставен дори от едно единствено ребро!

Цикъл

"Цикъл" ("cycle" на английски) в граф представлява път (последователност от едно или повече ребра), която започва в даден връх и завършва в същия връх. Например, тъй като Ели познава Крис, Крис познава Станчо, а Станчо познава Ели, то пътят Ели -> Крис -> Станчо -> Ели e цикъл.

Примка

Примка ("loop" на английски) представлява ребро, което води от връх обратно в същия връх (с други думи, цикъл с дължина едно). Пример за примка би бил, да кажем, околовръстен път в някой град - той обикновено започва от една част на града и свършва в друга негова част. От гледна точка на България, той почва в този град и свършва в този град, което е точно ребро от връх до себе си. В примера с графа от числа, които се делят на други числа, всеки "връх" в графа има примка - наистина, всяко число се дели на себе си (не се заяждайте за нулата).

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

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

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

Прост пример би бил граф с пет върха (в случая хора) и кой е приятел с кого. Нека хората са Ели, Крис, Станчо, Пешо и Гошо. Ели, Крис и Станчо се познават, като допълнително Крис познава Пешо, а Станчо и Ели познават Гошо. Този граф е показан визуално на картинката вдясно.

Видове графи според ребрата

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

Претеглени графи

Граф, в който ребрата имат асоциирани числови стойности, наричаме претеглен граф ("weighted graph", на английски). Най-често стойността, асоциирана с дадено ребро, наричаме негова "цена". Както вече казахме, в примера с населените места в България тази стойност би могла да бъде разстоянието между двете населени места. Но тя би могла да бъде (в общия случай) произволно нещо. Например, би могла да показва максималната скорост за движение по пътя. Или в графа с хората и приятелствата би могла да показва колко добре се познават двама души, или колко общи приятели имат.


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

Насочени графи

Ако имаме граф на това кой харесва кого в училището на Ели, то не е задължително ако човекът X е влюбен в човека Y, то и Y да е влюбен в X. Sad but true. Граф, в който някои от ребрата са еднопосочни, се нарича насочен или ориентиран граф ("directed graph", на английски).

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

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

?	Граф, в който имаме както насочени, така и ненасочени ребра, наричаме смесен граф.

За простота обикновено можем да приемем всички графи за "насочени", като, в случая, в който дадено ребро е двупосочно, просто имаме две насочени ребра (по едно за всяка посока).

Насочените ребра се представят визуално като стрелкички, сочещи в посоката, в която е "движението".

Несвързан граф

?

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

Не винаги между всеки два върха в даден граф съществува път. Граф, в които има два върха, между които няма път, се нарича несвързан граф ("disconnected graph", на английски). Пример за несвъразн граф е този с приятелствата във Facebook. В него има хора, с които не сте приятели, нямате общи приятели, нямате приятели на общи приятели и т.н. - тоест няма никаква верига от приятелства, която би стигнала от вас до тях. От друга страна пътната мрежа на градовете в България е пример за свързан, макар и некачествено, граф ("connected graph" на английски), тъй като от всеки град можете да стигнете до всеки друг.

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

!	В темите на informatika.bg ползваме "свързан граф" когато графът е свързан ако считаме ребрата за ненасочени (дори те да са насочени), а "силно-свързан граф" - когато той е свързан дори взимайки в предвид посоката им.

Обикновено в насочени графи вместо "свързан граф" се ползва терминът силно-свързан граф ("strongly-connected graph", на английски). Забележете, че графът може да "изглежда" свързан, но реално да не изпълнява условието, че има път от всеки връх до всеки друг, тъй като е разрешено да се движим по ребрата само в едната посока. Примерът за насочен граф по-горе (кой-кого харесва) е имено такъв - макар и да изглежда свързан, реално няма път от Пешо до Гошо, или пък от Станчо до Пешо (макар и да има от Пешо до Станчо).

Специфични видове графи

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

Дървета

!	Ако графът е несвързан, но отделните му компоненти са дървета, тогава се нарича гора ("forest", на английски).

Ненасочен граф, в който съществува точно един прост път между всеки два върха, наричаме "дърво" ("tree", на английски). Това автоматично налага две неща:

1. Графът е свързан;
2. Графът има N-1 ребра, където N е броят върхове.

Насочен граф, в който съществува един връх, от който има точно един път до всички други върхове, също е дърво. В този случай дървото се нарича кореново ("rooted tree", на английски), а този връх - корен на дървото.

Ациклични графи

!	Често ще срещате абревиетурата "DAG", което е съкращение на английският термин за този тип графи ("Directed Acyclic Graph"). Такива графи често са свързани с динамично програмиране.

Граф, който няма цикли, се нарича ацикличен граф ("acyclic graph", на английски). Напомняме, че цикъл е път, който тръгва от даден връх и свършва пак в него. Ако графът е ненасочен, то това автоматично значи, че е дърво или гора. В насочен граф, обаче, това не е гарантирано. Хората казват, че една картина струва колкото 1000 думи, така че...

Мултиграфи

Граф, в който има повече от едно ребро между два върха, се нарича мултиграф ("multigraph", на английски). Наистина, дори в пътната карта на България може да се намерят двойки населени места, между които има "стар път" и "нов път"; или магистрала и обикновен път.

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

Двуделни графи

Граф, които може да се раздели на две части (обикновено представяни като "лява" и "дясна"), така че всички ребра да свързват само върхове в различните части (но не и два в лявата или два в дясната) се нарича двуделен граф ("bipartite graph", на английски). Такива графи обикновено са нужни за прилагане на специфични алгоритми. Пример, в който се ползват, е bipartite matching, който ще разгледаме в темата за потоци.

"Двуделността" на графа налага редица други характеристики, някои от които са:

• Няма цикъл с нечетна дължина. Нещо повече, един граф е двуделен тогава и само тогава, когато не съдържа цикъл с нечетна дължина.
• Можем да оцветим върховете на графа в два цвята по такъв начин, че да няма два съседни върха с еднакъв цвят. Наистина, ако си представим върховете като "леви" и "десни", можем да оцветим левите в единия цвят, а десните в другия.

Транзитивни графи

?	Транзитивно затваряне на граф се нарича допълване на граф с минимален брой нови ребра, така че той да стане транзитивен.

Граф, в който ако има ребро от A до B и ребро от B до C, то има ребро и от A до C, се нарича транзитивен граф ("transitive graph", на английски). Пример за такъв граф беше даденият по-горе DAG на делителите на числото 48. Тъй като ребрата там представяха делимости, логично, че ако A се дели на B, и B се дели на C, то A се дели на C.

Пълни графи

Това са графи, в които съществуват всички възможни ребра - тоест между всеки два върха има ребро. Обикновено такива графи не са мултиграфи, а също така няма примки, което означава, че броят ребра е точно N * (N - 1) / 2. Допълнително, в най-честия случай такива графи са претеглени. Графът в дясно е пример за пълен граф.

В този тип графи обикновено ребрата не са зададени директно, а съществува някаква функция, с която може да се изчисли тяхната цена. Пример за такъв граф е граф от N точки в равнината (зададени с техните X и Y координати), като "ребро" между всеки две точки представлява правата линия между тях. Интуитивно, цената на реброто е просто неговата дължина.

Планарни графи

Граф, който може да се представи в 2D пространството без никои две ребра да се пресичат, се нарича планарен граф ("planar graph", на английски). Обикновено при тях важат някакви по-ниски граници за сложност на алгоритмите (тоест стандартни алгоритми работят по-бързо, отколкото в произволен граф). Също така съществуват и алгоритми, работещи единствено в планарни графи. Графът в дясно е пример и за планарен граф.

Начини за пазене на графи

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

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

Пазенето на списък на съседите ("adjacency list", на английски) има следната идея. За всеки връх ще пазим масив (по-точно динамичен масив или списък) с всички негови съседи. Това, в най-общия случай, изглежда по следния начин: Тоест пазим numNodes на брой вектора (по един за всеки връх), като във всеки от тези вектори пазим съседите на съответния връх. Този начин на представяне е много удобен (и бърз) за намиране на всички съседи на даден връх, което го прави чудесен избор ако графът е сравнително "рядък" - тоест броят ребра е сравнително малък в сравнение с максималния брой ребра, които може да има в графа (М << N²).

При този модел на представяне на граф, добавянето на ребро е много бързо (O(1)), но изтриването на ребро е O(N). Тъй като, обаче, на състезания рядко се налага да изтриваме ребра (а и бихме могли не да ги изтриваме наистина, ами само да ги маркираме като изтрити и да не ги ползваме), това не е особен недостатък.

Тази структура работи чудесно както ако графът е насочен, така и ако е ненасочен. В насочения вариант добавяме "съсед" само на единия връх, докато в ненасочения вариант реално добавяме две насочени ребра (по едно за всеки връх).

Допълнително, структурата няма проблем да се справи и с мултиграфи, като просто един съсед ще присъства повече от веднъж във вектора на съседните на даден връх.

Ако графът е претеглен, освен "съседите" на всеки връх, трябва да пазим и каква е цената на реброто до всеки от тези съседи. Така бихме ползвали един от следните два варианта: Вторият е малко по-дълъг, но по-четим (затова лично аз предпочитам него).

Съветваме ви да ползвате този начин на представяне, ако броят ребра е под 10-20% от максималния възможен (който, както казахме, е N * (N - 1) / 2). Например, ако имате задача, в която имате 1 ≤ N ≤ 10,000 върха и 1 ≤ M ≤ 100,000 ребра, той би бил чудесен избор.

!

Бихме могли да оптимизираме скоростта на проверка дали два върха са съседни, като държим съседите сортирани и да ползваме двоично търсене, постигайки O(log(N)). За съжаление, това прави строенето на графа със сложност O(M∙log(M)), тъй като се налага да ги сортираме. Допълнително, това не позволява (бързо) вкарване на нови ребра по-нататък при работа на алгоритъма.

Недостатъците тук са, че няма особено бърз начин да проверим дали два върха са съседни (има ребро между тях). За целта трябва да вземем съседите на единия връх и да обходим всички тях, търсейки другия. Така проверката за съседност е O(N).

Този вариант заема O(N + M) памет, където N е броят на върховете, M е броят на ребрата.

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

Представянето на графа чрез матрица на съседство ("adjacency matrix" или "incidence matrix", на английски), има следната идея. Ще пазим квадратна булева матрица, в която клетката graph[X][Y] е true, ако има ребро между върховете X и Y, или false в противен случай. За претеглени графи може матрицата да е от тип int или double като във всяка клетка вместо true/false пазим цената на реброто от X до Y, или някаква невалидна стойност, ако няма ребро. Информацията, в най-общия случай, пазим по следния начин: Очевидно, този вариант също работи добре както за насочени, така и за ненасочени графи. Тъй като graph[X][Y] е различна клетка от graph[Y][X], то можем да пазим различни стойности в тях.

За разлика от списъка на съседите, тук проверката дали има ребро между два върха е константна (както и намирането на цената на това ребро, ако графът е претеглен). Това допълнително позволява, както добавянето, така и премахването на ребро да става много бързо (с O(1)).

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

Недостатъците при това представяне са, че няма бърз начин, по който да намерим съседите на някой връх. За съжаление, трябва да обходим всички N възможни клетки на X-тия ред, за да намерим съседите на връх X, което прави сложността на тази операция O(N).

Допълнително, сравнително трудно е да се справяме с мултиграфи. Вариант е за всяка клетка от таблицата да пазим vector (вместо int), но това би изисквало няколко пъти повече допълнителна памет - ненужно. Добрата новина е, че в повечето случаи реално не се нуждаем да пазим всички ребра - едно от тях е "оптимално" в някакъв смисъл и можем да пазим само него. В други случаи пък ще можем да комбинираме няколко ребра в едно (например ако ребрата пазят капацитет на тръби - можем да си представим, че има само една тръба, с капацитет сбора на всички). Така че това рядко е проблем на практика.

Този вариант заема O(N2) памет, където N е броят върхове в графа. В случая на мултиграф (имплементиран с вектори) сложността става O(N2 + M).

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

Представянето на графа чрез списък на ребрата ("edge list", на английски) ще срещнете много рядко. Тъй като на практика това представяне не намира почти никакво приложение в състезателното програмиране, ще го опишем съвсем накратко.

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

Така постигаме търсене на ребро с O(logM). Намирането на всички съседи на даден връх се свежда до намиране на първия съсед (и после обхождане на следващите ребра, докато "началото" е върха, който ни интересува), което също е относително бързо (O(logM) за намиране на първия, и после колкото на брой ребра има).

Вместо да ползваме търсене всеки път за да намерим къде започват ребрата на даден връх, можем да жертваме O(N) памет и да запазим стартовите индекси на всеки връх.

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

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

Приложения на графи в реалния живот

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

• Връзки между хората във Facebook
• PageRank алгоритъмът на Google търсачката
• Google Maps, Apple Maps, и всяка друга навигационна система, за която можете да се сетите
• Почти всички recommender systems: повечето онлайн магазини (например Amazon), реклами, онлайн радиа (например Spotify, Pandora и YouTube)
• Движението на единиците в StarCraft, DotA, и всяка друга стратегическа игра, за която можете да се сетите
• Силно приложение в компилаторите (вкл. нa C++)
• Garbage Collection в езици като Java и Python
• Приложение в медицината (съчетаване на пациенти и органи за трансплантация)
• Интернет (трафикът намира най-късия път от вашия компютър до сървъра ползвайки алгоритъма на Дейкстра)
• Операционните системи (файлови системи, deadlock detection)
• График на автобуси, влакове и самолетни полети

Задачи за тренировка

Задачи ще дадем в следващите теми, когато разглеждаме конкретни алгоритми за работа в графи, като например:

• търсене в дълбочина;
• търсене в ширина;
• алгоритъм на Дейкстра;
• минимално покриващо дърво;
• и други.

Референции

1. Graphs (discrete mathematics) (en.wikipedia.org)
2. Алгоритми в графи. Основни алгоритми (автор Красимир Манев) - хубава книга на български език, която разглежда в детайли графите и различни графови алгоритми (на по-високо, по-скоро университетско, ниво)
3. Great projects, implemented using graph theory (quora.com)

предишна тема

версия за печат

следваща тема