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

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

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

Върхът b на орграфа (графа) G се нарича постижимоот U, ако и само ако U=V или има път (маршрут), свързващ U с V (U е началният връх, V е крайният връх). По този начин върху множеството върхове на орграф (графа) се дефинира не само отношението на съседство A, но и отношението на достижимостта T.

Матрица за постижимост Tорграф (графика) G се нарича T 2 n×n, чиито елементи се намират от условието: 1, ако е достижимо от ; 0, ако не е достъпно от .

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

Въведеното отношение на достижимост във върховете на графа G(V,X): върхът w е достижим от върха v, ако v = w или има път от v до w в G. С други думи, достижимостта е рефлексивното и преходно затваряне на връзката на съседство.

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

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

G(V,X) се нарича свързаниако някой от неговите върхове е достъпен от всеки друг връх.

Орграфът G(V,X) се нарича еднопосочно свързано, ако за всеки два от неговите върха, поне единият е достъпен от другия.

Орграфът G(V,X) се нарича силно свързаниако някой от неговите върхове е достъпен от всеки друг.

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

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

Силен свързващ компонентна орграфа G(V,X) се нарича максималният, според броя на срещанията на върхове, силно свързан подграф на този орграф. Свързаният компонент на не-диграф се дефинира по подобен начин.

Матрицата на силната свързаност (свързаност)на орграфа (графа) G(V,Х) се нарича S n×n, чиито елементи се намират от условието: 1, ако е достижимо от и достижимо от ; 0, ако не е достъпно от и не е достъпно от .

(диграф) силно свързан или свързан, достатъчно е да се определи наличието на 0 в матрицата, ако

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

Силно свързаната матрица може да бъде конструирана от матрицата на достижимостта по формулата

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

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

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

Ето един от тях. Графикаможе да бъде модел на някаква организация, в която хората са представени от върхове, а дъгите интерпретират комуникационните канали. Когато се разглежда такъв модел, може да се запита дали информация от едно лице 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. Достижимост в графиката: a -граф; 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 в

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 .

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

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

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

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

Лекция 8

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

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

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

Маршрути, вериги и контури

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

, (1)

, (2)

(3)

са пътеки.

Ориз. един.

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

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

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

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

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

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

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

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

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

° ° °

° ° ° ° ° °

a B C

Ориз. 2.

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

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

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

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

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

° ° ° ° ° °

° ° ° °

° ° ° ° ° °

° ° °

° ° ° ° °

Ориз. 3

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

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

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

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

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

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

2) ;

3) .

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

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

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

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

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

° °

° ° °

° °

Ориз. 4.

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

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

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

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

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

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

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

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

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

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

Ориз. 5.

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

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

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

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

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

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

Един от първите въпроси, които възникват при изследването на графите, е въпросът за съществуването на пътища между дадени или всички двойки върхове. Отговорът на този въпрос е горното отношение на достижимост във върховете на графа 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". К компонентът се нарича минимумако не е строго достъпен от нито един компонент.

Тъй като всички върхове в един компонент са взаимно достижими, лесно е да се види, че отношенията на достижимост и стриктна достижимост върху компонентите не зависят от избора на върхове 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, ако и само ако и двата елемента
и
са равни на 1, т.е.

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

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

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

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

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

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

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

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

Тази връзка може да бъде представена като насочен граф, чиито върхове са компонентите, а ръбът
означава, че
строго постижимо от
. Компонентната графика за Пример 14.1 е показана по-долу.

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

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

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

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

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

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