Насочена графа. Дефиниция на насочен граф Пример за използване на матрица на съседство

Ръбът е подредена двойка върхове. Граф, за който е посочена посоката на всяко от неговите ребра, се нарича ориентиран.

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

Можете също да дефинирате връзки на следване или предпочитание с насочени графики.

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

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

Таня Наташа

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

Еднопосочен.

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

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

На езика на теорията на графите тя се формулира по следния начин: при какво условие ръбовете на граф G могат да бъдат ориентирани така, че за всяка двойка негови върхове да има ориентирана верига, която ги свързва?

Ясно е, че всеки такъв граф трябва да бъде свързан, но това не е достатъчно.

Ръбът E = (A,B) ще бъде извикан свързващо ребро, или провлак, ако това е единственият път от А до Б (или обратното).

Свързващият ръб разделя всички върхове на графа на две групи: тези, които могат да бъдат достигнати от A, без да минават покрай E, и тези, които могат да бъдат достигнати от B, без да минават по E. Графът в този случай се състои от две части G 1 и G 2, свързани само с ръб E (фиг. a и a+1).

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

Ако ръбът E i = (A i, B i) не е свързващ, тогава има друг път, свързващ A i и B i и не минаващ по E i. Следователно ще наричаме такова ребро циклично ребро.

Фиг.2 Подвързване Фиг. 2+1 Краен (свързване) Фиг. 2+2 Циклично

ребро ребро

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

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

Можем да докажем тази теорема, като посочим начин за правилно ориентиране на графиката. Да изберем Ж произволен ръб E = (A,B) . Ако д - свързващ ръб, той ще остане двустранен и след това ще бъде възможно да се премести от него А Да се IN и обратно (фиг. 2+3).

фиг.2+3 фиг. 2+4

Ако д е циклично ребро, то е включено в някакъв цикъл С, на който можете да зададете цикличната ориентация (фиг. 2+4).

Да приемем, че вече сме ориентирали част н графика G, така че от всеки връх на графа н можете да отидете до всеки друг негов връх, като спазвате правилата за еднопосочно движение. Тъй като графиката Ж е свързан, тогава или н съответства на цялата графика G, или има ръб E= (A,B), което не принадлежи н , но един от неговите върхове, да речем А , принадлежи н .

Ако д - свързващо ребро AB , тогава ще остане двустранен. Тогава за всеки връх х графика н можете да намерите ориентирана верига Р , свързване Х с А , което означава (през ръба д ), и със IN . Обратно от върха IN през ръба д може да отидеш до А , а след това по приблизителната верига З - от А Да се х (Фигура a+5). Прикачване д Да се з , вече ще получим повечетографика Ж , притежаващи необходимите свойства. Ако ръба E= (A,B) е цикличен, принадлежи към някакъв цикъл СЪС . Задали сме посоката към СЪС от А преди IN и по-нататък СЪС до първия връх д от СЪС собственост на н (фиг. a+6).

ориз. а+5 фиг. а+6

Ще прикрепим всички тези ръбове към н . Позволявам х - произволен връх от н , А U - всеки връх от СЪС ; можете да намерите ориентирана верига Р , принадлежи на н и свързване х с А , а след това заедно СЪС отидете на върха U от СЪС . Връщам се от U можете да вървите заедно СЪС до горе д , а от него - принадлежност н ориентирана верига З - от д Да се х . Следователно насочената графика, получена чрез добавяне към н определени ръбове на цикъла СЪС , също отговаря на необходимите условия. Продължавайки този процес, в крайна сметка ориентираме оригиналната графика по необходимия начин Ж .

Степени на върха.

За насочени графи във всеки връх имаме броя p(A) на изходящите ръбове и броя p * (A) на входящите ръбове. Общ бройръбовете са равни на:

N = p(A 1) + p(A 2) +... + p(A n) = p * (A 1)+p * (A 2)+...+p * (A n)

На разположение Различни видовеграфи, за които степените на върховете имат някои специални свойства. Графиката се нарича хомогенен, ако степените на всички негови върхове са равни на едно и също число r: за всеки връх A:

p(A) = p * (A) = r

Упражнение

Построете хомогенни насочени графи със степен r = 2 с брой върхове n = 2,6,7,8.

ВРЪЗКА.

Релации и графики.

Всякакви математическа системаработи с много обекти или елементи. (Знаци: алгебра, геометрия)

За да изградим математическа теория, ние се нуждаем не само от самите тези елементи, но също така връзкамежду тях. (Примери: за числа a > b; в геометрията - равенство на триъгълници, // прави; в теорията на множествата - равенство и включване на множества.)

Всички тези отношения засягат два обекта, поради което се наричат бинарни отношения, или просто отношения, има и други видове връзки, напр троични отношения, касаещи три обекта. (Например, точка A се намира между точки B и C).

Нека въведем обща дефиниция на бинарното отношение R: аRв - в е в отношението на R към а.

Например връзката a > b означава, че b принадлежи към множеството на всички числа, по-малки от a

Всъщност всеки насочен граф G дефинира някаква релация в своето множество от върхове. Тази връзка може да бъде записана във формата: аGв. Това означава, че графиката има насочено ребро, преминаващо от a към b.

Специални условия.

Нека е дадено някакво отношение R. Ако елемент a е в отношение R със себе си, тогава той съответства на цикъл в графиката

Релация R, за която е изпълнено условието аRв за всяко a, Наречен отразяващ.

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

За всяко отношение R можем да дефинираме обратно съотношение R*, като се има предвид, че aR * in тогава и само ако aR in.

От дефиницията на обратната връзка е ясно, че ако графиката G, съответстваща на R, има ребро (a, b), тогава графиката G *, съответстваща на R *, трябва да има ребро (b, a). С други думи, графиката G * е обратна на G, т.е. графика със същите ребра като G, но противоположно ориентирана.

Отношението се нарича симетричен, ако aRb предполага bRa.

Симетрична релация съответства на графика с неориентирани ръбове; обратно, графика с неориентирани ръбове дефинира някакво симетрично отношение.

Отношението се нарича антисиметричен, ако от аRв следва, че очевидно не се провежда в Rа. Графите на антисиметричните отношения нямат неориентирани или противоположно ориентирани ръбове, свързващи една и съща двойка върхове; освен това върху тях няма бримки, т.е. тези отношения са антирефлексивни.

Съотношение преходно, ако от две условия аRв и вRс следва, че аRc.

Транзитивната релационна графика има следното характерно свойство: за всяка двойка ребра (a, b), (b, c) има изоставащръб, край. Прилагайки това свойство многократно, стигаме до заключението, че ако има ориентиран път на тази графика, преминаващ от върха X до върха Y, тогава има и ориентиран ръб (x, y).

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

Отношения на еквивалентност.

Отношението на еквивалентност, обикновено означавано със символа ~, се характеризира със следните три свойства:

1). Рефлексивност: a ~ a;

2). Симетрия: от a ~ до Þ до ~ a;

3). Преходност: от a ~ в и в ~ c Þ a ~ c.

Всъщност отношението на еквивалентност е обобщение на свойството равенство.

Отношението на еквивалентност въвежда дял в множеството от върхове несвързани класове на еквивалентност.

Нека B i е множеството от върхове на графа на еквивалентност G, еквивалентни на връх i. Тогава всички върхове, принадлежащи на B i, са свързани помежду си с ръбове, т.е. В i е пълна графика G i . Във всеки връх на такъв граф има цикъл Графът G се разделя на набор от свързани компоненти G i .

Частична поръчка.

Поведение частичен ред- това (използвайки примера на комплекти):

1). Рефлексивност: A Ê A

2). Преходност: ако A Ê B и B Ê C Þ A Ê C

3). Идентичност: ако A Ê B и B Ê AÞ A = B

Строги връзки на включване -

1). Антирефлексивност: И ÉA никога не се случва;

2). Преходност: ако A É B и B É C, тогава A É C

Отношение на подреждане(в строгия смисъл) се нарича строго подреждане, a>b, за което в допълнение към предишните условия важи и следното:

Условие за пълнота.За всеки два несъвпадащи елемента b и a винаги е изпълнено едно от двете отношения a>b или b>a.

Обикновено графиката на частично подреждане се изобразява в подредена форма. Тъй като за всеки ръб (a, b) и (b, c) има затварящ ръб (a, c), той може да бъде пропуснат.

ПЛОСКИ ГРАФИКИ.

Условия за равнинни графи.

Графика на Куратовски K 3.3

Графична задача на три къщи и три кладенеца

Куратовски граф К 5

Тези две графики НЕ СА ПЛОСКИ!

Разширяване на графиката- нови върхове бяха поставени на някои ръбове, така че тези ръбове

станаха елементарни вериги, състоящи се от няколко ръба.

Обратна операция, при което разделителните върхове се премахват от елементарни вериги се нарича компресияграфика.

Теорема на Куратовски

За да бъде една графа плоска, е необходимо и достатъчно тя да не съдържа никаква графа вътре в себе си, която може да бъде компресирана в графа K 3,3 или графа K 5.

ФОРМУЛА НА ОЙЛЕР

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

От дефиницията на полигоналните графи следва, че те са свързани. Ние също така изискваме нито един многоъгълник да не лежи в друг. Граничните ръбове на всеки такъв многоъгълник образуват цикъл, понякога наричан минимален цикъл. Частта от равнината, съдържаща се в многоъгълник, се нарича край на графиката. Графиката също съдържа максимален цикъл C 1, заобикаляща цялотографика с всичките й лица. Ще разгледаме частта от равнината, лежаща извън C 1, също като лице на графиката с граница C 1 - безкраенлице F ¥ .

Нека означим с

брой върхове, ръбове и лица пространствен многоъгълник..

Теорема на Ойлер

c - p + g = 2

Доказателство:Формулата е очевидна за многоъгълник с n ръба. Наистина, n върха и n ребра, както и две лица F 1 F ¥

Нека добавим ново ребро към граф с r ребра, като начертаем по лицето F ¥ някаква елементарна верига, свързваща два върха на максималния граф G. Ако тази дъга има r ребра, тогава ще трябва да добавим r - 1 нов връх и един нов ръб. Но след това

c’ - p’ + g’ = (c + g - 1) - (p + g) + (g + 1) = c - p + g (=2!)

по индукционната хипотеза.

Матрични представяния.

1. Матрица на инциденти А.

А). За неориентиран граф матрица на инцидентае матрица, чиито редове съответстват на върхове, а колони на ръбове. Матричен елемент е равен на 1, ако връх е инцидентен на ребро. В противен случай матричният елемент приема стойност 0.

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

2. Матрица от цикли C.

А). За неориентирана графа редовете на матрицата на цикъла съответстват на прости цикли на графиката, а колоните съответстват на нейните ребра. Матричен елемент a ij =1, ако цикълът C i съдържа ребро e j. В противен случай a ij =0.

б). За насочен граф a ij =1, -1 или 0, в зависимост от това дали ориентацията на цикъла C i и дъгата e j е еднаква или противоположна, или дали даденият цикъл изобщо не съдържа дъгата e j.

3. Матрицата на съседство на върховете (или просто матрицата на съседство) V е матрица, чиито редове и колони съответстват на върховете, а матричният елемент a ij в случай на неориентиран граф е равен на броя на ребрата, свързващи върховете i и й. За насочен граф елемент a ij е равен на броя на ребра, насочени от връх i към връх j.

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

1). Рангът (максимален брой линейно независими колони) на матрицата на инцидентност A на свързан граф (насочен и ненасочен) с n върха е равен на (n-1).

2). Рангът на цикличната матрица C на свързан граф с m ребра и n върха е (m-n+1).

Пример за използване на матрицата на съседство.

Следното преобразуване показва, че графите G 1 и G 2 са изоморфни

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

A 2 = PA 1 P", където

P = , или p ij =d p(i),j (символ на Кронекер)

и P" е транспонираната матрица.

Намирането на P матрицата може да бъде трудно.

Изоморфизмът на G 1 и G 2 означава, че A 1 и A 2 имат еднакви собствени стойности. Това условие обаче не е достатъчно (пример по-долу).

Позволявам V, D- произволни множества и V??.Нека означим с V 2набор от декартови квадрати V.

Насочен граф или накратко диграф Жнаречен три ( V, D, ц) : Където ц- някакво преобразуване на множеството D в множеството V 2. Елементи на множества VИ дсе наричат ​​съответно върхове и дъги на орграфа Ж. Набори от върхове и дъги на орграф Жудобно е да се означава с VGИ DGсъответно. Ако f- дъга, тогава ц(f) е подредена двойка ( и v), Където И : v Ј V. Дъга fизлиза от върха Ии отива на върха v; на свой ред ИИ vсе наричат ​​крайни върхове на дъгата f; в бъдеще ще пишем f= (и понякога дори - f = uvосвен ако няма опасност от объркване).

Когато пишете произволен диграф, той обикновено ще бъде представен във формата Ж = (V, D).

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

С всеки диграф Ж = (V, D) естествено свързват графиката Ж о = (В, Е), наречена основа на този диграф. За да се получи основата, е необходимо в диграфа Жзаменете всяка дъга f= ръб e = uv

На фиг. 8 показва диграф и неговата основа

Фигура 8

Диграф Жсе нарича свързан, ако основата му е свързана. Ориентиран маршрут или накратко orroute в диграф Же редуваща се последователност от върхове и дъги

При което

Този маршрут обикновено се нарича (ср О , v T) - маршрут; върхове v оИ v Tсе наричат ​​съответно начален и краен върх на такъв маршрут. Ако v о = v T, тогава маршрутът се нарича затворен. Броят на дъгите, които изграждат маршрута, е дължината на маршрута.

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

Не е трудно да се провери съществуването (ф, в;) - маршрутът гарантира наличието на прост ( и v) - орцепс.

Казват, че върхът vдостъпен от върха И, ако съществува ( и v) orroute. Диграф Же силно свързан или или-свързан, ако някой от неговите върхове е достижим от всеки друг връх. Очевидно силно свързан диграф е свързан; обратното, разбира се, не е вярно.

Графика Жсе нарича ориентируемо, ако е основата на някакъв силно свързан орграф.

Теорема 1.3. Свързана графика Жориентираме тогава и само тогава, когато всеки от неговите ръбове не е мост.

Доказателство. Нека графиката Же основата на диграфа нИ Жсъдържа мост д. След това в нима дъга f=, където и v- краища на реброто д. Очевидно, в нНе ( u, v) - упътвания на маршрута. Следователно, графиката Жне е ориентираемо.

Назад, нека броят Жняма мостове, т.е. всеки ръб на графиката Жсъдържащи се в някакъв цикъл. Тъй като всеки цикъл е ориентируема графика, в графиката Жима максимален ориентируем подграф н. Нека се уверим в това н = Ж. Да приемем, че това равенство не е изпълнено. Поради свързаността на графиката Жима ръб e, инцидентен на върха vот ни да не лежи н. По предположение ръбът e лежи в някакъв цикъл СЪС. Нека означим с Qнабор от ребра на цикли, които не принадлежат на подграфа н. Лесно е да разберете, че като добавите към нвсички ръбове от комплекта Q, отново получаваме ориентируем подграф, противоречащ на избора н.

Позволявам Ж- произволен орграф. Половин градус на резултата degvвърхове vе броят на всички дъги, които имат vкато начало. По същия начин, половин степен на подход degvе броят на всички дъги, за които връх vе краят. Диграф, съдържащ Пвърхове и Tдъги, които ще извикаме ( n, t) - диграф.

Полустепените на резултата и полустепените на подхода са свързани по следния очевиден начин.

Лема 1. Позволявам Ж- произволен ( n, t) - диграф. Тогава

Това твърдение е подобно на лема 1 от раздел. 1.1; често се нарича орлема на ръкостискане.

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

Основни понятия

Формално, диграф D = (V , E) (\displaystyle D=(V,E))се състои от много V (\displaystyle V), чиито елементи се наричат върхове, и комплекти E (\displaystyle E)подредени двойки върхове u , v ∈ V (\displaystyle u,v\in V).

Дъга (u , v) (\displaystyle (u,v)) инцидентенвърхове u (\displaystyle u)И v (\displaystyle v). В същото време те казват, че u (\displaystyle u) - начален връхдъги и v (\displaystyle v) - финален връх.

Свързаност

Маршрутв диграф е редуваща се последователност от върхове и дъга, Тип v 0 (v 0, v 1) v 1 (v 1, v 2) v 2. . . v n (\displaystyle v_(0)\(v_(0),v_(1)\)v_(1)\(v_(1),v_(2)\)v_(2)...v_(n))(върховете могат да се повтарят). Дължина на маршрута- броя на дъгите в него.

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

Веригаима затворен път.

За половин маршрутограничението за посоката на дъгите се премахва и на наполовинаИ полу-верига.

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

Максимум силенподграфът се нарича силен компонент; едностранен компонентИ слаб компонентсе определят по подобен начин.

Кондензациядиграф D (\displaystyle D)наречен орграф, чиито върхове са силни компоненти D (\displaystyle D), а дъгата в D ⋆ (\displaystyle D^(\star ))показва наличието на поне една дъга между върховете, включени в съответните компоненти.

Допълнителни определения

Насочен ацикличен графили хамакима неконтурен диграф.

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

Изображение и свойства на всички диграфи с три възела

Легенда: СЪС- слаб, операционна система- едностранно, СС- силен, н- е насочена графа, Ж- е хамак (ацикличен), T- е турнир

0 дъги	1 дъга	2 дъги	3 дъги	4 дъги	5 дъги	6 дъги
празен, N, G	Н, Г		операционна система	CC	CC	пълен, CC
		OS, N, G	CC, N, T	CC
		C, N, G	OS, N, G, T	операционна система
		C, N, G	операционна система

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

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

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

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

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

Ето някои важни обозначения, използвани в теорията на графите:

• G=(V, E), тук G е графът, V са неговите върхове, а E са неговите ребра;
• |V| – ред (брой върхове);
• |E| – размер на графа (брой ребра).

В нашия случай (фиг. 1) |V|=5, |E|=10;

Когато всеки друг връх е достъпен от който и да е връх, тогава се извиква такъв граф неориентирансвързана графа (фиг. 1). Ако графът е свързан, но това условие не е изпълнено, тогава се извиква такъв граф ориентиранили диграф (фиг. 2).

Насочените и неориентираните графи имат понятието степен на върха. Най-висока степене броят на ръбовете, които го свързват с други върхове. Сумата от всички степени на графика е равна на удвоения брой на всичките му ръбове. За фигура 2 сумата от всички степени е 20.

В диграф, за разлика от неориентиран граф, е възможно да се премести от връх h към връх s без междинни върхове, само когато ребро напусне h и влезе в s, но не и обратното.

Насочените графи имат следната нотация:

G=(V, A), където V са върхове, A са насочени ръбове.

Третият тип графики е смесенграфики (фиг. 3). Те имат както насочени, така и ненасочени ръбове. Формално една смесена графика се записва така: G=(V, E, A), където всяка от буквите в скоби означава същото нещо, което й е било присвоено по-рано.

В графиката на фигура 3 някои дъги са насочени [(e, a), (e, c), (a, b), (c, a), (d, b)], други са ненасочени [(e, d), (e, b), (d, c)…].

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

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

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

Във всяка от графиките, които разгледахме, е възможно да изберете път и освен това повече от един. Пътекае поредица от върхове, всеки от които е свързан със следващия чрез ребро. Ако първият и последният връх съвпадат, тогава такъв път се нарича цикъл. Дължината на пътя се определя от броя на ръбовете, които го съставят. Например на фигура 4.a пътят е последователността [(e), (a), (b), (c)]. Този път е подграф, тъй като дефиницията на последния се прилага за него, а именно: графиката G'=(V', E') е подграф на графиката G=(V, E) само ако V' и E' принадлежат на V, E.

В предишните глави представихме някои основни резултати от теорията на неориентираните графи. Неориентираните графики обаче не са достатъчни, за да опишат някои ситуации. Например, когато се представя модел на движение като графика, чиито ръбове съответстват на улици, на ръбовете трябва да бъде зададена ориентация, за да се посочи допустимата посока на движение. Друг пример е компютърна програма, моделирана от графика, чиито ръбове представляват потока на управление от един набор от инструкции към друг. В това представяне на програмата на краищата също трябва да бъде зададена ориентация, за да се посочи посоката на контролния поток. Друг пример за физическа система, която изисква насочена графика, за да я представи, е електрическа верига. Приложенията на насочени графи и свързаните с тях алгоритми са обсъдени в гл. 11-15.

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

5.1. Основни определения и понятия

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

Насоченият граф се състои от две множества: крайно множество V, чиито елементи се наричат ​​върхове, и крайно множество E, чиито елементи се наричат ​​ръбове или дъги. Всяка дъга е свързана с подредена двойка върхове.

Символите се използват за обозначаване на върхове, а символите се използват за обозначаване на дъги. Ако , тогава те се наричат ​​крайни върхове; в този случай - начален връх, - краен връх. Всички дъги с една двойка начални и крайни върхове се наричат ​​успоредни. Една дъга се нарича цикъл, ако инцидентният връх е нейният начален и краен връх.

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

линии, свързващи точки или кръгове, представляващи техните крайни върхове. Освен това на дъгите се задава ориентация, обозначена със стрелка, сочеща от началния връх към крайния връх.

Например, ако е така, че Their), насочен граф може да бъде представен на фиг. 5.1. В тази графика има успоредни дъги и a е цикъл.

Ориз. 5.1. Насочена графа.

Казва се, че една дъга инцидентна с крайните си върхове. Върховете се наричат ​​съседни, ако са крайни точки на една дъга. Ако дъгите имат общ краен връх, тогава те се наричат ​​съседни.

Казва се, че една дъга започва от началния си връх и завършва в крайния си връх. Един връх се нарича изолиран, ако няма инцидентни дъги.

Степента на един връх е броят на дъгите, инцидентни му. Полустепента на влизане на върха е броят на дъгите, влизащи във V], а полустепента на изтичане е броят на дъгите, излизащи от него. Символите и b" означават минималната половин степен на изходящ и входен график на насочената графа. По същия начин символите означават максималната половин степен на изходящ и входен, съответно.

Множествата на всеки връх се дефинират както следва: . Например в графиката на фиг. 5.1.

Обърнете внимание, че цикълът увеличава полустепените на входа и изхода на този връх. Следното твърдение е следствие от факта, че всяка дъга увеличава с 1 сумата от полустепените на входа и изхода на насочения граф.

Теорема 5.1. В насочен граф с дъги

Сума от полустепените на входа = Сумата от полустепените на изхода = m.

Подграфите и генерираните подграфи на насочен граф се дефинират по същия начин, както в случая на неориентирани графи (раздел 1.2).

Неориентираният граф, получен в резултат на деориентация на дъгите на насочен граф G, се нарича основен неориентиран граф G и се означава с .

Насочен маршрут на насочен граф е такава крайна последователност от върхове

Какво е дъга на графа G. Такъв маршрут обикновено се нарича насочен -път, като началният връх е краен връх на маршрута, а всички останали върхове са вътрешни. Началният и крайният върх на насочен маршрут се наричат ​​негови крайни върхове. Имайте предвид, че дъгите и следователно върховете могат да се появят повече от веднъж в насочен маршрут.

Ориентиран маршрут се нарича отворен, ако крайните му върхове са различни, в противен случай се нарича затворен.

Ориентиран маршрут се нарича ориентирана верига, ако всичките му дъги са различни. Една ориентирана верига е отворена, ако нейните крайни върхове са различни, в противен случай е затворена.

Отворен ориентиран път се нарича ориентиран път, ако всички негови върхове са различни.

Затворена ориентирана верига се нарича ориентиран цикъл или контур, ако нейните върхове, с изключение на крайните, са различни.

Насочената графа се нарича ациклична или безконтурна, ако няма контури. Например насоченият граф на фиг. е ацикличен. 5.2.

Ориз. 5.2. Ациклична насочена графа.

Ориз. 5.3. Силно свързан насочен граф.

Поредица от върхове в насочен граф G се нарича маршрут в G, ако е маршрут в основния неориентиран граф. Например последователността в графа на фиг. 5.2 е маршрут, но не е ориентиран.

Веригата, пътят и цикълът на насочен граф се дефинират по подобен начин.

Насочен граф се нарича свързан, ако основният неориентиран граф е свързан.

Подграф на насочен граф G се нарича компонент на G, ако е компонент на графа

Казват, че върховете на насочен граф G са силно свързани, ако има насочени пътища от и към G. Ако е силно свързано с тогава, очевидно е силно свързано с . Всеки връх е силно свързан със себе си.

Ако един връх е силно свързан с връх, тогава, както е лесно да се види, върхът е силно свързан с връх.Следователно в този случай ние просто казваме, че върховете са силно свързани.

Насоченият граф се нарича силно свързан, ако всички негови върхове са силно свързани. Например графиката на фиг. е силно свързана. 5.3.

Максимален силно свързан подграф на насочен граф G се нарича силно свързан компонент на G. Ако насочен граф е силно свързан, тогава той има единичен силно свързан компонент, а именно себе си.

Помислете за насочена графа. Лесно се вижда, че всеки от неговите върхове принадлежи точно на един силно свързан компонент на графа G. Следователно множествата от върхове на силно свързани компоненти образуват дял на множеството от върхове Y на графа

Ориз. 5.4. Графика и нейната кондензация.

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

Интересно е, че в насочен граф може да има дъги, които не са включени в никакви силно свързани компоненти на графа. Например нито един силно свързан компонент не включва никакви дъги в графиката на фиг. 5.4, ​​а.

По този начин, въпреки че свойството на „силна свързаност“ включва разделяне на набора от върхове на графика, то може да не доведе до разделяне на набора от дъги.

Обединение, пресичане, сбор по модул 2 и други операции върху насочени графи се дефинират по абсолютно същия начин, както в случая на неориентирани графи (раздел 1.5).

Графиката, получена в резултат на свиване на всички дъги от силно свързани компоненти на насочена графа G, се нарича кондензирана графика на G. Кондензацията на графиката, показана на фиг. 5.4, ​​​​а, е показано на фиг. 5.4, ​​б.

Върховете на графа съответстват на силно свързани компоненти на графа G и се наричат ​​съкратени образи на компонентите.

Рангът и цикломатичният номер на насочен граф са същите като тези на съответния неориентиран граф. Това означава, че ако насочен граф G има дъги, върхове и компоненти, тогава рангът и цикломатичният номер на графа G се определят от изразите

Сега нека дефинираме минимално свързани насочени графи и да проучим някои от техните свойства.

Насочен граф G се нарича минимално свързан, ако е силно свързан и премахването на всяка дъга го лишава от свойството силно свързан.

Ориз. 5.5. Минимално свързан насочен граф.

Например графиката, показана на фиг. 1, е минимално свързана. 5.5.

Очевидно минимално свързаните графи не могат да имат успоредни дъги и цикли.

Знаем, че един неориентиран граф е минимално свързан тогава и само ако е дърво (Пример 2.13). Съгласно теорема 2.5 едно дърво има поне два върха от степен 1. Следователно минимално свързаните неориентирани графи имат поне два върха от степен 1.

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