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

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

Определение. стойносттад(v,w) (краен или безкраен) ще бъде извикан разстояние между върховете v, w . Това разстояние удовлетворява аксиомите на метриката:

1) д(v,w) 0 ид(v,w) = 0 тогава и само акоv=w;

2) d(v, w) = d(w, v);

3) d(v, w) d(v, u) + d(u, w).

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

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

Пример 82.

За графика G, показана на фиг. 3.16, намерете радиуса, диаметъра и центровете.

Ориз. 3.16. Пребройте например 82

Решение.

За определяне на центрове, радиус, диаметър на графиката Ж, намерете матрицата Д(ж)разстояния между върховете на графа, елементи дийкоито ще бъдат разстоянията между върховете v iи vj. За това използваме графично представянеграфика. Имайте предвид, че матрицата Д(ж)симетричен спрямо главния диагонал.

Използване на получената матрица за всеки връх на графиката Ждефинирайте най-голямото отстраняване от израза: за аз,j = 1, 2, …, 5. В резултат на това получаваме: r(v1) = 3,r(v2) = 2,r(v3) = 2,r(v4) = 2,r(v5) = 3.Минимумът от получените числа е радиусът на графиката Ж, максимумът е диаметърът на графиката Ж. означава, R(G) = 2и Д(G) = 3, центровете са върховете v 2,v 3,v 4.

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

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

Радиусграфиката е минималният ексцентрицитет на върховете и диаметър графиката е максималният ексцентрицитет на върховете.

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

Периференвърховете имат ексцентричност, равна на диаметъра.

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

Теорема 12.1.В свързана графа диаметърът е най-много рангът на нейната матрица на съседство.

Теорема 12.2.(Йордания) Всяко дърво има център, състоящ се от един или два съседни върха.

Теорема 12.3.Ако диаметърът на дървото е четен, тогава дървото има един център и всички диаметрални вериги минават през него; ако диаметърът е нечетен, тогава има два центъра и всички диаметрални вериги съдържат ръб, който ги свързва.

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

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

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

. (12.2)

Нека изчислим ексцентрицитета на всеки връх. Тази стойност може да се дефинира като максималния елемент на съответната колона на матрицата на разстоянието (или ред, тъй като матрицата Ссиметричен). Получаваме

№

Радиус на графиката rе минималният ексцентрицитет на върховете. AT този случай r= 2. Такъв ексцентрицитет имат върховете № 2, № 4 и № 5. Тези върхове образуват центъра на графиката. Диаметър на графиката де максималният ексцентрицитет на върховете. В такъв случай д= 3. Такъв ексцентрицитет имат върхове № 1 и № 3, това е периферията на графа. В изследвания граф върховете се оказаха или централни, или периферни. Има и други върхове в графите от по-висок ред.

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

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

Решаването на проблеми на теорията на графите с помощта на различни трансформации на матрицата на съседство се нарича алгебричен метод .

Пример 12.6.Намерете матрицата на разстоянието на графиката, показана на фиг. 12.1, по алгебричен метод.

Решение.Матрицата на съседство на тази графика е:

.

Ще попълним матрицата на разстоянието, като вземем предвид степените на матрицата на съседство. Единиците на матрицата на съседство показват двойки върхове, които имат разстояние едно помежду си (т.е. те са свързани с един ръб).

.

Диагоналните елементи на матрицата на разстоянието са нули. Умножете матрицата на съседство сама по себе си:

.

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

.

Остава неизвестно разстоянието между върховете 1 и 3. Ще умножим матрицата на съседство върху себе си до матрицата не-нулев елемент няма да се появи . След това съответният елемент от матрицата на разстоянието равен на степентаматрици на съседство: . На следващата стъпка получаваме

В последния раздел подчертахме, че матрицата на съседство $A$, въведена там, или по-скоро матрицата на съседство на върхове на граф, играе много важна роля. съществена роляв теорията на графите. Отбелязахме като предимства на тази матрица - тя е квадратна от порядъка, равно на числоторедове от матрицата на инцидентност $B$, т.е., като правило, съдържа по-малко числоелементи. Второ, тази матрица съхранява цялата информация за ръбовете на графа и, за дадено номериране на върховете, уникално описва графа. Матрицата на съседство, подобно на матрицата на инцидентност на графика, е (0,1)-матрица, т.е. неговите елементи могат да се разглеждат като елементи на други алгебрични структури, а не само като елементи на множеството от цели числа. По-специално отбелязахме, че елементите на матрицата на съседство могат да се разглеждат като елементи на булевата алгебра, подчинени на законите на булевата аритметика, но не обяснихме това правилно. Преди да запълним тази празнина, подчертаваме предимствата на матрицата на съседство, които произтичат от нейната квадратура.

За целта си припомняме правилата за умножение на матрици. Нека са дадени произволни матрици с числени елементи: матрица $A$ с размерност $n\times m$ с елементи $a_(ik)$ и матрица $B$ с размерност $m\times q$ с елементи $b_(kj)$ . Матрица $C$ с размерност $n\times q$ се нарича произведение на матрица $A$ и $B$ (редът е важен), ако нейните елементи $c_(ij)$ са дефинирани по следния начин: $c_(ij) = \сума\граници_( k = 1)^m (a_(ik) b_(kj))$. Произведението на матриците се записва по обичайния начин $AB=C$. Както можете да видите, произведението на матриците изисква последователност в размерите на първия и втория фактор (броят на колоните на първата факторна матрица е равен на броя на редовете на втората факторна матрица). Това изискване изчезва, ако разглеждаме квадратни матрици от един и същ ред и следователно можем да разглеждаме произволни степени на квадратна матрица. Това е едно от предимствата квадратни матриципред правоъгълниците. Друго предимство е, че можем да дадем графична интерпретация на степенните елементи на матрицата на съседство.

Нека матрицата на съседство $A$ е във формата: $A = \left(((\begin(array)(*c) (a_(11) ) & (a_(12) ) & (...) & ( a_(1n ) ) \\ (a_(21) ) & (a_(22) ) & (...) & (a_(2n) ) \\ (...) & (...) & (.. .) & (...) \\ (a_(n1) ) & (a_(n2) ) & (...) & (a_(nn) ) \\ \end(array) )) \right)$, и неговата $ k$-та степен — $A^k = \left(((\begin(array)(*c) (a_(11)^((k)) ) & (a_(12)^((k) ) ) & (...) & (a_(1n)^((k)) ) \\ (a_(21)^((k)) ) & (a_(22)^((k)) ) & ( .. .) & (a_(2n)^((k)) ) \\ (...) & (...) & (...) & (...) \\ (a_(n1)^ (( k)) ) & (a_(n2)^((k)) ) & (...) & (a_(nn)^((k)) ) \\ \end(array) )) \right) $, където $k = 2,3,...$ Очевидно е, че $A^k$, подобно на матрицата $A$, ще бъде симетрична матрица.

Нека $k=2$. Тогава $a_(ij)^((2)) = \sum\limits_(k = 1)^n (a_(il) a_(lj))$ ($i,j = 1,2,...,n $), а всеки член $a_(il) a_(lj)$ е равен на $0$ или $1$. Случаят, когато $a_(il) a_(lj) = 1$ означава, че има две ребра в графиката: ребро $\(i,l\)$ (тъй като $a_(il) = 1)$ и ребро $\( l,j\)$ (тъй като $a_(lj) = 1$) и следователно пътя $\(( \(i,l\), \(l,j\) )\)$ от $i $- ти връх до $j$-ти с дължина две (път от две ребра). Тук говорим за път, а не за верига, тъй като посоката е указана - от $i$-тия връх до $j$-тия. Така $a_(ij)^((2))$ ни дава броя на всички пътища на графиката (в геометричната интерпретация на графиката) с дължина 2, водещи от $i$-тия връх до $j$-тия един.

Ако $k=3$, тогава $A^3 = A^2A = AA^2 = AAA$ и $a_(ij)^((3)) = \sum\limits_(l_1 = 1)^n (a_( il_1 ) ) a_(l_1 j)^((2)) = $ $\sum\limits_(l_1 = 1)^n (a_(il_1 ) ) \left((\sum\limits_(l_2 = 1)^n ( a_ (l_1 l_2 ) a_(l_2 j) ) ) \right) =$ $\sum\limits_(l_1 = 1)^n (\sum\limits_(l_2 = 1)^n (a_(il_1 ) ) ) a_( l_1 l_2 ) a_(l_2 j) = \sum\limits_(l_1 ,l_2 = 1)^n (a_(il_1 ) a_(l_1 l_2 ) a_(l_2 j) )$.

Терминът $a_(il_1 ) a_(l_1 l_2 ) a_(l_2 j) $, ако е равен на 1, дефинира път с дължина 3, преминаващ от $i$-тия връх до $j$-тия връх и минаваща през върховете $l_1$ и $l_2$. Тогава $a_(ij)^((3))$ ни дава броя на пътищата с дължина 3, свързващи $i$-тия и $j$-тия връх. AT общ случай$a_(ij)^((k))$ указва броя на пътеките с дължина $k$, свързващи $i$-тия и $j$-тия връх. Освен това $a_(ij)^((k)) = \sum\limits_(l_1 ,l_2 ,...,l_(k - 1) = 1)^n (a_(il_1 ) a_(l_1 l_2 ) .. .) a_(l_(k - 2) l_(k - 1) ) a_(l_(k - 1) j)$.

Ясно е, че количеството $a_(ii)^((k)) $ ни дава броя затворени пътища с дължина $k$, започващи и завършващи във върха $i$. Така, път с дължина 2, $a_(il) a_(li)$, означава път, минаващ по ръба $\( i,l \)$ от върха $i$ до върха $l$ и обратно. Следователно $a_(ii)^((2)) = s_i$, т.е. диагоналните елементи на матрицата $A^2$ са равни на степените на съответните върхове.

Помислете сега, заедно с матрицата $A$, матрицата $\dot (A)$, която се различава от матрицата $A$ само по това, че нейните елементи (числа 0 или 1) се разглеждат като елементи на булевата алгебра. Следователно действията с такива матрици ще се извършват съгласно правилата на булевата алгебра. Тъй като операциите за събиране и умножение на матрици с булеви елементи се свеждат до операциите за добавяне и умножение на елементи от тези матрици според правилата на булевата аритметика, надяваме се, че това няма да доведе до затруднения. Матрица с булеви елементи ще се нарича булева матрица. Очевидно операциите събиране и умножение на булеви матрици са затворени върху множеството от булеви матрици, т.е. резултатът от тези операции отново ще бъде булева матрица.

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

Резултатът от добавянето на две булеви симетрични матрици от един и същи ред ще бъде булева симетрична матрица от същия ред с нули на онези места, където и двата члена имат нули, и единици на тези места, където поне един член има единица. В графичната интерпретация тази операция се нарича операция добавяне на графика. Сумата от две графики, дадено на едно и също множество от върхове с еднакво номериране, се нарича граф, чиито върхове i и j са несъседни, ако не са съседни и за двата сборни графа, а върховете i и j са съседни, ако са съседни най-малко една сборна графика.

Нека сега интерпретираме втората степен на булевата матрица на съседство $\dot (A)^2$ със записи $\dot (a)_(ij)^((2)) = \sum\limits_(l = 1)^ n (\dot ( a)_(il) \dot (a)_(lj) )$. Ясно е, че $\dot (a)_(ij)^((2)) = 1$, ако поне един член $\dot (a)_(il) \dot (a)_(lj) $ е равен на 1 и $\dot (a)_(ij)^((2)) = 0$, ако всички членове са равни на 0. Ако матрицата $\dot (A)$ е матрицата на съседство на някаква графика, т.е. е симетрична (0,1)-матрица с нулев главен диагонал, тогава матрицата $\dot (A)^2$, най-общо казано, не е матрица на съседство на граф в смисъла, който сме възприели, тъй като всички нейни диагоналните елементи са равни на 1 (ако графиката няма изолирани върхове). За да разглеждаме такива матрици като матрици на съседство, трябва, когато разглеждаме връзките между върховете на някаква свързана система, които определят тази система като граф, да допуснем връзката на някои върхове със себе си. Извиква се „ръб“, който определя връзката на определен връх със себе си цикъл. Ще продължим, както и преди, под думата граф ще разбираме граф без цикли, а за граф с цикли, ако това не става ясно от контекста, ще кажем така - граф с цикли.

Помислете за сумата $\dot (A)^() = \dot (A) + \dot (A)^2$. Матрицата $\dot (A)^()$ ни дава граф, получен от оригиналния, като го "насищаме" с допълнителни връзки, съответстващи на пътища с дължина 2. Тоест върховете $i$ и $j$ са съседни в новата графа, ако са съседни в оригиналната графа или тези върхове са свързани с някакъв път с дължина 2, а върховете $i$ и $j$ са несъседни, ако не са съседни в оригиналната графа и има няма път с дължина 2, свързващ тези върхове.

$\dot (A)^() = \dot (A) + \dot (A)^2 + \dot (A)^3$ се дефинира по подобен начин. Тоест в графиката дадени от матрицата$\dot (A)^()$ върховете $i$ и $j$ са съседни, ако са съседни в графиката $\dot (A)^()$ или тези върхове са свързани с някакъв път с дължина 3 в оригинална графа и върховете $i$ и $j$ са несъседни, ако не са съседни в графиката $\dot (A)^()$ и няма път с дължина 3, свързващ тези върхове в оригиналната графа . И така нататък.

Като цяло $\dot (A)^([k]) = \sum\limits_(i = 1)^k (\dot (A)^i) $. Лесно се вижда, че всички $\dot (A)^([k])$ за $k \ge n - 1$, където $n$ е редът на матрицата $\dot (A)$, са равни . Наистина, ако върховете $i$ и $j$ са свързани, тогава има път (верига), свързващ тези върхове, и следователно има прост път (проста верига), свързващ тези върхове. Максималният възможен прост път в граф с $n$-върхове има дължина $n-1$ (прост път, свързващ всички отделни върхове на графа). Следователно, ако в матрицата $\dot (A)^()$ има 1 на място $(i,j)$, то на същото място в матрицата $\dot (A)^([k])$ за $k \ge n - 1$ също ще бъде 1, тъй като матрицата $\dot (A)^()$ е включена като булев член в дефиницията на матрицата $\dot (A)^([k] )$. Ако в матрицата $\dot (A)^()$ има 0 вместо $(i,j)$, това означава, че в графиката няма проста верига, свързваща $i$-ти и $j$- ия връх и следователно изобщо няма верига, свързваща тези върхове. Следователно в разглеждания случай и в матрицата $\dot (A)^([k])$ за $k \ge n - 1$ мястото ($i$,$j)$ ще бъде 0. Това доказва нашето твърдение за равенството на всички матрици $\dot (A)^([k])$ за $k \ge n - 1$ на матрицата $\dot (A)^()$ и, следователно, на всяка друго.

Извиква се матрицата $\dot (A)^()$ матрицата на транзитивното затваряне на матрицата$\dot (A)$, както и матрицата на съседство на транзитивното затваряне на графа, зададена от матрицата $\dot (A)$. Съвсем очевидно е, че матрицата на транзитивното затваряне на свързан граф е матрицата на съседство пълна графика, т.е. квадратна матрица, състояща се само от единици. Това наблюдение също ни дава метод за определяне на свързаността на графика: графът е свързан тогава и само тогава, когато матрицата на транзитивното затваряне на неговата матрица на съседство ще се състои само от единици (това ще бъде матрицата на пълната графа).

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

Нека сега покажем как процедурата на транзитивно затваряне ни позволява да конструираме така наречената "матрица на разстоянието". За целта определяме разстоянието между върховете $i$ и $j$. Ако върховете $i$ и $j$ са свързани, тогава разстояниемежду тях ще назовем дължината на минималния (според броя на обхожданията на ребрата) прост път, свързващ тези върхове; ако върховете $i$ и $j$ са несвързани, тогава задаваме разстоянието равно на нула (нула като отрицание на някакъв път, свързващ тези върхове). С тази дефиниция на разстояние разстоянието между върха и себе си е равно на 2 (дължината на пътя по ръба и обратно). Ако във върха има цикъл, тогава разстоянието между върха и себе си е равно на 1.

За да конструираме матрица на разстоянието за граф с $n$-върхове с матрица на съседство $A$, която би посочила разстоянието между всеки два върха, ние въвеждаме матриците $A^(\(k\)) = A^([ k]) - A^()$, където $k = 2,3,...,n - 1$ и $A^(\(1\)) = A^() = A$. Липсата на точки над нотацията на матрицата показва, че разглеждаме матриците $A^([k])$ ($k = 1,2,...,n - 1)$ като числени (0,1)-матрици, естествено получени от матриците $\dot (A)^([k])$ (сега разглеждаме булевите елементи 0 и 1 като числата 0 и 1). От метода за конструиране на матриците $A^([k])$ следва, че $A^([k]) \ge A^()$ ($k = 2,3,...,n - 1$ ) и следователно $A^(\(k\))$ ($k = 1,2,...,n - 1$) са (0,1)-матрици. Освен това матрицата $A^(\(2\))$ съдържа 1 само на онези места, където върховете, определени от това място (номер на ред и номер на колона), са свързани с някакъв път с дължина две и не са свързани с по-малък път. По подобен начин, $A^(\(3\))$ съдържа 1 само на онези места, където върховете, дефинирани от това място, са свързани с път с дължина три и не са свързани с път с по-малка дължина и т.н. Така матрицата $D = \sum\limits_(k = 1)^(n - 1) (k \cdot A^(\(k\)))$ ще бъде желаната матрица на разстоянието. Елементът $d_(ij)$ на тази матрица ще бъде равен на разстоянието между върховете $i$ и $j$. Разстоянието между върховете $u$ и $v$ също ще бъде означено като $d(u,v)$.

Коментирайте.Конкретен продукт на събираемото $a_(il_1 ) a_(l_1 l_2 ) ...a_(l_(k - 2) l_(k - 1) ) a_(l_(k - 1) j) = 1$ елемент $a_(ij ) ^((k))$ $k$-та степен на матрицата на съседство $A^k$ определя конкретен $(i,j)$-път $i\(i,l_1\)l_1 \(l_1 ,l_2 \ )l_2 ...l_(k - 2) \(l_(k - 2) ,l_(k - 1) \)l_(k - 1) \(l_(k - 1) ,j\)j$ от $ i$ -ти връх към $j$-ти. Последователност от съседни върхове и ръбове, които ги свързват $i\(i,l_1 \)l_1 \(l_1 ,l_2 \)l_2 ...l_(k - 2) \(l_(k - 2) ,l_(k - 1) \ )l_(k - 1) \(l_(k - 1) ,j\)j$ също се нарича $(i,j)$-маршрут. Маршрутът се различава от верига, състояща се само от отделни съседни ръбове по това, че в маршрута са разрешени равни ръбове. Един прост маршрут се състои от различни съседни върхове и ръбове, т.е. почти идентичен с обикновена верига.

Съвсем очевидно е, че елементът $d_(ij) $ от матрицата на разстоянието определя дължината на минималната верига, свързваща $i$-тия връх с $j$-тия.

Разгледайте примери за графики, дадени на фигури 1 и 2, техните матрици на съседство и техните матрици на разстояние.

Фиг.1 (Графика $\Gamma _1$, матрица на съседство $A_1$, матрица на разстояние $D_1$).
$A_1 = \left(((\begin(array)(*c) 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 \\ 1 & 1 и 1 и 0 и 0 и 0 и 0 и 0 и 0 и 0 и 0 и 0 и 0 \\ 0 и 0 и 1 и 0 и 0 и 1 и 1 и 1 и 0 и 1 и 0 и 0 и 1 \\ 0 и 0 и 0 и 0 и 1 и 0 и 1 и 1 и 0 и 0 и 0 и 0 и 0 \\ 0 и 0 и 0 и 0 и 1 и 1 и 0 и 1 и 0 и 0 и 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ \end(array) )) \right), $
$D_1 = \left(((\begin(array)(*c) 2 & 1 & 1 & 1 & 2 & 3 & 3 & 3 & 3 & 2 & 3 & 3 & 2 \\ 1 & 2 & 1 & 1 и 2 и 3 и 3 и 3 и 3 и 2 и 3 и 3 и 2 \\ 1 и 1 и 2 и 1 и 1 и 2 и 2 и 2 и 2 и 1 и 2 и 2 и 1 \\ 1 & 1 и 1 и 2 и 2 и 3 и 3 и 3 и 3 и 2 и 3 и 3 и 2 \\ 2 и 2 и 1 и 2 и 2 и 1 и 1 и 1 и 2 и 1 и 2 и 2 и 1 \\ 3 и 3 и 2 и 3 и 1 и 2 и 1 и 1 и 3 и 2 и 3 и 3 и 2 \\ 3 и 3 и 2 и 3 и 1 и 1 и 2 и 1 и 3 и 2 и 3 & 3 & 2 \\ 3 & 3 & 2 & 3 & 1 & 1 & 1 & 2 & 3 & 2 & 3 & 3 & 2 \\ 3 & 3 & 2 & 3 & 2 & 3 & 3 & 3 & 2 & 1 & 1 & 1 & 2 \\ 2 & 2 & 1 & 2 & 1 & 2 & 2 & 2 & 1 & 2 & 1 & 1 & 1 \\ 3 & 3 & 2 & 3 & 2 & 3 & 3 & 3 & 2 & 2 & 2 & 1 & 2 \\ 3 & 3 & 2 & 3 & 2 & 3 & 3 & 3 & 3 & 1 & 1 & 1 & 1 & 2 & 2 \\ 2 & 2 & 1 & 2 & 1 & 2 & 2 & 2 & 2 & 1 & 2 & 2 & 2 \\ \end(масив) )) \right) $

Ориз. 2 (Графика $\Gamma _2$, матрица на съседство $A_2$, матрица на разстояние $D_2$).
$A_2 = \left(((\begin(array)(*c) 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 1 & 0 \ \ 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ \end(array) )) \right)$,
$D_2 = \left(((\begin(array)(*c) 2 & 1 & 2 & 3 & 4 & 5 & 6 & 4 & 4 & 5 \\ 1 & 2 & 1 & 2 & 3 & 4 & 5 & ​​​​3 & 3 & 4 \\ 2 & 1 & 2 & 1 & 2 & 3 & 4 & 2 & 2 & 3 \\ 3 & 2 & 1 & 2 & 1 & 2 & 3 & 1 & 1 & 2 \ \ 4 & 3 & 2 & 1 & 2 & 1 & 2 & 2 & 2 & 3 \\ 5 & 4 & 3 & 2 & 1 & 2 & 1 & 3 & 3 & 4 \\ 6 & 5 & 4 & 3 & 2 & 1 & 2 & 4 & 4 & 5 \\ 4 & 3 & 2 & 1 & 2 & 3 & 4 & 2 & 2 & 3 \\ 4 & 3 & 2 & 1 & 2 & 3 & 4 & 2 & 2 & 1 \\ 5 & 4 & 3 & 2 & 3 & 4 & 5 & 3 & 1 & 2 \\ \end(array) )) \right). $

От матриците $D_1$ и $D_2$ е лесно да се определи диаметри$d_1$ на графиката $\Gamma _1$ и $d_2$ на графиката $\Gamma _2$ като максимални стойности на елементите на тези матрици. Така че $d_1 = 3$ и $d_2 = 6$.

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

В края на раздела ще отбележим методите за определяне на минималните и максималните вериги с помощта на матрицата на разстоянията, свързващи $i$-тия и $j$-тия върхове в графиката.

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

Ексцентричност$e(v)$ на връх $v$ в свързана графа $\Gamma$ се определя като max $d(u,v)$ за всички върхове $u$ в $\Gamma$. Радиус$r(\Gamma)$ е най-малкият от ексцентрицитетите на върха. Имайте предвид, че най-големият от ексцентрицитетите е равен на диаметъра на графиката. Върхът $v$ се нарича централен връх на графиката $\Gamma$, ако $e(v) = r(\Gamma)$; центърграф $\Gamma$ е множеството от всички централни върхове.

Така че за графиката $\Gamma _1$ от фиг.1, ексцентрицитетът на връх 13 ще бъде равен на 2 ($e(13) = 2$). Върховете 3, 5 и 10 ще имат еднакви ексцентритети ($e(3) = e(5) = e(10) = 2$). Ексцентрицитетът, равен на 2, ще бъде най-малък за графиката $\Gamma _1$, т.е. $r(\Gamma _1) = 2$. Центърът на графиката $\Gamma _1$ ще се състои от върхове 3, 5, 10 и 13. Най-големият ексцентрицитет ще бъде равен на 3 и ще бъде равен, както беше отбелязано по-горе, на диаметъра на графиката $\Gamma _1$ .

За графиката $\Gamma _2$ от фиг. 2, единственият връх 4 ще има най-малък ексцентрицитет ($e(4) = r(\Gamma _2) = 3$). Следователно центърът на графиката $\Gamma _2$ се състои от един връх 4. Диаметърът на графиката $\Gamma _2$, както беше отбелязано по-горе, е 6.

Графът $\Gamma _2$ е дърво и структурата на центъра на всяко дърво се описва от следната теорема.

Теоремата на Джордан-Силвестър.Всяко дърво има център, състоящ се от един връх или два съседни върха.

Доказателство.Означаваме с $K_1$ графа, състоящ се от един изолиран връх, а с $K_2$ графа от два върха, свързани с ребро. По дефиниция задаваме $e(K_1) = r(K_1) = 0$. Тогава твърдението на теоремата ще бъде валидно за $K_1$ и $K_2$. Нека покажем, че всяко дърво $T$ има същите централни върхове като дървото $(T)"$, получено от $T$ чрез премахване на всички негови висящи върхове. Ясно е, че разстоянието от даден връх $u$ до всеки друг връх $v$ може да достигне най-голямата стойностсамо ако $v$ е висящ връх.

По този начин, ексцентричността на всеки връх на дървото $(T)"$ е точно с едно по-малка от ексцентричността на същия връх в $T$. ексцентричността в $(T)"$, т.е. центровете на дърветата $T$ и $(T)"$ съвпадат. Ако продължим процеса на премахване на висящи върхове, тогава получаваме последователност от дървета със същия център като $T$. Тъй като $T$ е краен, непременно ще стигнем или до $ K_1$, или до $K_2$ Във всеки случай всички върхове на дървото, получени по този начин, образуват центъра на дървото, което следователно се състои или от един връх, или от два съседни върха.

Нека сега покажем как, използвайки матрицата на разстоянието, може да се определи, например, минималният път, свързващ връх 4 с връх 8 на графиката $\Gamma _1$. В матрицата $D_1$ елементът $d_(48) = 3$. Нека вземем 8-мата колона на матрицата $D_1$ и намерим в колоната всички елементи от тази колона, равни на 1. Поне един такъв елемент може да бъде намерен поради свързаността на графа $D_1$. Всъщност в 8-ма колона ще има три такива единици и те са разположени в 5-ти, 6-ти и 7-ми редове. Нека сега вземем 4-тия ред и разгледаме в него елементите, разположени в 5-та, 6-та и 7-ма колона. Тези елементи ще бъдат съответно 2, 3 и 3. Само елементът, намиращ се в 5-та колона, е равен на 2 и заедно с 1, намиращ се на място (5,8), дава сумата 3. Следователно връх 5 е включен във веригата $\( \(4, ?\), \(? ,5\),\(5,8\)\)$. Нека сега вземем 5-тата колона на матрицата и разгледаме 1 от тази колона. Това ще бъдат елементите, разположени на 3-ти, 6-ти, 7-ми, 8-ми, 10-ти и 13-ти ред. Връщаме се отново на 4-ти ред и виждаме, че само в пресечната точка на третата колона и 4-тия ред е 1, което, комбинирано с 1 на място (3,5), дава общо 2. Следователно желаната верига ще бъде $\( \ (4,3\),\(3,5\),\(5,8\)\)$. Разглеждайки сега фигура 1, ние сме убедени във валидността на намереното решение.

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

Нека G(V,X) е псевдограф и нека върховете v и w (v¹w) на този граф са свързани с маршрут. Тогава задължително съществува минимален маршрут, свързващ тези върхове. Означете дължината на този маршрут d(v, w). Задаваме също d(v, v) =0 за всеки връх vнV; d(v, w) = ¥ ако няма маршрут между v и w.

Стойността d(v,w), дефинирана по този начин за всякакви върхове v и w на графиката G(V, X), се нарича разстоянието между v и w.

Броят на разстоянията в граф с n върха е равен на броя на комбинациите C n 2 .

Нека графиката G(V,X) е свързана. Нека дефинираме следните понятия за него:

Диаметър на графиката: d(G) = maxd(v, w).

Ексцентричност (максимално изместване) на върха: r(v) = maxd(v, w);

Радиус на графиката: r(G) = min r(v);

Център на графиката: всеки връх vОV такъв, че r(v) = r(G).

Диаметърът на графиката, ексцентритетите на върховете, радиусът на графиката и центровете на графиката се наричат ​​метрични характеристики на графиката.

Пример. Намерете метричните характеристики на графиката, дадена от диаграмата:

Нека намерим всички разстояния, като вземем предвид, че d(v, w) = d(w, v).

Броят на разстоянията в дадената графика С 5 2 = 5!/3!2! = 10: d(v 1, v 2) =1, d(v 1, v 3) = 2, d(v 1, v 4) = 2, d(v 1, v 5) = 3, d(v 2, v 3) = 1, d(v 2, v 4) = 1, d(v 2, v 5) = 2, d(v 3, v 4) = 1, d(v 3, v 5) = 2, d(v 4, v 5) = 1.

Диаметър на графиката d(G) =3.

Ексцентритетите на върховете: r(v 1) = 3, r(v 2) = 2, r(v 3) = 2, r(v 4) = 2, r(v 5) = 3.

Радиус на графиката r(G) = 2.

Графични центрове v 2 , v 3 , v 4 .

3. Минимални маршрути в заредени графики

Граф G(V, X) се нарича зареден, ако в множеството от ребра на графиката има функция, наречена тегловна функция, която свързва с всяко ребро x нX на графиката някакво число l(x). Стойността l(x) се нарича дължина на дъгата.

Количеството l(x) може да бъде дадено различен смисъл: транспортни разходи, време за пътуване, разстояние между точките, разход на бензин и др.

Сумата от дължините на ръбовете, включени в маршрута, се нарича дължина на маршрута.

Забележете, че ако за всички x Î X l(x) = 1, тогава графиката може да се счита за ненатоварена.

Маршрут в графа G(V, X) от връх v до връх w (v¹w) се нарича минимален, ако има минималната дължина сред всички маршрути в графика G(V, X) от връх v до връх w.

Ограничаваме се до графики, за които l(x)>0.

При търсене на минималния маршрут в заредена графика с l(x)>0

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

всеки минимален маршрут е прост път.

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

Нека графът G(V,X) е зареден, броят на върховете n ³ 2 е необходимо да се изгради минимален маршрут от v 1 до v n .

Нека дадем алгоритъм.

Стъпка 1. Присвоете индекс a(v i) на всеки връх: a(v 1) = 0, a(v i) = ¥, i ¹ 1. Оцветете върха v 1 и задайте v = v 1 .

Стъпка 2. За всеки неоцветен връх v j променете индекса според правилото:

a(v j) = min (a(v j), a(v) + l(v, v j)).

Оцветете върха, за който a(v j) е най-малкият.. също оцветете ръба, водещ до избрания възел. тази стъпкавръх v j . Поставете v = v j.

Стъпка 3. Ако v = v j, завършете процедурата от най-краткия маршрут от v 1 до v n. ако v ¹ v n, тогава преминете към стъпка 2.

Коментирайте. Стъпка 2 е невъзможна, ако всички a(v j)= ¥. В този случай върхът v n е недостижим.

Нека приложим горния алгоритъм към графиката, дадена от диаграмата. Нека намерим в него най-краткия път от v 1 до v 6 .

Стъпка 1. Оцветете върха v 1 . Задайте индекси на върховете: a(v 1) =0, a(v 2) = a(v 3)=…= a(v n)=¥. Поставяме v 1 = v.

a(v 2) = min(¥, 0+4) = 4,

a(v 3) = min(¥, 0+7) = 7,

a(v 4) = min(¥, 0+3) = 3,

a(v 5) = min (¥, 0+¥) = ¥,

a(v 6) = min (¥, 0+¥) = ¥.

Оцветяваме върха v 4 и ръба (v 1 , v 4 ).

Стъпка 3. Тъй като върхът v 6 не е оцветен, изпълняваме стъпка 2, задавайки v = v 4 .

a(v 2) = min(4, 3+¥) = 4,

a(v 3) = min(7, 3+¥) = 7,

a(v 5) = min(¥, 3+3) = 6,

a(v 6) = min (¥, 3+¥) = ¥.

Оцветяваме върха v 2 и ръба (v 1 , v 2 ).

Стъпка 3. Тъй като върхът v 6 не е оцветен, изпълняваме стъпка 2, задавайки v = v 2 .

a(v 3) = min(7, 4+3) = 7,

a(v 5) = min(6, 4+2) = 6,

a(v 6) = min (¥, 4+¥) = ¥.

Оцветяваме върха v 5 и ръба (v 4 , v 5 ).

Стъпка 3. Тъй като върхът v 6 не е оцветен, изпълняваме стъпка 2, задавайки v = v 5 .

a(v 3) = min(7, 6+¥) = 7,

a(v 6) = min (¥, 6+2) = 8.

Оцветяваме върха v 3 и ръба (v 1 , v 3 ).

Стъпка 3. Тъй като върхът v 6 не е оцветен, изпълняваме стъпка 2, задавайки v = v 3 .

a(v 6) = min(8, 7+2) = 8.

Оцветяваме върха v 6 и ръба (v 5 , v 6 ).

Тъй като върхът v 6 е оцветен, спираме работата. Получихме минималния маршрут v 1 v 4 v 5 v 6 , чиято дължина е равна на 8 .

Обърнете внимание, че в този случай това не е единственият минимален маршрут за върхове v 1 и v 6, защото в алгоритъма беше възможно да оцветим вместо ръба (v 4 , v 5 ) ръба (v 2 , v 5 ), тогава щяхме да получим друг маршрут със същата дължина.

4. Задачи върху дървета

Графиката се нарича ациклична, ако няма цикли.

Граф без цикли се нарича гора.

Дървото е свързан ацикличен граф.

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

Лесно е да се провери, че концепцията за разстояние, въведена по този начин, удовлетворява аксиомите на метриката:

2. ако и само ако ;

3. ;

4. неравенството на триъгълника е вярно:

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

диаметърграфиката се нарича число, равно на разстояниетомежду най-отдалечените един от друг върхове на графа:

.

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

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

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

За да илюстрираме, нека да разгледаме графиката на фиг. 4.29. Тук

Ето защо

Връх 2 е центърът на графиката, а всички останали върхове са периферни. Верига 1, 2, 3 е една от диаметралните вериги.

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

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

Обхождане на графика

Вече беше отбелязано, че началото на теорията на графите е свързано с проблема за мостовете в Кьонигсберг. Този известен на времето си проблем се състои в следното. Седем моста на град Кьонигсберг (сега Калининград) са били разположени на река Прегел, както е показано на фиг. 4.30. Задачата е да напуснете къщата и да се върнете обратно, като минавате само веднъж на всеки мост.

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

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

Например графиката, показана на фиг. 4.31 е Ойлер, защото съдържа цикъла на Ойлер 1, 2, 3, 4, 5, 6, 4, 2, 6, 1. Има други цикли на Ойлер в тази графика. Ясно е, че всеки два такива цикъла се различават един от друг само по реда, в който се пресичат ръбовете.

Теорема 4.7.(Л. Ойлер, 1736 г .) Свързаният граф е Ойлер тогава и само тогава, когато степените на всички негови върхове са четни.

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

Теорема 4.8(Л. Ойлер, 1736 г .) Мултиграф има верига на Ойлер тогава и само ако е свързан и броят на върховете с нечетна степен е 0 или 2.

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