Елементи 

Диграфи и бинарни отношения. Коефициентът на достижимост на върховете на орграф

Разглеждат се въпросите за достижимостта на орграфи и методите за намиране на матрици на достижимост и противопостижимост. Разглежда се матричен метод за намиране на броя на пътищата между всички върхове на графа, както и за намиране на набора от върхове, включени в пътя между двойка върхове. Целта на лекцията: Да се ​​даде представа за постижимостта и контрадостижимостта и как да ги намерите

Достижимост и противопоставимост

Задачи, в които се използва понятието достъпност, доста от.

Ето един от тях. Графикаможе да бъде модел на някаква организация, в която хората са представени от върхове, а дъгите интерпретират комуникационните канали. Когато се разглежда такъв модел, може да се запита дали информация от едно лице i може да бъде прехвърлена на друго лице j, т.е. има ли път, който минава от върхове i до върхове j. Ако такъв път съществува, тогава казваме, че върховете j постижимоот върхове i . Човек може да се интересува от достижимостта на върхове j от върхове i само по пътища, чиито дължини не надвишават дадена стойност или чиято дължина е по-малка от най-големия брой върхове в графика и т.н. на задачата.

Достижимостта в графиката се описва с матрицата на достижимостта R=, i, j=1, 2, ... n, където n е броят на върховете на графа и всеки елемент е дефиниран, както следва:

r ij =1, ако върховете j са достъпни от x i ,

r ij =0, в противен случай.

Множеството от върхове R(x i) на графа G, достижимо от даден връх x i , се състои от елементи x i, за които (i, j)-ти елемент в матрицата на достижимостта е равен на 1. Очевидно всички диагонали елементи в матрицата R са равни на 1, тъй като всеки връх е достъпен от себе си по път с дължина 0. Тъй като директното отображение от първи ред Г +1 (x i) е множеството от такива върхове x j, които са достъпни от x i, използвайки пътеки с дължина 1, тогава множеството Г + (Г +1 (x i)) = Г +2 (x i) се състои от върхове, достъпни от x i, използвайки пътища с дължина 2. По същия начин, r + p (x i) е множеството от върхове които са достъпни от x i, като се използват пътища с дължина p.

Тъй като всеки връх на графа, който е достижим от x i, трябва да бъде достигнат с помощта на път (или пътеки) с дължина 0 или 1, или 2, ... или p, наборът от върхове, достъпни за връх x i, може да бъде представен като

R (x i) = ( x i ) G +1 (x i) G +2 (x i) ... G + p (x i).

Както можете да видите, наборът от достижими върхове R(x i) е пряко транзитивно затваряне на върха x i , т.е. R(x i) = T + (x i). Следователно, за да построим матрицата на достижимостта, намираме достижими множества R(x i) за всички върхове x i X. Поставяне на r ij =1, ако x j R(x i) и r ij =0 в противен случай.

Ориз. 4.1. Достижимост в графиката: а - графика; b – матрица на съседство; c – матрица на достижимост; r е матрицата за контрадостижимост.

За графиката, показана на фиг. 4.1, а, достъпни комплектиса разположени, както следва:

R (x 1) = ( x 1 ) ( x 2 , x 5 ) ( x 2 , x 4 , x 5 ) ( x 2 , x 4 , x 5 ) = ( x 1 , x 2 , x 4 , x 5 ) ),

R (x 2) = ( x 2 ) ( x 2 , x 4 ) ( x 2 , x 4 , x 5 ) ( x 2 , x 4 , x 5 ) = ( x 2 , x 4 , x 5 ),

R (x 3) = ( x 3 ) ( x 4 ) ( x 5 ) ( x 5 ) = ( x 3 , x 4 , x 5 ),

R (x 4) = ( x 4 ) ( x 5 ) ( x 5 ) = ( x 4 , x 5 ),

R (x 5) = ( x 5 )( x 5 ) = ( x 5 ),

R (x 6) = ( x 6 )( x 3 , x 7 ) ( x 4 , x 6 ) ( x 3 , x 5 , x 7 ) ( x 4 , x 5 , x 6 ) = ( x 3 , x 4, x 5, x 6, x 7),

R (x 7) = ( x 7 )( x 4 , x 6 )( x 3 , x 5 , x 7 )( x 4 , x 5 , x 6 ) = ( x 3 , x 4 , x 5 , x 6 , x 7).

Матрица на достижимост има формата, както е показано на фиг. 4.1, c. Матрица на достижимостможе да се изгради според матрица на съседство(фиг. 4.1b), образувайки множество T + (x i) за всеки връх x i .

Матрица за противопоставимост Q = [ q ij ],i, j =1, 2, ... n, където n е броят на върховете на графа, се дефинира, както следва:

q ij =1, ако от връх x j е възможно да се достигне връх x i ,

q ij =0, в противен случай.

противопостижимомножеството Q (x i) е множество от върхове, така че от всеки връх на това множество е възможно да се достигне до върха x i . Подобно на конструирането на достижимото множество R (x i), можем да напишем израз за Q (x i):

Q (x i) = ( x i ) Г -1 (x i) Г - 2(x i) ... Г -p (x i).

По този начин е ясно, че Q (x i) не е нищо повече от обратното транзитивно затваряне на върха x i, т.е. Q (x i) = T - (x i). От дефинициите е очевидно, че колоната x i на матрицата Q (в която q ij =1, ако x j Q (x i), и q ij =0 в противен случай) съвпада с реда x i на матрицата R, т.е. Q = R T , където R T е матрицата, транспонирана към матрица на достижимостР.

Матрица за противопоставимостпоказано на фиг. 4.1, g.

Трябва да се отбележи, че тъй като всички елементи на матриците R и Q са равни на 1 или 0, всеки ред може да се съхранява в двоична форма, спестявайки разходи за компютърна памет. Матриците R и Q са удобни за обработка на компютър, тъй като от изчислителна гледна точка основните операции са високоскоростни логически операции.

Намиране на набора от върхове, включени в пътя

Ако трябва да знаете за върховете на графа, включени в тези пътища, тогава трябва да запомните определенията за директни и обратни транзитивни затваряния. Тъй като T + (x i) е множеството от върхове, до които има пътища от върха x i , а T - (x j) е наборът от върхове, от които има пътища до x j , то T + (x i) T - (x j ) е множеството от върхове, всеки от които принадлежи на поне един път, минаващ от x i до x j. Тези върхове се наричат ​​съществени или интегрални по отношение на двата крайни върха x i и x j . Всички останали върхове на графа се наричат ​​незначителни или излишни, тъй като тяхното премахване не засяга пътищата от x i до x j .

Ориз. 4.2. орграф

Така че за графиката на фиг. 4.2 намирането на върховете, включени в пътя, например от връх x 2 до върхове 4, се свежда до намиране на T + (x 2) \u003d ( x 2, x 3, x 4, x 5, x 6 ),

T - (x 4) \u003d ( x 1, x 2, x 3, x 4, x 5) и техните пресечни точки T + (x 2) T - (x 4) = ( x 2, x 3, x 4, х 5).

Матричен метод за намиране на пътища в графики

Матрицата на съседство напълно дефинира структурата на графиката. Нека квадратираме матрицата на съседство според правилата на математиката. Всеки елемент от матрицата A 2 се определя по формулата

a (2) ik = n j=1 a ij a jk

Членът във формулата е равен на 1, ако и само ако и двете числа a ij и a jk са равни на 1, в противен случай той е равен на 0. Тъй като равенството a ij = a jk = 1 предполага съществуването на път с дължина 2 от връх x i до върхове k, преминаващи през връх x j , тогава (i -ти, k-ти) елемент на матрицата A 2 е равен на броя на пътищата с дължина 2, минаващи от x i до k .

Таблица 4.1а показва матрицата на съседство на графиката, показана на фиг. 4.2. Резултатът от квадратурата на матрицата на съседство A 2 е показан в Таблица 4.1b.

Така че "1", стоящ в пресечната точка на втория ред и четвъртата колона, показва съществуването на един път с дължина 2 от връх x 2 до върхове 4 . Наистина, както виждаме в колонана фиг. 4.2, има такъв път: a 6 , a 5 . "2" в матрица A 2 показва съществуването на два пътя с дължина 2 от върхове 3 до върхове 6: a 8 , a 4 и a 10 , a 3 .

По същия начин, за матрицата на съседство, повдигната на трета степен A 3 (Таблица 4.1в), a (3) ik е равно на броя на пътищата с дължина 3, минаващи от x i до x k . От четвъртия ред на матрица A 3 може да се види, че има пътища с дължина 3: един от x 4 в 4 (a 9 , a 8 , a 5), ​​един от x 4 in

x 5 (a 9, a 10, a 6) и два пътя от x 4 в 6 (a 9, a 10, a 3 и a 9, a 8, a 4). Матрица А 4 показва съществуването на пътища с дължина 4 (Таблица 4.1d).

По този начин, ако p ik е елемент от матрицата A p, тогава p ik е равен на броя на пътищата (не е задължително или вериги или прости или вериги) с дължина p, минаващи от x i до x k .

Графика за достъпност

Един от първите въпроси, които възникват при изследването на графите, е въпросът за съществуването на пътища между дадени или всички двойки върхове. Отговорът на този въпрос е горното отношение на достижимост във върховете на графа G=(V,E): върхът w е достижим от върха v, ако v = w или има път от v до w в G. С други думи, отношението на достижимостта е рефлексивното и транзитивно затваряне на релацията E. За неориентирани графи тази връзка също е симетрична и следователно е релация на еквивалентност на множеството върхове V. В неориентирана графа класовете на еквивалентност на достижимостта са наречени свързани компоненти. За насочени графи по принцип достижимостта не трябва да е симетрична връзка. Взаимната достъпност е симетрична.

Определение 9.8.Върховете v и w на насочен граф G=(V,E) се казва, че са взаимнодостъпни, ако G има път от v до w и път от w до v.

Ясно е, че връзката на взаимната достижимост е рефлексивна, симетрична и транзитивна и следователно еквивалентност на множеството върхове на графа. Класовете на еквивалентност по отношение на взаимната достъпност се наричат ​​силно свързани компоненти или двойно свързани компонентиграфика.

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

Определение 9.9.Нека G=(V,E) е ориентиран граф. Графата на достижимост G * =(V,E *) за G има същия набор от върхове V и следния набор от ръбове E * =( (u, v) | в графа G, върхът v е достижим от върха u).

Пример 9.3.Разгледайте графиката G от пример 9.2.

Ориз. 9.2.Граф Г

След това можем да проверим, че графиката на достижимост G* за G изглежда така (новите ръбове на цикъла във всеки от върховете 1-5 не са показани):

Ориз. 9.3.Брой G*

Как може да се построи графика G * от графика G? Един от начините е да се определи за всеки връх на графа G множеството от върхове, достижими от него, като последователно се добавят към него върховете, достигани от него по пътища с дължина 0, 1, 2 и т.н.

Ще разгледаме друг метод, базиран на използването на матрицата на съседство A G на графа G и булеви операции. Нека множеството от върхове V=(v 1 , … , v n ). Тогава матрицата A G е n × n булева матрица.

По-долу, за да запазим приликата с обичайните операции с матрици, ще използваме "аритметичната" нотация за булевите операции: ще означаваме дизюнкцията с +, а конюнкцията - с ·.

Означете с E n идентичната матрица с размер n × n. Нека сложим . Нека нашата процедура за конструиране на G * се основава на следното твърдение.

Лема 9.2.Позволявам . Тогава

Доказателствонека извършим чрез индукция по k.

Основа.За k=0 и k=1 твърдението е вярно по дефиниция и .

индукционна стъпка.Нека лемата е валидна за k. Нека покажем, че то остава валидно и за k + 1. По дефиниция имаме:

Да приемем, че в графиката G от v i до v j има път с дължина k+1. Помислете за най-краткия от тези пътища. Ако дължината му е k, то според индукционната хипотеза a_(ij)^((k))=1. В допълнение, a jj (1) =1. Следователно a ij (k) a jj (1) =1 и a ij (k+1) =1. Ако дължината на най-краткия път от v i до v j е равна на k+1, тогава нека v r е неговият предпоследен връх. Тогава от v i до v r има път с дължина k и, според хипотезата на индукцията, a ir (k) =1. Тъй като (v r ,v j) E, то a_(rj)^((1))=1. Следователно a ir (k) a rj (1) =1 и a ij (k+1) =1.

Обратно, ако a ij (k+1) =1, тогава за поне едно r сборът a ir (k) a rj (1) е равен на 1. Ако това е r=j, тогава a ij (k) = 1 и според индуктивната хипотеза G има път от v i до v j с дължина k. Ако r j, тогава a ir (k) =1 и a rj (1) =1. Това означава, че G има път от v i до v r с дължина k и ръб (v r ,v j) E. Комбинирайки ги, получаваме път от v i до v j с дължина k+1.

От леми 9.1 и 9.2 директно получаваме

Последствие 1.Нека G=(V,E) е насочен граф с n върха и G * неговият граф на достижимост. Тогава A_(G*) = . Доказателство.Лема 5.1 предполага, че ако G има път от u до v u, то има и прост път от u до v с дължина n-1. И според лема 5.2 всички такива пътища са представени в матрицата.

По този начин процедурата за изграждане на матрицата на съседство A G* на графиката на достижимостта за G се свежда до издигане на матрицата до степен на n-1. Нека направим някои забележки, за да опростим тази процедура.

където k е най-малкото число, така че 2 k n.

такова r е намерено, че a ir = 1 и a rj =1, тогава цялата сума a ij (2) =1. Следователно останалите термини могат да бъдат игнорирани.

Пример 9.3.Нека разгледаме като пример изчисляването на матрицата на графика на достижимост A G* за графиката G, представена в фиг.9.2. В такъв случай

Тъй като G има 6 върха, тогава . Нека изчислим тази матрица:

и (последното равенство е лесно за проверка). По този начин,

Както можете да видите, тази матрица наистина дефинира графиката, показана на фиг.9.3.

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

По аналогия с графиката на достижимостта, ние дефинираме графика със силна достижимост.

Определение 9.10.Нека G=(V,E) е ориентиран граф. Силно достижимият граф G * * =(V,E * *) за G има същия набор от върхове V и следния набор от ръбове E * * =( (u, v) | в G, върховете v и u са взаимно постижимо).

От матрицата на графиката на достижимостта е лесно да се построи матрицата на графиката на силната достижимост. Всъщност от дефинициите за достижимост и силна достижимост следва директно, че за всички двойки (i,j), 1 i,j n, стойността на елемента е равна на 1, ако и само ако и двата елемента A G* (i, j) и A G* (j, i) са равни на 1, т.е.

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

    Нека поставим в компонента K 1 върха v 1 и всички върхове v j, така че A_(G_*^*)(1,j) = 1.

    Нека компонентите K 1 , …, K i и v k вече са изградени - това е върхът с минималния брой, който все още не е включен в компонентите. След това поставяме в компонента K_(i+1) върха v k и всички такива върхове v j ,

    че A_(G_*^*)(k,j) = 1.

Повторете стъпка (2), докато всички върхове се разпределят между компонентите.

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

Използвайки описаната по-горе процедура, откриваме, че върховете на графа G са разделени на 4 силно свързани компонента: K 1 = (v 1 , v 2 , v 3 ), \ K 2 =( v 4 ), \ K 3 = ( v 5 ), \ K 4 =( v 6 ). Върху множеството от силно свързани компоненти ние също така дефинираме отношението на достижимост.

Определение 9.11.Нека K и K" са силно свързани компоненти на граф G. Компонентата K достъпно откомпоненти K^\прости, ако K= K" или има два върха u K и v K" такива, че u е достижимо от v. К строго постижимо от K^\прост, ако K K" и K е достижимо от K". Компонентът K се нарича минимумако не е строго достъпен от нито един компонент.

Тъй като всички върхове в един компонент са взаимно достижими, лесно е да се види, че отношенията на достижимост и стриктна достижимост върху компонентите не зависят от избора на върхове u K и v K".

Следната характеристика на строгата достъпност се извежда лесно от определението.

Лема 9.3.Връзката на строгата достижимост е отношение на частичен ред, т.е. той е антирефлексивен, антисиметричен и преходен.

Тази връзка може да бъде представена като насочен граф, чиито върхове са компонентите, а ръбът (K, K) означава, че K е строго достижимо от K". На ориз. 9.4тази графика на компонентите е показана за графиката G, разгледана по-горе.

Ориз. 9.4.

В този случай има един минимален компонент K 2 .

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

Определение 9.12.Нека G=(V,E) е ориентиран граф. Подмножеството от върхове W V се нарича генеративна, ако от върховете на W е възможно да се достигне до всеки връх на графа. Подмножество от върхове W V се нарича графична основа, ако генерира, но нито едно от собствените му подмножества не генерира.

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

Теорема 9.1.Нека G=(V,E) е ориентиран граф. Подмножество от върхове W V е основа на G тогава и само ако съдържа един връх от всяка минимална силно свързана компонента на G и не съдържа други върхове.

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

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

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

    Намерете всички силно свързани компоненти на G.

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

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

Пример 9.5.Ние дефинираме всички бази на насочения граф G, показан в фиг.9.5.

Ориз. 9.5.Граф Г

На първия етап намираме силно свързаните компоненти на G:

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

Ориз. 9.6.Графа на връзката на достижимостта върху G компоненти

Определяме минималните компоненти: K 2 = ( b ), K 4 =( d, e, f, g) и K 7 = ( r).

Накрая изброяваме всичките четири бази на G: B 1 = ( b, d, r), B 2 = ( b, e, r), B 3 = ( b, f, r) и B 1 = ( b, g , r) .

Задачи

Проблем 9.1.Докажете, че сборът от степените на всички върхове на произволно ориентиран граф е четен.

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

Проблем 9.2.Избройте всички неизоморфни неориентирани графи, които имат най-много четири върха.

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

Проблем 9.4.Докажете, че един неориентиран свързан граф с n върха

    съдържа най-малко n-1 ръбове,

    ако съдържа повече от n-1 ръбове, тогава има поне един цикъл.

Проблем 9.5.Докажете, че във всяка група от 6 души има трима познати по двойки или трима непознати по двойки.

Проблем 9.6.Докажете, че неориентираният граф G=(V,E) е свързан ↔ за всяко дял V= V 1 V 2 с непразни V 1 и V 2 има ръб, свързващ V 1 с V 2 .

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

Проблем 9.8.Нека G=(V,E) е неориентиран граф с |E|< |V|-1. Докажите, что тогда G несвязный граф.

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

Проблем 9.10.Нека неориентиран граф без цикли G=(V,E) има k свързани компоненти. Докажи го тогава

Проблем 9.11.Определете за какво служи графика за достигане

    граф с n върха и празен набор от ребра;

    графика с n върха: V= (v 1 ,… , v n ), чиито ръбове образуват цикъл:

Проблем 9.12.Изчислете матрицата на графика на достижимостта за графика

и построете съответната графика на достижимостта. Намерете всички основи на графика G.

Проблем 9.13.Изграждане за дадено на ориз. 9.7насочен граф G 1 =(V,E) неговата матрица на съседство A G1 , матрица на инцидентите B G1 и списъци на съседство. Изчислете матрицата на достижимостта A G1* и построете съответната графика на достижимост G 1 * .

Ориз. 9.7.

Ненасочени и ориентирани дървета

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

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

Определение 10.2.Насочен граф G=(V,E) се нарича (насочено) дърво, ако

На ориз. 10.1са показани примери за ненасочено дърво G 1 и насочено дърво G 2. Обърнете внимание, че дървото G 2 се получава от G 1, като се избере връх c като корен и се ориентират всички ръбове в посока "далеч от корена".

Ориз. 10.1.Ненасочени и насочени дървета

Това не е случайно. Докажете си следното твърдение за връзката между ненасочени и насочени дървета.

Лема 10.1.Ако в някое неориентирано дърво G=(V,E) изберем произволен връх v V като корен и ориентираме всички ръбове в посока "от корена", т.е. направи v началото на всички ръбове, инцидентни с него, върховете, съседни на v - начала на всички все още ненасочени ръбове, инцидентни на v и т.н., тогава полученият насочен граф G" ще бъде насочено дърво.

Ненасочените и насочени дървета имат много еквивалентни характеристики.

Теорема 10.1.Нека G=(V,E) е неориентиран граф. Тогава следните условия са еквивалентни.

    G е дърво.

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

    G е свързан, но когато някой ръб се отстрани от E, той престава да бъде свързан.

    G е свързан и |E| = |V| -един.

    G е ацикличен и |E| = |V| -един.

    G е ацикличен, но добавянето на всяко ръбо към E генерира цикъл.

Доказателство(1) (2): Ако някои два върха в G бяха свързани с два пътя, тогава очевидно би имало цикъл в G. Но това противоречи на определението за дърво в (1).

(2) (3): Ако G е свързан, но E остава свързан, когато някакъв ръб (u,v) бъде премахнат, тогава има път между u и v, който не съдържа този ръб. Но тогава G има поне два пътя, свързващи u и v, което противоречи на условие (2).

(3) (4): Предоставя се на читателя (виж проблем 9.4).

(4) (5): Ако G съдържа цикъл и е свързан, тогава при премахване на който и да е ръб от цикъла, свързаността не трябва да се прекъсва, но ръбовете остават |E|= V -2, а по задача 9.4(a ), свързаният граф трябва да има поне V -1 ребра. Полученото противоречие показва, че в G няма цикли и условие (5) е изпълнено.

(5) (6): Да предположим, че добавянето на ръб (u,v) към E не води до цикъл. Тогава върховете u и v в G са в различни свързани компоненти. Тъй като |E|= V -1, то в една от тези компоненти, нека е (V 1 ,E 1), броят на ръбовете и броят на върховете са еднакви: |E 1 |=|V 1 |. Но тогава той съдържа цикъл (виж проблем 9.4(b)), което противоречи на факта, че G е ацикличен.

(6) (1): Ако G не беше свързан, тогава ще има два върха u и v от различни свързани компоненти. Тогава добавянето на ръба (u,v) към E няма да доведе до появата на цикъл, което противоречи на (6). Следователно G е свързано и е дърво.

За насочени дървета често е удобно да се използва следната индуктивна дефиниция.

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

Ориз. 10.2илюстрира това определение.

Ориз. 10.2.Индуктивно определение на насочени дървета

Теорема 10.2.Определенията за насочени дървета 10.2 и 10.3 са еквивалентни.

ДоказателствоНека графиката G=(V,E) удовлетворява условията на дефиниция 10.2. Нека покажем чрез индукция по броя на върховете |V|, че .

Ако |V|=1, то единственият връх v V е коренът на дървото по свойство (1), т.е. в тази графика няма ръбове: E = . Тогава .

Да предположим, че всеки граф с n върха, който отговаря на дефиниция 10.2, е включен в . Нека графът G=(V,E) с (n+1)-ти връх удовлетворява условията на дефиниция 10.2. По условие (1) той има коренен връх r 0 . Нека k ребра излизат от r 0 и водят до върхове r 1 , … , r k (k 1). Означете с G i ,(i=1, …, k) графиката, която включва върховете V i =( v V|v \textit( достъпно от )r i ) и свързващите ги ръбове E i E. Лесно е да се види че G i удовлетворява условията на дефиницията 10.2. Всъщност r i не съдържа ръбове, т.е. този връх е корен на G i . Всеки от останалите върхове от V i има едно ръбче, точно както G . Ако v V i , то е достижимо от корена r i по дефиницията на графа G i . Тъй като |V i | n, тогава по индуктивната хипотеза. Тогава графиката G се получава по индуктивното правило (2) от дефиниция 10.3 от дърветата G 1 , ..., G k и следователно принадлежи към класа .

⇐ Ако някаква графика G=(V,E) принадлежи към класа, то изпълнението на условията (1)-(3) от дефиниция 10.2 за нея може лесно да се установи чрез индукция по дефиниция 10.2. Оставяме това на читателя като упражнение.

Има богата терминология, свързана с ориентирани дървета, която идва от два източника: ботаника и областта на семейните отношения.

Коренът е единственият връх, който няма ръбове, листата са върхове, които нямат ръбове. Пътят от корена до листата се нарича клон на дървото. Височината на едно дърво е максималната дължина на клоните му. Дълбочината на един връх е дължината на пътя от корена до този връх. За връх v V подграфът на дървото T=(V,E), който включва всички върхове, достъпни от v и свързващите ги ръбове от E, образува поддърво T v на дървото T с корен v (вж. Задача 10.3 ). Височината на v е височината на дървото T v. Графа, която е обединение от няколко непресичащи се дървета, се нарича гора.

Ако ребро води от връх v до връх w, тогава v се извиква баща w и w - син v (напоследък в англоезичната литература се използва асексуална двойка термини: родител - дете). От дефиницията на дървото директно следва, че всеки връх има уникален баща освен корена. Ако пътят води от връх v до връх w, тогава v се нарича предшественик на w, а w се нарича потомък на v. Върховете, които имат общ баща, се наричат братяили сестри.

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


компютър технология, по-специално програма ... 2009 на годинатаОсновното училище е експериментален обект Навъвеждането на федералната състояние ...

  • МОНИТОРИНГ МЕДИИ Модернизация на професионалното образование март – август 2011г

    Резюме

    Юнайтед състояниеизпити" Наизбор": информационен компютъртехнология, биология и литература. Между другото, в това годинаИЗПОЛЗВАЙТЕ... въпрос„За резултатите от изпълнението програмиразвитие на националните изследователски университети в 2009 -2010 години". ...

  • ПРОГРАМА ЗА СТРАТЕГИЧЕСКО РАЗВИТИЕ Твер 2011г

    Програма

    AT 2009 година. Структурни промени, наблюдавани през 2010 г годинаНакъм 2009 , ... Професионално – ориентираначужд език”, „Съвременна обуч технология". Във всеки програмамодул за напреднало обучение " състояние ...

    • 1. Достижимост и противопоставимост

    Има доста проблеми, в които се използва понятието достижимост. Ето един от прякорите. Графиката може да бъде модел на някакъв вид организация, в която хората са представени от върхове, а дъгите интерпретират комуникационните канали. При разглеждането на такъв модел може да се постави въпросът дали информация от едно лице x може да бъде прехвърлена на друго лице x 7 , т.е. дали има път от връх x до връх X/. Ако такъв път съществува, тогава се казва, че върхът x е достъпен от върха x,. Човек може да се интересува от достижимостта на върха x, - от върха x, само по такива пътища, чиито дължини не надвишават дадена стойност или дължината на които е по-малка от най-големия брой върхове в графа.

    Достижимостта в графиката се описва с матрицата на достижимост R = ||r, y||, i,j =1,2,... P,където Пе броят на върховете на графа и всеки елемент е дефиниран, както следва:

    гу- 1 ако е отгоре Х,достъпно от x,

    Gu= 0 иначе.

    Множеството от върхове R(x,) на графа G, достижимо от даден връх xn, се състои от такива елементи x; , за което (/, /)-тият елемент в матрицата за достижимост е равен на 1. Очевидно е, че всички диагонални елементи в матрицата R са равни на 1, тъй като всеки връх е достъпен от себе си по път от дължина 0. Тъй като директното отображение от 1-ви ред Г +1 (x,) е множеството от такива върхове xj,които са достъпни от x по пътища с дължина 1, тогава множеството Γ (Γ (x,)) = Γ Х,)се състои от върхове, достъпни от x, използвайки пътища с дължина 2. По същия начин, Γ p(x,)е наборът от върхове, които са достъпни от x, като се използват пътища с дължина Р.

    Тъй като всеки връх на графа, който е достъпен от xn, трябва да бъде достигнат с помощта на път (или пътеки) с дължина 0 или 1 или 2,..., или Р, то наборът от върхове, достижими за върха xn, може да бъде представен като

    Както виждаме, множеството от достижими върхове R(x,) е пряко транзитивно затваряне на върха xn, т.е. R(x,) = T(x,). Следователно, за да построим матрицата на достижимостта, намираме достижими множества R(x,) за всички върхове x, e X. g y - 1, ако x 7 e R(x,) и гу- 0 иначе. За графиката, показана на фиг. 59.4, а, наборите за достъпност се намират, както следва:

    Ориз. 59.4.

    Матриците на съседство (A), достижимост (R), противопостижимост (Q) имат следния вид:

    Матрица за противопоставимост Q = qij,i,j= 1,2,... P,където П- броят на върховете на графа, се определя, както следва:

    qij= 1, ако е възможно да се стигне до върха от xy x h qtj =О иначе.

    контрадостижим комплект Q(x,)е множество от върхове, така че от всеки връх на това множество може да се стигне до връх X/. Подобно на конструирането на достижимото множество R(x,) може да се напише израз за Q(x,):

    Така е ясно, че Q(x,) не е нищо друго освен обратното транзитивно затваряне на върха x, т.е. Q (x () \u003d T "(x,). От дефинициите става ясно, че колоната X, матрица Q (в която q t j = 1, ако xy € Q(x,), и s/y=0в противен случай) съвпада с реда x на матрицата R, т.е. Q = R, където R е матрицата, транспонирана в матрицата на достижимостта R.

    Матрицата за контрадостижимост е показана по-рано.

    Трябва да се отбележи, че тъй като всички елементи на матриците R и Q са равни на 1 или 0, всеки ред може да се съхранява в двоична форма, спестявайки разходи за компютърна памет. Матриците R и Q са удобни за обработка на компютър, тъй като по отношение на изчисленията основните операции са високоскоростни логически операции.

    2. Намиране на набора от върхове, включени в пътя Ако трябва да разберете за върховете на графа, включени в тези пътища, тогава трябва да запомните определенията за директни и обратни транзитивни затваряния. Тъй като T + (x,) е множеството от върхове, до които има пътища от върха x, а T "(Y) е наборът от върхове, от които има пътища до x /, то T (x,) n T (xj)- набор от върхове, всеки от които принадлежи на поне един път от x до xy. Тези върхове се наричат ​​съществени или интегрални по отношение на двата крайни върха. х,и ху. Всички останали върхове на графа се наричат ​​ирелевантни или излишни, тъй като тяхното премахване не засяга пътищата от x/ до xy.

    Така че, за графиката на фиг. 59.5 намирането на върховете, включени в пътя, например от върха X2 до върха X4, се свежда до намиране на T + (xr) \u003d (xr, xs, X4, X5, Xb), T "(x4) \ u003d (xi, X2, X3, X4, X5) и техните пресечни точки T + (xz) n T(x4) = (X2, X3, X4, X 5 ).

    Позволявам Г = (х, d) - графика на модулна структура, х r, Х-. -върхове, принадлежащи на х.Ако в графиката Гима ориентирана верига от x, до Xpтогава върхът x, - достижимо от върха x,-. Следното твърдение е вярно: ако е връх Xjдостъпно от x, ax (- от Xpтогава х/достъпно от x^Доказателството за този факт е очевидно. Помислете за бинарна релация на множеството х,което определя достижимостта между върховете на графа. Въвеваме обозначението x, -> x, за достижимостта на върха x, - от Xj.Връзката е преходна. Означете с H(x,) множеството върхове на графа г,достъпно от x; . Тогава равенството

    дефинира преходно затваряне на x по отношение на достижимостта.

    Нека докажем следната теорема.

    Теорема 1.1. За избран свързан компонент на графа на модулна структура всеки връх е достъпен от корена, съответстващ на този компонент, т.е. равенство (Х/-корен връх)

    Доказателство.Да предположим, че върховете, (x, e х)недостижим от Xj. Тогава x, e X/ и множеството X" = X x) не е празен. Тъй като избраният компонент на графиката е свързан, тогава има връх x, - д x и веригата /7(x; , xj),водещи от x, към x, -. Въз основа на ацикличността на графиката г,в Х"трябва да има проста верига H(x/, xj),къде до върха х ене включвайте дъги (тази верига може да бъде празна, ако Х"се състои само от x,). Да разгледаме веригата H(x/, xj) = H(x/, x,) U I (x, xj).Това означава, че x. достъпно от върхове x, и Xjи двата върха не съдържат входящи дъги. И това противоречи на дефиницията на графа на модулна структура с един коренен връх. Теоремата е доказана.

    Основното изискване за достъпност е липсата на ненасочени цикли в графика. Въз основа на графиката на фиг. 1.4, отбелязваме, че графът съдържа насочен цикъл и модули, съответстващи на върховете х 4, х 5, f 6 , никога няма да бъде изпълнена. По този начин резултатите от теорема 1.1 засилват изискването да няма насочени цикли в графа на модулите.

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

    Коефициент а, у= 1, ако модулът, съответстващ на индекс /, е достъпен от модула, съответстващ на индекс иСледните резултати се базират на добре позната теорема от теорията на графовете.

    Ориз. 1.4.

    Теорема 1.2. Коефициент че l-тияградуси на матрицата на съседство Разширява броя на различни маршрути, съдържащи / дъги и свързващи върха X/sвръх на ^-насочен граф.

    Помислете за следните три следствия от тази теорема.

    Следствие 1.1.Матрица M \u003d "? J M t,където М- матрица на съседство на ориентация

    уморена графика с Пвърхове, съвпада до числови стойности на коефициентите с матрицата на достижимост НО.

    Доказателство.В насочен граф, съдържащ Пвърхове, максималната дължина на път без повтарящи се дъги не може да надвишава П.Следователно, последователността от степени на матрицата на съседство M 1, където i = 1,2,

    i, определя броя на всички възможни пътища в графика с n дъги.Нека коефициентът t 1)матрици Мразличен от нула. Това означава, че има степен на матрицата M>,за което съответният коефициент T ()също е различно от нула. Следователно от върха има пътека Xjда се Xpтези. връх ^ е достъпен от x rТова следствие определя връзката на матрицата на извикване на графиката на модулна структура, която съвпада с матрицата на съседство A/, с матрицата на достижимост НОи определя алгоритъма за конструиране на последния.

    Следствие 1.2.Нека за някои ив реда на степените на матрицата на съседство М*има коефициент t X1> 0. Тогава в оригиналната графика има насочен цикъл.

    Доказателство.Позволявам m (i > 0 за някои азследователно, Xjдостъпно от x vтези. има цикъл. Съгласно теорема 1.2 този цикъл има / дъги (обикновено повтарящи се).

    Следствие 1.3.Позволявам p-iстепен на матрица на съседство М страцикличната графика съвпада с нулевата матрица (всички коефициенти са равни на нула).

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

    За ациклични графики релацията на достижимост е еквивалентна на частичен строг ред. Транзитивността на релацията на достижимост беше обсъдена по-горе. Антисиметрията следва от липсата на насочени цикли: ако върхът Х )достъпно от x vтогава обратното не е вярно. Въвеждаме обозначението x x > Xpако отгоре Xjдостъпно отгоре x v

    Позволявам G=(X, Г) е ацикличен график, съответстващ на някаква модулна структура. Помислете за низходяща верига от елементи от частично подредено множество X:

    където знакът ">" обозначава отношението на достижимост. Защото хРазбира се, веригата е скъсана x n > x i2 > ... > x в .Връх xjnняма изходящи дъги, т.е. елемент х инминимален (отговаря на модул, който не съдържа извиквания към други модули). Максималният елемент в множеството X е коренният връх.

    • Доказателството на тази теорема е дадено в работата (книга): Лаврищева Е. М., Гришченко В. Н. Програмиране на асембли. Киев: Наукова думка, 1991. 287 с.

    ДОСТИЖНОСТ И СВЪРЗВАНОСТ В ГРАФИ Кратко на лекцията: Пътища на верига и цикли. Графична свързаност и компоненти за свързване. Диаметър, радиус и център на графиката.


    Споделяйте работата си в социалните мрежи

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



    Баранов Виктор Павлович Дискретна математика. Раздел 3Графики, мрежи, кодове.

    Лекция 8

    Лекция 8 ДОСТИЖНОСТ И СВЪРЗВАНЕ В ГРАФИЦИ

    План на лекцията:

    1. Маршрути, вериги и цикли.
    2. Графична свързаност и компоненти за свързване.
    3. Диаметър, радиус и център на графиката.
    4. Матрици за постижимост и противопоставимост.
    1. Маршрути, вериги и контури

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

    , (1)

    , (2)

    (3)

    са пътеки.

    Ориз. един.

    ориентирана верига(или орепио ) се нарича пътят, в който всяка дъга иС използван не повече от веднъж. Така, например, пътища (2) и (3) са орвериги, но път (1) не е, тъй като дъгата се използва два пъти в него.

    Просто се нарича верига, в която всеки връх се използва от най-много единотносно пъти. Например, orchain (3) е проста, но orchain (2) не е.

    Маршрут е ненасочен близнак на пътя, т.е. поредица от ръбове, в които всеки ръб, с изключение на първия и последния, е свързан чрез крайни върхове с ръбовете и. Лента над символ на дъга означава, че се третира като ръб.

    Точно както сме дефинирали орвериги и прости вериги, можем да дефинираме вериги и прости вериги.

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

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

    1. Графична свързаност и компоненти за свързване

    Връх в орграф се казва, че е достъпен от върха, ако има път. Ако освен това е достижимо от, тогава се казва, че тези върхове са взаимно достижими.

    Орграфът се нарича силно свързан или силен , ако всеки два върха в него саа ИМО постижимо. Пример за силен орграф е показан на фиг. 2 а. Тъй като в колонатад даден орцикъл, който включва всички върхове, се вземат всеки два от тяхно постижимо.

    ° ° °

    ° ° ° ° ° °

    ° ° ° ° ° °

    a B C

    Ориз. 2.

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

    Орграфът се наричаслабо свързани или слаби , ако съдържа всеки два върха спочти обединени наполовина . Половин път, за разлика от пътя, може да има обратна посока.в мързеливи дъги. Пример за слаб орграф е показан на фиг. 2 инча Очевидно е, че графиката не съдържапри ty между върховете и, но има полупът, състоящ се от противоположни nа управлявани дъги и.

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

    Дефинирани са три типа свързани компоненти за орграф:силен компонент– ма к най-силният подграф,едностранен компонент- максимално единичниотносно Рони подграф ислаб компоненте най-слабият подграф.

    Концепцията за силен компонент е илюстрирана на фиг. 3.

    ° ° ° ° ° °

    ° ° ° °

    ° ° ° ° ° °

    ° ° ° ° ° °

    ° ° °

    ° ° ° ° °

    Ориз. 3

    Графа, която е еднопосочно свързана, съдържа шест силнид графики, от които само и са силни компонентин тами. Концепцията за еднопосочен компонент е илюстрирана по подобен начин. В тази бележкад Еднопосочният компонент е същият като самата графика. Ако променим ориентациятаа дъга, например, към противоположната, тогава получаваме слаба графика с две едностранниотносно фронтални компоненти, единият от които е образуван от върхове, а другият от ve r гуми.

    За неориентиран граф ние дефинираме на множеството от неговите върхове binР връзка, като се приеме, че има връзка с верига към. Тази връзка еа дава свойствата на рефлексивност, симетрия и транзитивност, тоест става дума за T еквивалентност на носенето. Той разделя набора от върхове на непресичащи се класове: . Два върха от един и същи клас са еквивалентни, тоест има верига в графа, която ги свързва; няма такава верига за върхове от различни класове. От края наЮ Ако ръбовете са във връзка, тогава множеството от ръбове на графиката също ще бъде разделено на непресичащи се класове: , където множеството от всички ребра, чиито краища принадлежат, се означава с .

    Графиките са свързани и се събират в графика. Тези графики се наричаткомпоненти за свързванеграфика. Числото е друга числова характеристика на графика. За свързана графика, ако графиката е изключена, тогава.

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

    1. Диаметър, радиус и център на графиката

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

    2) ;

    3) .

    Определете разстоянието от всеки връх на графиката до най-отдалечения връх от него

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

    Максималният ексцентриситет се наричадиаметър графика, а минимумът -радиус графика. В пълната графика имаме, а в прост цикъл - .

    Върхът се нарича централен ако. Графиката може да има няколкоб такива върхове, а в някои графики всички върхове са централни. В проста верига, с нечетен брой върхове, само един е централен, а с четен брой от тяхС има два такива върха. В пълна графа и за прост цикъл всички върхове са централни. Множеството от централни върхове се наричацентъра на графиката.

    Пример 1 Намерете диаметъра, радиуса и центъра на графиката, показани на фиг. четири.

    ° °

    ° ° °

    ° °

    ° °

    Ориз. четири.

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

    За всеки ред от матрицата намираме най-големия елемент и го записваме са wa от тирето. Най-голямото от тези числа е равно на диаметъра на графиката, най-малкото е pа диус на графиката. Центърът на графиката се формира от централните върхове и.

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

    1. Матрици за постижимост и противопоставимост

    Матрица на достижимостсе определя, както следва:

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

    Матрица за противопоставимост (обратна достижимост) дефинира е както следва:

    Подобно на конструирането на достъпен комплект, човек може да формира наборотносно жест, използвайки следния израз:

    От дефинициите следва, че -та колона на матрицата съвпада с -тия ред на ma T , т.е. къде е матрицата, транспонирана в матрицата.

    Пример 2 Намерете матрици на достижимост и контрадостижимост за графика и т.н.и показано на фиг. 5.

    Ориз. 5.

    Нека дефинираме наборите за достъпност за върховете на графа:

    Следователно матриците за достижимост и противопостижимост имат формата:

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

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

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