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

Изявление. Ако има маршрут за два върха, който ги свързва, тогава трябва да има минимален маршрут, свързващ тези върхове. Нека означим дължината на този маршрут катод(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, матрицата на разстоянието има следващ изглед:

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

Радиус на графиката 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. Ще умножим матрицата на съседство върху себе си до матрицата не-нулев елемент няма да се появи . След това съответният елемент от матрицата на разстоянието равен на степентаматрици на съседство: . На следващата стъпка получаваме

Следователно, , и накрая

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

Нека 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. Задачи върху дървета

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

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

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

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

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

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

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

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

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

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

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

. (12.2)

№

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

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

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

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

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

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