Описание на графи

Ето един начин за представяне на социална мрежа:

Чертата между имената на двама души означава, че се познават. Ако между две имена няма черта, то хората не се познават. Връзката "познават се" е в двете посоки; например, тъй като Одри познава Гейл, Гейл познава Одри.

Тази социална мрежа е граф. Имената са върховете на графа. (Ако говориш само за един от върховете, той е връх.) Всяка линия е ребро, което свързва два върха. Означаваме ребро, което свързва $u$‍ и $v$‍ като двойката $(u,v)$‍. Тъй като връзката "познават се" е двустранна, този граф е неориентиран. Неориентирано ребро $(u,v)$‍ е същото като $(v,u)$‍. По-късно ще разгледаме ориентирани графи, в които не е задължително всички връзки между върховете да са двустранни. В един неориентиран граф едно ребро между два върха, като реброто между Одри и Гейл, е инцидентно на два върха и казваме, че върхове, свързани от ребро, са съседни или съседи. Броят ребра, които са инцидентни на един връх, е степента на върха.

Одри и Франк не се познават. Да предположим, че Франк е решил да се запознае с Одри. Как може да стане това? Добре, той познава Емили, която познава Бил, който познава Одри. Казваме, че между Франк и Одри има път от три ребра. Всъщност това е най-прекият път между Франк и Одри. Между тях няма път с по-малко от три ребра. Наричаме пътя между два върха с най-малко ребра най-кратък път. По-долу сме очертали този конкретен най-кратък път:

Когато пътят води от един връх обратно към себе си, това се нарича цикъл. Социалната мрежа съдържа много цикли. Един от тях минава от Одри към Бил и Емили, към Джеф и обратно към Одри. Има и по-кратък цикъл, който съдържа Одри, показан по-долу: Одри към Бил към Гейл и обратно към Одри. Какви други цикли можеш да откриеш?

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

Общият термин, който използваме за числото, което поставяме до реброто, е неговото тегло, а граф, чиито ребра имат тегла, се нарича тегловен граф. В случая с пътната карта, ако искаш да намериш най-краткия път между две локации, търсиш път между два върха с минимална сума на теглото на ребрата по всички пътища между двата върха. Както е при нетегловните графи, наричаме този път най-пряк път. Например най-прекият път в този граф от Ню Йорк до Конкорд минава през Ню Йорк към Ню Хевън към Харфорд към Стърбридж към Уестън към Рийдинг към Конкорд, общо 289 мили.

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

Сега ребрата, означени със стрелки, са насочени и имаме ориентиран граф. Тук посоките показват кои части от екипировката трябва да се поставят преди другите. Например реброто от нагръдника към пуловера показва, че нагръдника трябва да се облече преди пуловера. Числата до върховете показват един от възможните редове, в които може да се облече екипировката, така че бельото идва първо, след това чорапите, след това клинът и т. н., а блокерът е последен. Вероятно забелязваш, че този ориентиран граф няма цикли. Наричаме такъв граф ориентиран ацикличен граф, или оаг. Разбира се, можем да имаме тегловни ориентирани графи, като пътните карти с еднопосочни улици и дължини на улиците.

За насочените ребра използваме различна терминология. Казваме, че едно насочено ребро напуска един връх и влиза в друг. Например едно ориентирано ребро напуска върха на нагръдника и влиза във върха на пуловера. Ако насоченото ребро напуска връх $u$‍ и влиза във връх $v$‍, го отбелязваме с $(u,v)$‍, а редът на върховете в двойката има значение. Броят на ребрата, които напускат един връх, е неговата степен на напускане, а броят на ребрата, които влизат в един връх, е степен на навлизане.

Както можеш да си предствиш неориентираните и ориентираните графи имат много приложения в моделирането на връзки в реалния свят.

Когато работим с графи е полезно да можем да говорим за групи от върхове и групи ребра. Обикновено означаваме набор от върхове с $V$‍, а набор от ребра с $E$‍. Когато представяме граф или изпълняваме алгоритъм върху граф, често искаме да използваме размерите на наборите от върхове и ребра в асимптотична нотация. Например ако искаме да говорим за времето за изпълнение, което е линейно на броя на върховете. Строго погледнато, трябва да кажем, че това време е $\mathrm{\Theta }(|V|)$‍, като използваме нотацията $|\cdot |$‍, за да означим размера на един набор. Но използването на тази нотация на набор в асимптотична нотация е тромаво и затова използваме конвенцията, че асимптотичната нотация и само в асимптотичната нотация, можем да пропуснем нотацията за размер на набора, като разбираме, че говорим за размери на набора. Затова вместо да пишем $\mathrm{\Theta }(|V|)$‍, записваме само $\mathrm{\Theta }(V)$‍. Подобно, вместо да пишем $\mathrm{\Theta }(\lg |E|)$‍, записваме $\mathrm{\Theta }(\lg E)$‍.

Това съдържание е резултат от съвместната дейност на преподавателите по Компютърни науки в Дартмут Thomas Cormen и Devin Balkcom, както и на екипа по компютърни науки на Кан Академия. Съдържанието е лицензирано CC-BY-NC-SA.