Grafi cestnih omrežij in algoritmi za delo z njimi. Matematični model

Naj bo G(V,X) psevdograf in naj bosta točki v in w (v¹w) tega grafa povezani s potjo. Potem mora obstajati minimalna pot, ki povezuje ta oglišča. Dolžino te poti označimo z d(v, w). Postavimo tudi d(v, v) =0 za poljubno vozlišče vÎV; d(v, w) = ¥, če ni poti, ki bi povezovala v in w.

Tako definirana vrednost d(v,w) za poljubni točki v in w grafa G(V, X) se imenuje razdalja med v in w.

Število razdalj v grafu z n vozlišči je enako številu kombinacij C n 2 .

Naj bo graf G(V,X) povezan. Določimo naslednje koncepte zanj:

Štetje premera: d(G) = maxd(v, w).

Ekscentričnost (največji odmik) oglišča: r(v) = maxd(v, w);

Polmer grafa: r(G) = min r(v);

Središče grafa: vsako vozlišče vÎV tako, da je r(v) = r(G).

Premer grafa, ekscentričnosti oglišč, polmer grafa in središča grafa imenujemo metrične značilnosti grafa.

Primer. Najdi metrične specifikacije graf, določen z diagramom:

Poiščemo vse razdalje, pri čemer upoštevamo, da je d(v, w) = d(w, v).

Število razdalj v tem grafu C 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.

Premer grafa d(G) =3.

Ekscentričnosti vrhov: r(v 1) = 3, r(v 2) = 2, r(v 3) = 2, r(v 4) = 2, r(v 5) = 3.

Polmer grafa r(G) = 2.

Središča grafa so v 2, v 3, v 4.

3. Minimalne poti v naloženih grafih

Graf G(V, X) imenujemo obremenjen, če je na množici robov grafa določena funkcija, imenovana utežna funkcija, ki vsakemu robu x ОХ grafa dodeli določeno število l(x). Vrednost l(x) imenujemo dolžina loka.

Vrednost l(x) je mogoče podati drugačen pomen: stroški prevoza, čas potovanja, razdalja med točkami, poraba bencina itd.

Vsoto dolžin robov, vključenih v pot, imenujemo dolžina poti.

Upoštevajte, da če je za vse x О Х l(x) = 1, potem lahko graf štejemo za neobremenjenega.

Pot v grafu G(V, X) od točke v do točke w (v¹w) imenujemo minimalna, če ima najmanjša dolžina med vsemi potmi v grafu G(V, X) od točke v do točke w.

Omejimo se na grafe, za katere je l(x)>0.

Pri iskanju minimalne poti v naloženem grafu z l(x)>0

Uporabimo isto izjavo kot za neobremenjeni graf, in sicer:

vsaka minimalna pot je preprost krog.

Oglejmo si sedaj problem iskanja minimalne poti v naloženem grafu.

Naj bo graf G(V,X) naložen, število vozlišč n ³ 2, potrebno je zgraditi minimalno pot od v 1 do v n .

Predstavimo algoritem.

Korak 1. Vsakemu vozlišču dodelite indeks a(v i): a(v 1) = 0, a(v i) = ¥, i ¹ 1. Pobarvajte vozlišče v 1 in postavite v = v 1.

Korak 2. Za vsako nepobarvano točko v j spremenite indeks v skladu s pravilom:

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

Pobarvaj točko, za katero je a(v j) najmanjša, pobarvaj tudi rob, ki vodi do točke v j, izbrane v tem koraku. Postavite v = v j .

Korak 3. Če je v = v j, zaključimo postopek, saj je najkrajša pot od v 1 do v n. če je v ¹ v n, pojdite na 2. korak.

Komentiraj. 2. korak je nemogoč, če so vsi a(v j)= ¥. V tem primeru je oglišče v n nedosegljivo.

Uporabimo opisani algoritem na grafu, ki ga določa diagram. Poiščimo v njej najkrajšo pot od v 1 do v 6 .

Korak 1. Pobarvajte oglišče v 1 . Vozliščem priredimo indekse: a(v 1) =0, a(v 2) = a(v 3)=…= a(v n)=¥. Predpostavimo, da je 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+¥) = ¥.

Pobarvaj oglišče v 4 in rob (v 1 , v 4 ).

Korak 3. Ker oglišče v 6 ni obarvano, izvedemo korak 2 ob predpostavki, da je 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+¥) = ¥.

Pobarvaj oglišče v 2 in rob (v 1 , v 2 ).

Korak 3. Ker vozlišče v 6 ni obarvano, izvedemo korak 2 ob predpostavki, da je v = v 2.

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

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

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

Pobarvaj oglišče v 5 in rob (v 4 , v 5 ).

Korak 3. Ker oglišče v 6 ni obarvano, izvedemo korak 2 ob predpostavki, da je v = v 5 .

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

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

Pobarvaj oglišče v 3 in rob (v 1 , v 3 ).

Korak 3. Ker vozlišče v 6 ni obarvano, izvedemo korak 2 ob predpostavki, da je v = v 3 .

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

Pobarvaj oglišče v 6 in rob (v 5 , v 6 ).

Ker je oglišče v 6 obarvano, prenehamo z delom. Dobili smo minimalno pot v 1 v 4 v 5 v 6 , katere dolžina je 8 .

Upoštevajte, da v tem primeru to ni edina minimalna pot za točki v 1 in v 6, saj v algoritmu je bilo možno namesto roba (v 4, v 5) pobarvati rob (v 2, v 5), potem bi dobili drugo traso enake dolžine.

4. Težave na drevesih

Graf se imenuje acikličen, če nima ciklov.

Graf brez ciklov imenujemo gozd.

Drevo je povezan aciklični graf.

Izračunavanje razdalj in določanje poti v grafu je eden najbolj očitnih in praktičnih problemov, ki se pojavljajo v teoriji grafov. Uvedimo nekaj potrebnih definicij.

Ekscentričnost vozlišča grafa – razdalja do največjega vozlišča od njega. Za graf, za katerega ni definiran teža njegovih robov je razdalja definirana kot število robov.

Radij graf je najmanjša ekscentričnost vozlišč in premer graf – največja ekscentričnost vozlišč.

Center graf tvorijo vozlišča, katerih ekscentričnost enaka polmeru. Središče grafa je lahko sestavljeno iz ene, več ali vseh točk grafa.

Periferni oglišča imajo ekscentričnost, ki je enaka premeru.

Imenuje se preprosta veriga z dolžino, ki je enaka premeru grafa diametralno .

Izrek 12.1.V povezanem grafu premer ni večji od ranga njegove sosednje matrike.

Izrek 12.2.(Jordan) Vsako drevo ima središče, sestavljeno iz enega ali dveh sosednja oglišča.

Izrek 12.3.Če je premer drevesa sod, ima drevo eno samo središče in vse diametralne verige potekajo skozenj; če je premer liho, potem sta središči dve in vse diametralne verige vsebujejo rob, ki ju povezuje.

Očitno praktični pomen središče grafa. Če npr. govorimo o o grafu cest z mestnimi oglišči, nato v matematični center je priporočljivo postaviti upravno središče, skladišča itd. Enak pristop lahko uporabimo za uteženi graf, kjer so razdalje uteži robov. Kot težo lahko vzamete evklidsko razdaljo, čas ali stroške premikanja med točkami.

Primer 12.5. Poiščite polmer, premer in središče grafa, prikazanega na sl. 12.1.

rešitev. Pri tej nalogi je priročno uporabljati matrika razdalje S. Element te kvadratne simetrične matrike enako razdalji med vrhom i in vrh j. Za graf, prikazan na sl. 12.1 ima matrika razdalje naslednjo obliko:

. (12.2)

Izračunajmo ekscentričnost vsakega oglišča. To vrednost je mogoče definirati kot največji element ustreznega stolpca matrike razdalje (ali vrstice - saj matrika S simetrično). Dobimo

№

Polmer grafa r– najmanjša ekscentričnost oglišč. V tem primeru r= 2. Točke št. 2, št. 4 in št. 5 imajo takšno ekscentričnost. Te točke tvorijo središče grafa. Štetje premera d– največja ekscentričnost oglišč. V tem primeru d= 3. Vrhovi št. 1 in št. 3 imajo takšno ekscentričnost; to je periferija grafa. V proučevanem grafu se je izkazalo, da so vozlišča bodisi osrednja bodisi obrobna. V grafih višjega reda so še druga vozlišča.

Ekscentričnosti oglišč majhnega grafa je mogoče enostavno izračunati z neposrednim izračunom iz risbe. Vendar pa graf ni vedno opredeljen s svojo zasnovo. Poleg tega ima lahko graf velika velikost. Zato je potrebna druga rešitev prejšnja naloga. Znan je naslednji izrek.

Izrek 12.4. Naj bo matrika sosednosti grafa G brez zank in , kjer je . Potem je enako številu poti dolžine k od točke do točke.

Reševanje problemov teorije grafov z uporabo razne transformacije se imenujejo matrike sosednosti algebrska metoda .

Primer 12.6. Poiščite matriko razdalje grafa, prikazanega na sl. 12.1 z uporabo algebraične metode.

rešitev. Matrika sosednosti tega grafa je enaka:

Matriko razdalje bomo izpolnili z upoštevanjem stopenj matrike sosednosti. Enote matrike sosednosti prikazujejo pare vozlišč, ki imajo med seboj razdaljo ena (to pomeni, da so povezana z enim robom).

Diagonalni elementi matrike razdalje so ničle. Pomnožite matriko sosednosti samo s seboj:

Po izreku so med vozlišči 2 in 3, 1 in 4 itd. obstaja določeno število poti dolžine 2 (ker je stopnja matrike dve). Število poti tukaj ni uporabljeno; pomembno je samo dejstvo poti in njena dolžina, kar kaže neničelni element stopnje matrike, ki ne sovpada z elementom, zabeleženim pri izračunu poti krajša dolžina. V prazne elemente matrike razdalje vstavimo 2 in dobimo naslednji približek:

Razdalja med točkama 1 in 3 ostaja neznana na sebi do v matrici ničelni element se ne bo pojavil . Nato ustrezen element matrike razdalje enako moči matrike sosednosti: . V naslednjem koraku dobimo

V zadnjem odstavku smo poudarili, da ima matrika sosednosti $A$, ki je tam predstavljena, ali natančneje matrika sosednosti vozlišč grafa, zelo pomembno vlogo pomembno vlogo v teoriji grafov. Opazili smo prednosti te matrike - je kvadrat reda enako številu vrstic incidenčne matrike $B$, tj. praviloma vsebuje manjše število elementov. Drugič, ta matrika shranjuje vse informacije o robovih grafa in z danim oštevilčenjem vozlišč enolično opisuje graf. Matrika sosednosti je tako kot vpadna matrika grafa (0,1) matrika, tj. njegove elemente je mogoče obravnavati kot elemente drugih algebrskih struktur in ne le kot elemente množice celih števil. Zlasti smo opazili, da je elemente matrike sosednosti mogoče obravnavati kot elemente Boolove algebre, za katere veljajo zakoni Boolove aritmetike, vendar tega nismo ustrezno razložili. Preden zapolnimo to vrzel, poudarimo prednosti matrike sosednosti, ki izhajajo iz njene kvadratnosti.

Če želite to narediti, se spomnite pravil za množenje matrik. Naj sta podani poljubni matriki z numeričnimi elementi: matrika $A$ dimenzije $n\times m$ z elementi $a_(ik)$ in matrika $B$ dimenzije $m\times q$ z elementi $b_(kj)$ . Matriko $C$ z dimenzijo $n\krat q$ imenujemo produkt matrike $A$ z $B$ (vrstni red je pomemben), če so njeni elementi $c_(ij)$ definirani takole: $c_(ij ) = \vsota\meje_( k = 1)^m (a_(ik) b_(kj))$. Produkt matrik zapišemo na običajen način $AB=C$. Kot lahko vidimo, produkt matrik zahteva skladnost velikosti prvega in drugega faktorja (število stolpcev prve faktorske matrike je enako številu vrstic druge faktorske matrike). Ta zahteva izgine, če upoštevamo kvadratne matrike istega reda in zato lahko upoštevamo poljubne potence kvadratne matrike. To je ena od prednosti kvadratnih matric pred pravokotnimi. Druga prednost je, da lahko podamo grafično interpretacijo stopenjskih elementov matrike sosednosti.

Naj ima matrika sosednosti $A$ obliko: $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)$ in njena $k$ta stopnja — $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(matrika) )) \right)$ , kjer je $k = 2,3,...$ Očitno bo $A^k$, tako kot matrika $A$, simetrična matrika.

Naj bo $k=2$. Potem je $a_(ij)^((2)) = \sum\limits_(k = 1)^n (a_(il) a_(lj))$ ($i,j = 1,2,...,n $), vsak izraz $a_(il) a_(lj)$ pa je enak $0$ ali $1$. Primer, ko je $a_(il) a_(lj) = 1$, pomeni, da sta v grafu dva roba: rob $$i,l$$ (ker je $a_(il) = 1)$ in rob $$ l,j$$ (ker je $a_(lj) = 1$) in torej pot $$( \(i,l$, $l,j$ )\)$ od $i $-to oglišče do $j$to oglišče dolžine dve (pot dveh robov). Tu govorimo o poti, ne o verigi, saj je prikazana smer od $i$te točke do $j$te točke. Tako nam $a_(ij)^((2))$ podaja število vseh poti na grafu (v geometrijski interpretaciji grafa) dolžine 2, ki vodijo od $i$te vozlišča do $j$te vertex.

Če je $k=3$, potem je $A^3 = A^2A = AA^2 = AAA$ in $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) = \vsota\meje_(l_1 ,l_2 = 1)^n (a_(il_1 ) a_(l_1 l_2 ) a_(l_2 j) )$.

Izraz $a_(il_1 ) a_(l_1 l_2 ) a_(l_2 j) $, če je enak 1, določa pot dolžine 3, ki poteka od $i$-tega oglišča do $j$-tega in poteka skozi točki $l_1$ in $l_2$. Nato nam $a_(ij)^((3))$ poda število poti dolžine 3, ki povezujejo $i$to in $j$to točko. Na splošno $a_(ij)^((k))$ podaja število poti dolžine $k$, ki povezujejo $i$-to in $j$-to vozlišče. V tem primeru je $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)$.

Jasno je, da nam količina $a_(ii)^((k)) $ podaja število zaprtih poti dolžine $k$, ki se začnejo in končajo v točki $i$. Torej pot dolžine 2 - $a_(il) a_(li)$, pomeni pot, ki poteka vzdolž roba $$ i,l $$ od oglišča $i$ do oglišča $l$ in nazaj. Zato $a_(ii)^((2)) = s_i$, tj. diagonalni elementi matrike $A^2$ so enaki stopinjam ustreznih oglišč.

Oglejmo si zdaj poleg matrike $A$ še matriko $\dot (A)$, ki se od matrike $A$ razlikuje le po tem, da se njeni elementi (števili 0 ali 1) obravnavajo kot elementi Boolove algebre. Zato bodo dejanja s takšnimi matrikami izvedena v skladu s pravili Boolove algebre. Ker so dejanja seštevanja in množenja matrik z logičnimi elementi zmanjšana na dejanja seštevanja in množenja elementov teh matrik v skladu s pravili logične aritmetike, upamo, da to ne bo povzročilo težav. Matriko z logičnimi elementi bomo imenovali logična matrika. Očitno je, da sta operaciji seštevanja in množenja Boolovih matrik zaprti na množici Boolovih matrik, tj. rezultat teh operacij bo spet logična matrika.

Očitno je, da za dano oštevilčenje vozlišč obstaja ujemanje ena proti ena med logičnimi matrikami sosednosti in grafi. Zato je zanimiva grafična interpretacija dejanj seštevanja in potenciranja Boolovih sosednjih matrik (v splošnem primeru produkt dveh simetričnih matrik istega reda ni nujno simetrična matrika).

Rezultat seštevanja dveh logičnih simetričnih matrik istega reda bo logična simetrična matrika istega reda z ničlami na tistih mestih, kjer imata oba člena ničle, in enicami na tistih mestih, kjer ima vsaj en člen enoto. V interpretaciji grafa se ta operacija imenuje operacija dodajanje grafov. Vsota dveh grafov, podan na isti množici vozlišč z enakim oštevilčenjem, se imenuje graf, katerega točki i in j nista sosednji, če nista sosednji v obeh komponentah grafa, in točki i in j sta sosednji, če sta sosednji v pri vsaj en grafični člen.

Razložimo zdaj drugo stopnjo logične matrike sosednosti $\dot (A)^2$ z elementi $\dot (a)_(ij)^((2)) = \sum\limits_(l = 1)^ n (\pika ( a)_(il) \pika (a)_(lj) )$. Jasno je, da je $\dot (a)_(ij)^((2)) = 1$, če je vsaj en člen $\dot (a)_(il) \dot (a)_(lj) $ enak na 1 in $\dot (a)_(ij)^((2)) = 0$, če so vsi členi enaki 0. Če je matrika $\dot (A)$ matrika sosednosti nekega grafa, tj. je simetrična (0,1) matrika z ničelno glavno diagonalo, potem matrika $\dot (A)^2$ na splošno ni sosednja matrika grafa v sprejetem smislu, saj vsi njeni diagonalni elementi so enaki 1 (če graf nima izoliranih vozlišč). Da lahko na takšne matrike gledamo kot na matrike sosednosti, moramo pri obravnavi povezav med vozlišči nekega povezanega sistema, ki ta sistem definirajo kot graf, dovoliti, da so nekatera vozlišča povezana sama s seboj. Imenuje se "rob", ki določa povezavo določenega vozlišča s samim seboj zanka. Nadalje, kot prej, bomo z besedo graf razumeli graf brez zank, o grafu z zankami, če to iz konteksta ni jasno, pa bomo rekli tako - graf z zankami.

Upoštevajte vsoto $\dot (A)^() = \dot (A) + \dot (A)^2$. Matrika $\dot (A)^()$ nam daje graf, ki ga dobimo iz prvotnega tako, da ga »nasičimo« z dodatnimi povezavami, ki ustrezajo poti dolžine 2. To pomeni, da sta v novem grafu točki $i$ in $ j$ so sosednje, če so sosednje v izvirnem grafu ali pa so te točke povezane z neko potjo dolžine 2, točki $i$ in $j$ pa sta nesosednji, če sta nesosednji v izvirnem grafu in tam ni poti dolžine 2, ki bi povezovala ta oglišča.

$\dot (A)^() = \dot (A) + \dot (A)^2 + \dot (A)^3$ je definiran podobno. To pomeni, da sta v grafu, definiranem z matriko $\dot (A)^()$, točki $i$ in $j$ sosednji, če sta sosednji v grafu $\dot (A)^()$ ali teh vozlišča so povezana na nek način dolžine 3 v izvirnem grafu, točki $i$ in $j$ pa sta nesosednji, če nista sosednji v grafu $\dot (A)^()$ in ni poti dolžine 3 povezovanje teh vozlišč v izvirnem grafu. In tako dalje.

Na splošno je $\dot (A)^([k]) = \sum\limits_(i = 1)^k (\dot (A)^i) $. Preprosto je videti, da so vsi $\dot (A)^([k])$ za $k \ge n - 1$, kjer je $n$ vrstni red matrike $\dot (A)$, enaki drug drugemu. Dejansko, če sta točki $i$ in $j$ povezani, potem obstaja pot (veriga), ki povezuje ti točki, in zato obstaja preprosta pot (preprosta veriga), ki povezuje ta točki. Največja možna enostavna pot v $n$-vozliščnem grafu ima dolžino $n-1$ (preprosta pot, ki povezuje vsa različna oglišča grafa). Če je torej v matriki $\dot (A)^()$ 1 na mestu $(i,j)$, potem je na istem mestu v matriki $\dot (A)^([k] )$ pri $k \ge n - 1$ bo prav tako 1, ker je matrika $\dot (A)^()$ vključena kot Boolov izraz v definiciji matrike $\dot (A)^([ k])$. Če je v matriki $\dot (A)^()$ namesto $(i,j)$ 0, potem to pomeni, da v grafu ni preproste verige, ki povezuje $i$-to in $j $- oglišča, zato ta oglišča sploh ne povezujejo. To pomeni, da bo v obravnavanem primeru in v matriki $\dot (A)^([k])$ za $k \ge n - 1$ na mestu ($i$,$j)$ 0. To dokazuje naša izjava o enakosti vseh matrik $\dot (A)^([k])$ za $k \ge n - 1$ matriki $\dot (A)^()$ in torej , drug drugemu.

Imenuje se matrika $\dot (A)^()$ matrika tranzitivnega zaprtja matrike$\dot (A)$, kot tudi matriko sosednosti tranzitivnega zaprtja grafa, definiranega z matriko $\dot (A)$. Povsem očitno je, da bo tranzitivna zaprta matrika povezanega grafa matrika sosednosti celotnega grafa, tj. kvadratna matrika, sestavljena samo iz enic. Ta ugotovitev nam daje tudi metodo za določanje povezljivosti grafa: graf je povezan, če in samo če je matrika tranzitivnega zaprtja njegove matrike sosednosti sestavljena samo iz enic (bo matrika popolnega grafa).

Tranzitivna zaprta matrika nam omogoča tudi rešitev problema razdelitve grafa na povezane komponente.

Zdaj pa pokažimo, kako nam postopek tranzitivnega zapiranja omogoča sestavo tako imenovane "matrike razdalje". Da bi to naredili, določimo razdaljo med točkama $i$ in $j$. Če sta točki $i$ in $j$ povezani, potem oddaljenost med njimi imenujemo dolžino najmanjše (glede na število prevoženih robov) enostavne poti, ki povezuje ta oglišča; če sta točki $i$ in $j$ nepovezani, potem nastavimo razdaljo enako nič (nič kot negacija katerekoli poti, ki povezuje ti točki). Pri tej definiciji razdalje je razdalja med točko in samim seboj enaka 2 (dolžina poti po robu in nazaj). Če je na točki zanka, je razdalja med točko in samim seboj enaka 1.

Za sestavo matrike razdalje za $n$-vozliščni graf z matriko sosednosti $A$, ki bi kazala razdaljo med katerima koli dvema vozliščema, uvedemo v obravnavo matrike $A^($k$) = A^ ([k]) - A^()$, kjer je $k = 2,3,...,n - 1$ in $A^($1$) = A^() = A$. Odsotnost pik nad oznako matrike pomeni, da matrike $A^([k])$ ($k = 1,2,...,n - 1)$ obravnavamo kot numerične (0,1)-matrike, naravno pridobljeno iz matrik $\dot (A)^([k])$ (zdaj obravnavamo logična elementa 0 in 1 kot števili 0 in 1). Iz metode konstruiranja matrik $A^([k])$ sledi $A^([k]) \ge A^()$ ($k = 2,3,...,n - 1$) in zato so $A^($k$)$ ($k = 1,2,...,n - 1$) (0,1)-matrike. Še več, matrika $A^($2$)$ vsebuje 1 le na tistih mestih, kjer so vozlišča, določena s tem mestom (številka vrstice in številka stolpca), povezana z neko potjo dolžine dva in niso povezana s krajšo pot. Podobno $A^($3$)$ vsebuje 1 samo na tistih mestih, kjer so vozlišča, ki jih določa to mesto, povezana s potjo dolžine tri in niso povezana z nobeno krajšo potjo itd. Tako bo matrika $D = \sum\limits_(k = 1)^(n - 1) (k \cdot A^($k$))$ zahtevana matrika razdalje. Element $d_(ij)$ te matrike bo enak razdalji med točkama $i$ in $j$. Razdaljo med točkama $u$ in $v$ bomo označili tudi kot $d(u,v)$.

Komentiraj. Specifični proizvodni izraz $a_(il_1 ) a_(l_1 l_2 ) ...a_(l_(k - 2) l_(k - 1) ) a_(l_(k - 1) j) = 1$ element $a_(ij ) ^((k))$ $k$-te potence matrike sosednosti $A^k$ podaja določeno $(i,j)$-pot $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$ od $i$ -te točke do $j$-te. Zaporedje sosednjih vozlišč in robov, ki jih povezujejo $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$ se imenuje tudi $(i,j)$-pot. Pot se razlikuje od verige, ki je sestavljena samo iz različnih sosednjih robov, v tem, da pot omogoča enaki robovi. Preprosta pot je sestavljena iz različnih sosednjih vozlišč in robov, tj. praktično sovpada s preprosto verigo.

Povsem očitno je, da element $d_(ij) $ matrike razdalje določa dolžino minimalne verige, ki povezuje $i$to točko z $j$to točko.

Oglejmo si primere grafov, prikazanih na slikah 1 in 2, njihove matrike sosednosti in njihove matrike razdalje.

Slika 1 (graf $\Gamma _1$, matrika sosednosti $A_1$, matrika razdalje $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(matrika) )) \desno), $
$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 & 1 & 1 & 1 & 1 & 2 & 2 \\ 2 & 2 & 1 & 2 & 1 & 2 & 2 & 2 & 2 & 1 & 2 & 2 & 2 \\ \end(matrika) )) \desno) $

riž. 2 (graf $\Gamma _2$, matrika sosednosti $A_2$, matrika razdalje $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(matrika) )) \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(matrika) )) \desno). $

Iz matrik $D_1$ in $D_2$ lahko enostavno ugotovimo premeri$d_1$ grafa $\Gamma _1$ in $d_2$ grafa $\Gamma _2$ kot največje vrednosti elementov teh matrik. Torej $d_1 = 3$ in $d_2 = 6$.

Teorija grafov poleg matrike razdalje upošteva tudi druge matrike, katerih elementi so določeni preko dolžine poti. To je na primer matriko prečkanja. IN matriko prečkanja$(i,j)$-ti element enaka dolžini najdaljšo pot (najdaljšo verigo) od $i$te točke do $j$to točke, in če teh poti sploh ni, potem je v skladu z definicijo razdalje $(i,j)$ element matrike prečkanja je enak nič.

Na koncu razdelka bomo zapisali metode za določanje minimalnih in maksimalnih verig z uporabo matrike razdalj, ki povezuje $i$-to in $j$-to točko v grafu.

Zdaj pa podajmo še nekaj definicij teorije grafov, povezanih z razdaljami med vozlišči in ki jih je enostavno določiti iz matrik razdalj.

Ekscentričnost$e(v)$ vozlišča $v$ v povezanem grafu $\Gamma$ je definirano kot max $d(u,v)$ nad vsemi vozlišči $u$ v $\Gamma$. Radij$r(\Gamma)$ je najmanjša ekscentričnost oglišč. Upoštevajte, da je največja ekscentričnost enaka premeru grafa. Oglišče $v$ se imenuje osrednje oglišče grafa $\Gamma$, če je $e(v) = r(\Gamma)$; center graf $\Gamma$ je množica vseh središčnih vozlišč.

Torej bo za graf $\Gamma _1$ s slike 1 ekscentričnost oglišča 13 enaka 2 ($e(13) = 2$). Vrhovi 3, 5 in 10 bodo imeli enake ekscentričnosti ($e(3) = e(5) = e(10) = 2$). Ekscentričnost, enaka 2, bo najmanjša za graf $\Gamma _1$, tj. $r(\Gama _1) = 2$. Središče grafa $\Gamma _1$ bo sestavljeno iz vozlišč 3, 5, 10 in 13. Največja ekscentričnost bo enaka 3 in bo enaka, kot je navedeno zgoraj, premeru grafa $\Gamma _1$ .

Za graf $\Gamma _2$ s sl. 2, bo imelo edino oglišče 4 najmanjšo ekscentričnost ($e(4) = r(\Gamma _2) = 3$). Posledično je središče grafa $\Gamma _2$ sestavljeno iz ene točke 4. Premer grafa $\Gamma _2$ je, kot je navedeno zgoraj, 6.

Graf $\Gamma _2$ je drevo, struktura središča katerega koli drevesa pa je opisana s spodnjim izrekom.

Jordan–Sylvester izrek. Vsako drevo ima središče, sestavljeno iz ene vozlišča ali dveh sosednjih vozlišč.

Dokaz. Z $K_1$ označimo graf, sestavljen iz ene izolirane vozlišča, z $K_2$ pa graf, sestavljen iz dveh vozlišč, povezanih z robom. Po definiciji postavimo $e(K_1) = r(K_1) = 0$. Potem bo izrek veljal za $K_1$ in $K_2$. Pokažimo, da ima vsako drevo $T$ enaka osrednja oglišča kot drevo $(T)"$, ki ga dobimo iz $T$ z odstranitvijo vseh njegovih visečih oglišč. Jasno je, da je razdalja od danega oglišča $u$ do poljubne drugo točko, ki jo $v$ lahko doseže najvišjo vrednost samo, če je $v$ viseče oglišče.

Tako je ekscentričnost vsakega oglišča drevesa $(T)"$ natanko ena manjša od ekscentričnosti istega oglišča v $T$. Iz tega sledi, da so oglišča drevesa $T$, ki imajo najmanjšo ekscentričnost v $ T$ sovpadajo z vozlišči, ki imajo najmanjšo ekscentričnost v $(T)"$, tj. središči dreves $T$ in $(T)"$ sovpadata. Če nadaljujemo s postopkom odstranjevanja visečih oglišč, bomo dobili zaporedje dreves z enakim središčem kot pri $T$. Ker je $T$ končna, bomo nujno prišli bodisi do $K_1$ bodisi do $K_2$. V vsakem primeru pa vsa tako dobljena oglišča drevesa tvorijo središče drevesa, ki je torej sestavljeno iz ene same oglišča oz. dve sosednji točki.

Pokažimo zdaj, kako lahko z uporabo matrike razdalje določimo na primer minimalno verigo, ki povezuje točko 4 z točko 8 na grafu $\Gamma _1$. V matriki $D_1$ je element $d_(48) = 3$. Vzamemo 8. stolpec matrike $D_1$ in v stolpcu poiščemo vse elemente tega stolpca enake 1. Zaradi povezanosti grafa $D_1$ bomo našli vsaj enega takega elementa. Pravzaprav bodo v 8. stolpcu tri takšne enote, ki se nahajajo v 5., 6. in 7. vrstici. Vzemimo zdaj 4. vrstico in poglejmo elemente v njej, ki se nahajajo v 5., 6. in 7. stolpcu. Ti elementi bodo 2, 3 in 3. Samo element, ki se nahaja v 5. stolpcu, je enak 2 in skupaj z 1, ki se nahaja na mestu (5,8), daje vsoto 3. To pomeni, da je oglišče 5 vključeno v verigo $$ \(4, ?$, $? ,5$, $5,8$ \)$. Vzemimo zdaj 5. stolpec matrike in razmislimo o 1 od tega stolpca. To bodo elementi, ki se nahajajo v 3., 6., 7., 8., 10. in 13. vrstici. Ponovno se vrnemo v 4. vrstico in vidimo, da je le na presečišču tretjega stolpca in 4. vrstice 1, kar v kombinaciji z 1 na mestu (3.5) daje skupno 2. Zato bo želena veriga biti $$ \ (4,3$, $3,5$, $5,8$ \)$. Ko smo zdaj pogledali sliko 1, smo prepričani o veljavnosti najdene rešitve.

Čeprav o matriki prečkanja sodobnih učbenikov pravijo, da "ni učinkovitih metod za iskanje njegovih elementov", spomnimo se, da lahko z uporabo incidenčne matrike najdemo vse verige, ki povezujejo par vozlišč v povezanem grafu, torej verige največje dolžine.

Izračunavanje razdalj in določanje poti v grafu je eden najbolj očitnih in praktičnih problemov, ki se pojavljajo v teoriji grafov. Uvedimo nekaj potrebnih definicij.

Ekscentričnost vozlišča grafa – razdalja do največjega vozlišča od njega. Za graf, za katerega ni definiran teža njegovih robov je razdalja definirana kot število robov.

Radij graf je najmanjša ekscentričnost vozlišč in premer graf – največja ekscentričnost vozlišč.

Center Graf tvorijo vozlišča, katerih ekscentričnost je enaka polmeru. Središče grafa je lahko sestavljeno iz ene, več ali vseh točk grafa.

Periferni oglišča imajo ekscentričnost, ki je enaka premeru.

Imenuje se preprosta veriga z dolžino, ki je enaka premeru grafa diametralno .

Izrek 12.1.V povezanem grafu premer ni večji od ranga njegove sosednje matrike.

Izrek 12.2.(Jordan) Vsako drevo ima središče, sestavljeno iz ene ali dveh sosednjih oglišč.

Praktični pomen središča grafa je očiten. Če na primer govorimo o grafu cest z mestnimi vozlišči, potem je priporočljivo v matematično središče postaviti upravno središče, skladišča itd. Enak pristop lahko uporabimo za uteženi graf, kjer so razdalje uteži robov. Kot težo lahko vzamete evklidsko razdaljo, čas ali stroške premikanja med točkami.

Primer 12.5. Poiščite polmer, premer in središče grafa, prikazanega na sl. 12.1.

rešitev. Pri tej nalogi je priročno uporabljati matrika razdalje S. Element te kvadratne simetrične matrike je enak razdalji med oglišči i in vrh j. Za graf, prikazan na sl. 12.1 ima matrika razdalje naslednjo obliko:

Izračunajmo ekscentričnost vsakega oglišča. To vrednost je mogoče definirati kot največji element ustreznega stolpca matrike razdalje (ali vrstice - saj matrika S simetrično). Dobimo

Ekscentričnosti oglišč majhnega grafa je mogoče enostavno izračunati z neposrednim izračunom iz risbe. Vendar pa graf ni vedno opredeljen s svojo zasnovo. Poleg tega je lahko graf velik. Zato je potreben drug način za rešitev prejšnjega problema. Znan je naslednji izrek.

Izrek 12.4. Naj bo matrika sosednosti grafa G brez zank in , kjer je . Potem je enako številu poti dolžine k od točke do točke.

Reševanje problemov teorije grafov z uporabo različnih transformacij matrike sosednje se imenuje algebrska metoda .

Primer 12.6. Poiščite matriko razdalje grafa, prikazanega na sl. 12.1 z uporabo algebraične metode.

rešitev. Matrika sosednosti tega grafa je enaka:

Diagonalni elementi matrike razdalje so ničle. Pomnožite matriko sosednosti samo s seboj:

Razdalja med točkama 1 in 3 ostaja neznana na sebi do v matrici ničelni element se ne bo pojavil . Potem je ustrezen element matrike razdalje enak stopnji matrike sosednosti: . V naslednjem koraku dobimo

torej, , in končno

Dobljena matrika sovpada z matriko razdalje S(12.2), ugotovljeno z neposrednimi izračuni iz slike.

Na podlagi obdelanih podatkov je mogoče zgraditi več modelov.

Pravokotna realna matrika

Po obdelavi podatkov smo dobili pravokotno realno matriko. Ta matrika odraža informacije o skupni vrednosti pogodb, sklenjenih v m regijah (spomnimo se, da je m = 86) za n razredov klasifikatorja OKPD (vse pogodbe so bile izvedene z uporabo 62 različnih kod klasifikatorjev). Torej je nastala matrika sestavljena iz m n-dimenzionalnih vektorjev.

Elementi matrike imajo močan razpon v območju od 0 do rubljev. Tako velik razpon lahko povzroči težave pri nadaljnji analizi podatkov. Poleg tega so nekateri klasifikatorji »popularni« in se uporabljajo za pogoste in velike količine nakupov, kot na primer za kodo klasifikatorja 45. Hkrati pa šifra klasifikatorja 12 (uranove in torijeve rude) vsebuje zelo redke nakupe za majhne količine. V zvezi z navedenim je pomembno nekako izenačiti prispevek teh količin in podatke normalizirati. Normalizacija podatkov je postopek spreminjanja izvirnih podatkov in njihovega spravljanja v brezdimenzijsko obliko. Ta proces vodi do izboljšane kakovosti podatkov.

Za normalizacijo te matrike lahko izberete eno od naslednjih metod: normalizacija v delih skupni znesek pogodbe za posamezno regijo, normalizacija v deležih skupnega zneska za posamezno oznako klasifikatorja, prebivalstvo regije.

1) Normalizacija po regijah

Za poljubno regijo je treba ugotoviti delež udeležbe posameznega klasifikatorja pri oblikovanju zneska pogodbene vrednosti v regiji i.

2) Normalizacija s kodami klasifikatorjev

Za poljubno šifro klasifikatorja ugotovitev deleža udeležbe posamezne regije pri oblikovanju višine pogodbene vrednosti po šifrah klasifikatorja j.

3) Normalizacija po številu regij

Vsak element matrike je treba deliti s prebivalstvom ustrezne regije.

Upoštevate lahko tudi standardne metode normalizacije podatkov:

1) Mini-max linearna normalizacija

kje je minimum in največja vrednost stroški za vsako regijo i v vektorju.

Ta normalizacija pripelje vse podatke na vrednosti v razponu.

2) Redukcija na porazdelitev tipa N (standardizacija podatkov)

kje je matematika. pričakovanje,

standardni odklon vektorja.

3) Nelinearna normalizacija

Ta metoda temelji na nelinearnem razmerju med izvirnimi in normaliziranimi podatki. Treba je izbrati določeno podatkovno matriko, jo poimenovati normalizirano in na njeni podlagi zgraditi normalizacijsko funkcijo. Vse druge podatke je treba normalizirati v skladu s to funkcijo.

Kvadratna matrika razdalje

Iz pravokotne realne matrike lahko preidemo na matriko razdalj med regijami. To bo kvadratna matrika velikosti. Razdaljo je mogoče izračunati z eno od naslednjih metrik.

Oglejmo si najpogostejše meritve:

1) Evklidska razdalja

Najpogostejša metrika je geometrijska razdalja v večdimenzionalnem prostoru.

2) metrika Minkowskega

Tako imenovana razdalja moči. V tem primeru je r odgovoren za tehtanje velikih razlik v razdaljah, p pa za tehtanje razlik v koordinatah. Upoštevajte, da ko r, p=2 sovpada z evklidsko razdaljo.

3) Manhattanska metrika

Imenuje se tudi metrika mestnih blokov. Izračuna se kot povprečna razlika koordinat. Običajno daje rezultate, podobne evklidski razdalji, vendar ima prednost pri vzorcih z velike vrednosti emisije.

4) Kosinusna podobnost

Ta ukrep je učinkovit za redke vektorje, ker se štejejo samo neničelne vrednosti. Ta metoda se lahko uporabi, če se prvotna realna matrika transformira (podatki so odrezani pri določenem pragu) in postane bolj redka.

5) Hammingova razdalja

Je poseben primer metrike Minkowskega in se uporablja za binarne vektorje. Da bi uporabili to razdaljo pri izračunu matrike razdalje v tem problemu, je treba zmanjšati začetno realno matriko na binarno (z uvedbo določenega praga).

Graf bližine

Graf bližine velikosti je izpeljan iz matrike razdalje na podlagi nekega praga ali stopnje oglišč. Ker matrika razdalje ni redka, lahko upoštevamo določene pragove, na primer prvih 5 elementov v vsaki vrstici (za vsako kodo klasifikatorja) ali prvih 5 v stolpcih (za vsako regijo). Na ta način lahko pridobite redko matriko, ki vam bo omogočila jasnejšo vizualizacijo rezultatov.

Zgoraj opisani modeli so univerzalni v okviru obravnavanega problema.

Prvič, uporabiti jih je mogoče za podatke ne samo za leto 2015, ampak tudi za katero koli obdobje.

Drugič, z uporabo različnih rezov in različnih pragov lahko greste na podobne matrice, kar pomeni, da lahko ta model uporabite večkrat glede na različne situacije.

IN ta del Opisani so trije matematični modeli. Od realno ovrednotenih pravokotna matrika mogoče dobiti kvadratna matrika razdalje Zgoraj opisane metrike se lahko uporabljajo kot merilo razdalje. Iz matrike razdalje je mogoče dobiti redek graf bližine z uvedbo določenih pragov in/ali omejitev.