Razmerje dosegljivosti grafičnih modulov. Digrafi in binarne relacije

Obravnavana so vprašanja dosegljivosti digrafov in metode iskanja matrik dosegljivosti in protidosegljivosti. Upošteva se matrična metoda za iskanje števila poti med poljubnimi vozlišči grafa, kot tudi iskanje niza točk, vključenih v pot med parom vozlišč. Namen predavanja: Podati predstavo o dosegljivosti in protidosegljivosti ter kako ju najti

Dosegljivost in protidosegljivost

Naloge, v katerih se uporablja koncept dosegljivost, kar nekaj.

Tukaj je eden od njih. Graf je lahko model neke organizacije, v kateri so ljudje predstavljeni z oglišči, loki pa interpretirajo komunikacijske kanale. Pri obravnavi takega modela se lahko vprašamo, ali je mogoče informacije iz ene osebe i prenesti na drugo osebo j, tj. ali obstaja pot, ki gre od tock i do tock j. Če taka pot obstaja, pravimo, da so vozlišča j dosegljivo iz oglišč i. Zanima nas lahko dosegljivost točk j iz točk i samo na poteh, katerih dolžine ne presegajo dane vrednosti ali katerih dolžina je manjša od največjega števila točk v grafu itd. problema.

Dosegljivost v grafu je opisana z matriko dosegljivosti R=, i, j=1, 2, ... n, kjer je n število vozlišč grafa, vsak element pa je definiran na naslednji način:

r ij =1, če so vozlišča j dosegljiva iz x i,

r ij =0, drugače.

Množica tock R(x i) grafa G, dosegljivih iz dane tocke x i, je sestavljena iz elementov x i, za katere je (i, j)-ti element v matriki dosegljivosti enak 1. Ocitno je, da so vse diagonale elementi v matriki R enaki 1, ker je vsako vozlišče dosegljivo iz sebe po poti dolžine 0. Ker je neposredna preslikava prvega reda Г +1 (x i) množica takšnih vozlišč x j, ki so dosegljiva iz x i z uporabo poti dolžine 1, potem je množica G + (Г +1 (x i)) = Г +2 (x i) sestavljena iz tock, dosegljivih iz x i z uporabo poti dolžine 2. Podobno je r + p (x i) množica tock ki so dosegljive iz x i z uporabo poti dolžine p.

Ker mora biti katera koli vozlišča grafa, ki je dosegljiva iz x i, dosegljiva z uporabo poti (ali poti) dolžine 0 ali 1, ali 2, ... ali p, potem lahko nabor vozlišč, dosegljivih za točko x i, predstavimo kot

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

Kot lahko vidite, je množica dosegljivih vozlišč R(x i) neposredna tranzitivna zapora vozlišča x i, tj. R(x i) = T + (x i). Zato za sestavo matrike dosegljivosti najdemo dosegljive množice R(x i) za vsa vozlišča x i X. Nastavitev r ij =1, če je x j R(x i), in r ij =0 drugače.

riž. 4.1. Dosegljivost v grafu: a - graf; b – matrika sosednosti; c – matrika dosegljivosti; r je matrika nasprotne dosegljivosti.

Za graf, prikazan na sl. 4.1, a, dosegljivi nizi se nahajajo na naslednji način:

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 ).

Matrika dosegljivosti ima obliko, kot je prikazano na sl. 4.1, c. Matrika dosegljivosti se lahko zgradi glede na matriko sosednosti(sl. 4.1b), ki tvori množice T + (x i) za vsako vozlišče x i.

Matrika nasprotne dosegljivosti Q = [ q ij ],i, j =1, 2, ... n, kjer je n število vozlišč grafa, je definiran kot sledi:

q ij =1, če je iz točke x j možno doseči točko x i ,

q ij =0, drugače.

izpodbojno množica Q (x i) je množica oglišč takih, da je iz katerega koli oglišča te množice možno doseči oglišče x i . Podobno kot pri konstrukciji dosegljive množice R (x i), lahko zapišemo izraz za Q (x i):

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

Tako je jasno, da Q (x i) ni nič drugega kot obratno tranzitivno zaprtje oglišča x i, tj. Q (x i) = T - (x i). Iz definicij je očitno, da stolpec x i matrike Q (v katerem je q ij =1, če je x j Q (x i), in q ij =0 sicer) sovpada z vrstico x i matrike R, tj. Q = RT, kjer je RT matrika, transponirana v matriko dosegljivosti R.

Matrika nasprotne dosegljivosti prikazano na sl. 4.1, g.

Upoštevati je treba, da ker so vsi elementi matrik R in Q enaki 1 ali 0, je mogoče vsako vrstico shraniti v binarni obliki, kar prihrani stroške računalniškega pomnilnika. Matrike R in Q so primerne za obdelavo na računalniku, saj so z računalniškega vidika glavne operacije hitre logične operacije.

Iskanje nabora vozlišč, vključenih v pot

Če morate vedeti o vozliščih grafa, vključenih v te poti, potem si morate zapomniti definicije direktnih in inverznih tranzitivnih zaprtij. Ker je T + (x i) množica oglišč, do katerih vodijo poti iz oglišča x i, T - (x j) pa je množica oglišč, iz katerih vodijo poti do x j, potem je T + (x i) T - (x j ) je množica vozlišč, od katerih vsako pripada vsaj eni poti, ki gre od x i do x j. Ta oglišča se imenujejo bistvena ali integralna glede na obe končni točki x i in x j . Vse druge točke grafa imenujemo nepomembne ali redundantne, saj njihova odstranitev ne vpliva na poti od x i do x j.

riž. 4.2. digraf

Torej za graf na sl. 4.2 iskanje oglišč, vključenih v pot, na primer od oglišča x 2 do oglišča 4, se zmanjša na iskanje 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) in njihova presečišča T + (x 2) T - (x 4) \u003d ( x 2, x 3, x 4, x 5 ).

Matrična metoda za iskanje poti v grafih

Matrika sosednosti v celoti definira strukturo grafa. Kvadriramo matriko sosednosti po pravilih matematike. Vsak element matrike A 2 je določen s formulo

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

Izraz v formuli je enak 1, če in samo če sta obe števili a ij in a jk enaki 1, sicer pa je enak 0. Ker enakost a ij = a jk = 1 implicira obstoj poti dolžine 2 od oglišča x i do oglišč k, ki potekajo skozi oglišče x j , potem je (i -th,k-th) element matrike A 2 enak številu poti dolžine 2, ki gredo od x i do k .

Tabela 4.1a prikazuje matriko sosednosti grafa, prikazanega na sl. 4.2. Rezultat kvadriranja matrike sosednosti A 2 je prikazan v tabeli 4.1b.

Torej "1", ki stoji na presečišču druge vrstice in četrtega stolpca, označuje obstoj ene poti dolžine 2 od oglišča x 2 do oglišča 4 . Dejansko, kot vidimo v stolpec na sl. 4.2 obstaja taka pot: a 6 , a 5 . "2" v matriki A 2 označuje obstoj dveh poti dolžine 2 od tock 3 do tock 6: a 8 , a 4 in a 10 , a 3 .

Podobno je za matriko sosednosti, dvignjeno na tretjo potenco A 3 (tabela 4.1c), a (3) ik enako številu poti dolžine 3, ki gredo od x i do x k . Iz četrte vrstice matrike A 3 je razvidno, da obstajajo poti dolžine 3: ena od x 4 v 4 (a 9 , a 8 , a 5), ​​ena od x 4 v

x 5 (a 9, a 10, a 6) in dve poti od x 4 v 6 (a 9, a 10, a 3 in a 9, a 8, a 4). Matrika A 4 prikazuje obstoj poti dolžine 4 (tabela 4.1d).

Torej, če je p ik element matrike A p, potem je p ik enak številu poti (ni nujno ali verig ali enostavnih ali verig) dolžine p, ki gredo od x i do x k.

Problemov, pri katerih se uporablja koncept dosegljivosti, je kar nekaj. Tukaj je eden od njih. Graf je lahko model nekakšne organizacije, v kateri so ljudje predstavljeni z vozlišči, loki pa interpretirajo komunikacijske kanale. Pri obravnavi takega modela se lahko pojavi vprašanje, ali je mogoče informacije z ene osebe x i prenesti na drugo osebo x j, tj. ali obstaja pot, ki gre od vrha x i do vrha x j. Če taka pot obstaja, pravimo, da je oglišče x j dosegljivo iz oglišča x i . Dosegljivost oglišča x j iz oglišča x i nas lahko zanima le na takšnih poteh, katerih dolžine ne presegajo dane vrednosti ali je dolžina manjša od največjega števila oglišč v grafu itd. težava.

Dosegljivost v grafu je opisana z matriko dosegljivosti R=, i, j=1, 2, ... n, kjer je n število vozlišč grafa, vsak element pa je definiran na naslednji način:

r ij =1, če je oglišče x j dosegljivo iz x i,

r ij =0, drugače.

Veliko vrhov R(x i) grafa G , ki je dosegljiv iz danega vozlišča x i , je sestavljen iz elementov x j, za katere je (i, j) -ti element v matriko dosegljivosti je enako 1. Očitno so vsi diagonalni elementi v matriki R enaki 1, saj je vsako vozlišče dosegljivo iz sebe po poti dolžine 0. Ker neposredni prikaz 1. red Г +1 (x i) je množica takšnih vozlišč x j, ki so dosegljiva iz x i z uporabo poti dolžine 1, potem je množica G + (G +1 (x i)) = G +2 (x i) je sestavljen iz vozlišč, ki so dosegljiva iz x i z uporabo poti dolžine 2. Podobno je r+p(x i) množica vozlišč, ki so dosegljiva iz x i z uporabo poti dolžine p.

Ker mora biti vsako vozlišče grafa, ki je dosegljivo iz x i , dosegljivo z uporabo poti (ali poti) dolžine 0 ali 1 ali 2, ... ali p, potem veliko vozlišč dosegljivo za točko x i lahko predstavimo kot

Kot lahko vidite, je množica dosegljivih vozlišč R(x i) direkt prehodno zaprtje oglišča x i , tj. R (x i) = T + (x i) . Zato za sestavo matrike dosegljivosti najdemo dosegljive množice R (x i) za vse vozlišča. Ob predpostavki, da je r ij =1, če in r ij =0 drugače.

Za graf, prikazan na sl. 4.1,a so dosegljive množice najdene na naslednji način:

Matrika dosegljivosti ima obliko, kot je prikazano na sl. 4.1, c. Matrika dosegljivosti se lahko sestavi iz matrike sosednosti (slika 4.1, b), ki tvori nize T + (x i) za vsako vozlišče x i .

Matrika nasprotne dosegljivosti Q = [q ij], i, j =1, 2, ... n, kjer je n število vozlišč grafa, je definiran kot sledi:

q ij =1, če je iz oglišča x j mogoče doseči oglišče x i,

q ij =0, drugače.

G(V,X) z zankami, vendar brez več lokov definira binarno relacijo X na množici V. Celoten graf ustreza univerzalni relaciji. Neusmerjen graf ustreza simetrični relaciji. Komplement grafa ustreza komplementu relacije. Spreminjanje smeri lokov ustreza obratnemu razmerju.

Digrafi in binarne relacije so isti razred predmetov, opisanih z različnimi sredstvi. Binarne relacije, funkcije so osnovno orodje za gradnjo velike večine matematičnih modelov, ki se uporabljajo za reševanje praktičnih problemov, grafe pa lahko vizualiziramo v obliki diagrama. To pojasnjuje široko uporabo diagramov različnih vrst pri kodiranju in oblikovanju.

Točko b digrafa (grafa) G imenujemo dosegljivo iz U, če in samo če je U=V ali obstaja pot (route), ki povezuje U z V (U je začetno oglišče, V je končno oglišče). Tako na množici vozlišč digrafa (grafa) ni definirana samo relacija sosednosti A, temveč tudi relacija dosegljivosti T.

Matrika dosegljivosti T digraf (graf) G imenujemo T 2 n×n, katerega elemente najdemo iz pogoja: 1, če je dosegljiv iz ; 0, če ni dosegljiv iz .

Opredelitev matrike dosegljivosti digrafa kot matrike refleksivnega in tranzitivnega zaprtja relacije sosednosti.

Uvedena relacija dosegljivosti v ogliščih grafa G(V,X): oglišče w je dosegljivo iz oglišča v, če je v = w ali obstaja pot od v do w v G. Z drugimi besedami, dosegljivost je refleksivno in tranzitivno zaprtje sosednje relacije.

Poiščite matriko sosednosti, tranzitivno in refleksivno zaprtje.

Povezljivost v grafih. Šibka, enosmerna in močna povezljivost v digrafih. Matrica povezljivosti in močne povezanosti. Povezovalne komponente. Definicija matrike močne povezljivosti na podlagi matrike dosegljivosti.

G(V,X) se imenuje povezanče je katera koli njegova oglišča dosegljiva iz katere koli druge oglišča.

Digraf G(V,X) imenujemo enosmerno povezani, če je za kateri koli dve njeni točki vsaj eno dosegljivo iz drugega.

Digraf G(V,X) imenujemo močno povezaniče je katera od njegovih oglišč dosegljiva iz katere koli druge.

Digraf G(V,X) imenujemo ohlapno povezana, če je ne-digraf, ki mu ustreza, dobljen kot rezultat brisanja orientacije lokov, povezan.

Digraf, ki ni šibko povezan, se imenuje neskladen.

Komponenta močne vezi digrafa G(V,X) imenujemo največji, glede na število pojavitev oglišč, močno povezan podgraf tega digrafa. Podobno je definirana povezovalna komponenta nedigrafa.

Matrica močne povezanosti (povezljivosti) digrafa (grafa) G(V,X) imenujemo S n×n, katerega elemente najdemo iz pogoja: 1, če je dosegljiv iz in dosegljiv iz ; 0, če ni dosegljiv iz in ni dosegljiv iz .

(digraf) močno povezan ali povezan, zadostuje določitev prisotnosti 0 v matriki, če

0 ni, potem je graf (digraf) povezan (močno povezan), sicer ne.

Močno povezano matriko lahko sestavimo iz matrike dosegljivosti s formulo

Pustiti G = (X, d) - graf modularne strukture, х r, X-. - vozlišča, ki pripadajo x.Če v grafu G obstaja usmerjena veriga od x do Xp nato oglišče x, - dosegljiva iz oglišča x,-. Velja naslednja trditev: če je vozlišče Xj dosegljiv od x, ax (- od Xp potem x/ dosegljiv iz x^ Dokaz tega dejstva je očiten. Razmislite o binarnem odnosu na množici x, ki določa dosegljivost med vozlišči grafa. Uvedemo oznako x, -> x, za dosegljivost točke x, - od Xj. Relacija je prehodna. Označimo s H(x,) množico vozlišč grafa g, dosegljiv od x; . Potem pa enakost

definira tranzitivno zaprtje x glede na dosegljivost.

Dokažimo naslednji izrek.

Izrek 1.1. Za izbrano povezano komponento grafa modularne strukture je vsako vozlišče dosegljivo iz korena, ki ustreza tej komponenti, tj. enakost (X/- korenski vrh)

Dokaz. Recimo, da so vozlišča (x, e x) nedosegljiv iz Xj. Potem x, e X/ in množica X" = X x) ni prazno. Ker je izbrana komponenta grafa povezana, potem obstaja oglišče x, - e x in veriga /7(x; , xj), ki vodi od x, do x, -. Na podlagi acikličnosti grafa g, v X" obstajati mora preprosta veriga H(x/, xj), kam na vrh x f ne vključujejo lokov (ta veriga je lahko prazna, če X" sestavljen samo iz x,). Razmislite o verigi H(x/, xj) = H(x/, x,) U I (x, xj). To pomeni, da x. dosegljiva iz vozlišč x, in Xj in obe točki ne vsebujeta vhodnih lokov. In to je v nasprotju z definicijo grafa modularne strukture z enim korenskim vozliščem. Izrek je dokazan.

Glavna zahteva za dosegljivost je odsotnost neusmerjenih ciklov v grafu. Na podlagi grafa na sl. 1.4 ugotavljamo, da graf vsebuje usmerjen cikel in module, ki ustrezajo vozliščem x 4, x 5, f 6 , ne bo nikoli izvršen. Tako rezultati izreka 1.1 krepijo zahtevo, da v grafu modulov ni usmerjenih ciklov.

Za analizo matrične predstavitve razmerja dosegljivosti grafa modularne strukture razmislite o grafu matrike dosegljivosti, prikazanem na sl. 1.1.

Koeficient a, y= 1, če je modul, ki ustreza indeksu /, dosegljiv iz modula, ki ustreza indeksu jaz. Naslednji rezultati temeljijo na dobro znanem izreku iz teorije grafov.

riž. 1.4.

Izrek 1.2. Koeficient da l-th stopnje matrike sosednosti Razširi število različnih poti, ki vsebujejo / loke in povezujejo točko X/s oglišče ^-usmerjenega grafa.

Razmislite o naslednjih treh posledicah tega izreka.

Posledica 1.1. Matrix M \u003d "? J M t, kje M- matriko sosednosti orientacije

utrujeni graf z p vozlišč, sovpada do številčnih vrednosti koeficientov z matriko dosegljivosti AMPAK.

Dokaz. V usmerjenem grafu, ki vsebuje p vozlišč, največja dolžina poti brez ponavljajočih se lokov ne more preseči p. Zato je zaporedje stopenj matrike sosednosti M 1, kjer jaz = 1,2,

i, določa število vseh možnih poti v grafu z n loki. Naj bo koeficient t 1) matrice M drugačen od nič. To pomeni, da obstaja stopnja matrice M>, za katere pripadajoči koeficient t () je tudi drugačen od nič. Zato je pot z vrha Xj do Xp tiste. oglišče ^ je dosegljivo iz x r Ta posledica določa povezavo klicne matrike grafa modularne strukture, ki sovpada z matriko sosednosti A/, z matriko dosegljivosti AMPAK in določa algoritem za konstrukcijo slednjega.

Posledica 1.2. Naj za nekatere jaz po vrstnem redu potence matrike sosednosti M* obstaja koeficient t X1> 0. Potem je v prvotnem grafu usmerjen cikel.

Dokaz. Pustiti m (i > 0 za nekatere JAZ. Posledično Xj dosegljiv iz x v tiste. obstaja cikel. V skladu s teoremom 1.2 ima ta cikel / lokov (na splošno se ponavljajo).

Posledica 1.3. Pustiti p-i stopnja matrike sosednosti M str aciklični graf sovpada z ničelno matriko (vsi koeficienti so enaki nič).

Dokaz.Če je graf acikličen, potem najpreprostejša pot v njem ne more imeti več kot p- 1 lok. Če v M str obstaja koeficient, ki ni enak nič, potem mora obstajati pot, sestavljena iz p loki. In ta pot je lahko le usmerjen cikel. Zato vsi koeficienti M str za aciklični graf so nič. Ta posledica zagotavlja nujen in zadosten pogoj za odsotnost ciklov v grafu modularne strukture.

Za aciklične grafe je relacija dosegljivosti enakovredna delnemu strogemu redu. O tranzitivnosti relacije dosegljivosti smo razpravljali zgoraj. Antisimetrija izhaja iz odsotnosti usmerjenih ciklov: če je oglišče X ) dosegljiv iz x v potem obratno ne drži. Uvedemo notacijo x x > Xpče je top Xj dosegljiva z vrha x v

Pustiti G=(X, Г) je acikličen graf, ki ustreza neki modularni strukturi. Razmislite o padajoči verigi elementov delno urejene množice X:

kjer znak “>” označuje relacijo dosegljivosti. Zaradi X Seveda je veriga pretrgana x n > x i2 > ... > x v. Vertex xjn nima izhodnih lokov, tj. element x v minimalen (ustreza modulu, ki ne vsebuje klicev drugih modulov). Največji element v množici X je korensko oglišče.

• Dokaz tega izreka je podan v delu (knjigi): Lavrishcheva E. M., Grishchenko V. N. Programiranje sklopov. Kijev: Naukova Dumka, 1991. 287 str.

DOSEGLJIVOST IN POVEZLJIVOST V GRAFIH Vsebina predavanja: Poti verige in cikli. Povezljivost grafov in komponente povezljivosti. Premer, polmer in središče grafa.

Če vam to delo ne ustreza, je na dnu strani seznam podobnih del. Uporabite lahko tudi gumb za iskanje

Baranov Viktor Pavlovič Diskretna matematika. Oddelek 3Grafi, mreže, kode.

Predavanje 8

Predavanje 8 DOSEGLJIVOST IN POVEZLJIVOST V GRAFIH

Načrt predavanja:

1. Poti, verige in kolesa.
2. Povezljivost grafov in komponente povezljivosti.
3. Premer, polmer in središče grafa.
4. Matrike dosegljivosti in nasprotno dosegljivosti.

1. Poti, krogi in zanke

Orientirana pot(ali po ) digrafa je zaporedje lokov, v katerem je končna točka katerega koli loka, razen zadnjega, začetna točka naslednjega. Na sl. 1 zaporedje lokov

, (1)

, (2)

(3)

so poti.

riž. eno.

usmerjena veriga(ali orepio ) se imenuje pot, v kateri vsak lok in z uporabljen ne več kot enkrat. Tako sta na primer poti (2) in (3) aliverigi, pot (1) pa ni, saj je lok v njej uporabljen dvakrat.

Enostavno se imenuje veriga, v kateri vsako vozlišče uporablja največ eno približno krat. Na primer, orchain (3) je preprost, orchain (2) pa ne.

Pot je neusmerjeni dvojnik poti, to je zaporedje robov, v katerem je vsak rob, razen prvega in zadnjega, povezan s končnimi oglišči z robovi in. Črta nad simbolom loka pomeni, da se obravnava kot rob.

Tako kot smo definirali aliverige in preproste verige, lahko definiramo verige in preproste verige.

Pot ali pot je lahko predstavljena tudi z zaporedjem vozlišč. Na primer in mere, lahko pot (1) zapišemo kot: .

Pot se imenuje zaprta , če začetna točka loka v njem sovpada s konjem h Noah vrh loka. Zaprte ali verige (verige) se imenujejo ali cikli (cikli ). Imenujejo se tudi orcikli konture . Zaprte preproste ali verige (verige) imenovane s preprosti ali cikli(cikli). zaprta potje neorientiran n zaprta dvojna na vas.

1. Povezljivost grafov in komponente povezljivosti

Za vozlišče v digrafu pravimo, da je dosegljivo iz vozlišča, če obstaja pot. Če je poleg tega dosegljiv iz, potem pravimo, da so ta vozlišča medsebojno dosegljiva.

Digraf se imenuje močno povezan ali močan , če sta kateri koli dve točki v njej a imo dosegljivo. Primer močnega digrafa je prikazan na sl. 2 a. Ker v kolumni e glede na orcikel, ki vključuje vsa vozlišča, se vzameta kateri koli dve od njih vendar dosegljivo.

° ° °

° ° ° ° ° °

° ° ° ° ° °

a B C

riž. 2.

Digraf se imenujeenosmerno povezani ali enostransko če je v katerem koli paru njegovih oglišč vsaj eno dosegljivo iz drugega. Primer enosmernega grafa je prikazan na sl. 2 b. Ta graf ima orcikel, ki vključuje štiri medsebojno dosegljiva vozlišča. Točka ima vstopno stopnjo nič, kar pomeni, da do te točke ne vodi nobena pot. Še več, iz njega je dosegljivo katero koli od ostalih štirih vozlišč.

Digraf se imenuje ohlapno povezani ali šibki , če vsebuje kateri koli dve točki z približno na pol poti . Polpot ima lahko za razliko od poti nasprotno smer. v leni loki. Primer šibkega digrafa je prikazan na sl. 2 in. Očitno je, da graf ne vsebuje pri ty med oglišči in, vendar obstaja polovična pot, sestavljena iz nasprotnih n a črtasti loki in.

Če za neki par vozlišč ni poti, ki bi ju povezovala, potem t a kateri digraf se imenuje neskladen.

Za digraf so definirane tri vrste povezanih komponent:močna komponenta ma k najmočnejši podgraf,enostranska komponentanajveč enojno približno ronny podgraf inšibka komponentamaksimalno šibek podgraf.

Koncept močne komponente je prikazan na sl. 3.

° ° ° ° ° °

° ° ° °

° ° ° ° ° °

° ° ° ° ° °

° ° °

° ° ° ° °

riž. 3

Graf, ki je enosmerno povezan, vsebuje šest močnih d grafi, katerih močni komponenti sta samo in n tami. Podobno je prikazan koncept enosmerne komponente. V tej opombi e Enosmerna komponenta je enaka samemu grafu. Če spremenimo orientacijo a loka, na primer nasprotnemu, potem dobimo šibek graf z dvema enostranskima približno čelne komponente, od katerih eno tvorijo oglišča, drugo pa ve r pnevmatike.

Za neusmerjen graf definiramo bin na množici njegovih vozlišč R razmerje, ob predpostavki, da obstaja verižna povezava z. To razmerje je a daje lastnosti refleksivnosti, simetrije in tranzitivnosti, torej gre za t enakovrednost nošenja. Razdeli množico vozlišč v razrede, ki se ne sekajo: . Dve točki iz istega razreda sta enakovredni, to pomeni, da v grafu obstaja veriga, ki ju povezuje, za točki iz različnih razredov pa te verige ni. Od konca Yu Če so robovi v relaciji, bo tudi množica robov grafa razdeljena na nesekajoče se razrede: , kjer je množica vseh robov, katerih konci pripadajo, označena z .

Grafa sta povezana in se seštejeta v graf. Ti grafi se imenujejokomponente povezljivostigraf. Število je še ena numerična značilnost grafa. Za povezani graf, če je graf nepovezan, potem.

Če dani graf ni povezan in se razdeli na več komponent, se lahko rešitev katerega koli vprašanja v zvezi s tem grafom praviloma zmanjša na študijo posameznih komponent, ki so povezane. Zato je v večini primerov smiselno domnevati, da je dani graf povezan.

1. Premer, polmer in središče grafa

Za povezan graf definiramo razdalja med njenima dvema ogliščima in kot dolžina najkrajše verige, ki povezuje ta oglišča, in jo označimo z. Dolžina verige je število robov, ki sestavljajo verigo. Preprosto je preveriti, ali ste vstopili n Ta razdalja izpolnjuje aksiome metrike:

2) ;

3) .

Določite razdaljo od vsake točke grafa do točke, ki je najbolj oddaljena od nje

ki se imenujeekscentričnost. Očitno je, da je ekscentričnost za vsa oglišča v celotnem grafu enaka ena, za oglišča enostavnega cikla pa .

Največja ekscentričnost se imenuje premer graf in minimum polmer graf. V celotnem grafu imamo, v preprostem ciklu pa .

Vozlišče se imenuje centralno, če. Graf jih je lahko več b takšna oglišča, v nekaterih grafih pa so vsa oglišča središčna. V preprosti verigi z lihim številom oglišč je samo ena osrednja in s sodim številom z obstajata dve taki točki. V popolnem grafu in preprostem ciklu so vsa vozlišča središčna. Množica osrednjih vozlišč se imenuje središče grafa.

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

° °

° ° °

° °

° °

riž. štiri.

Za rešitev te težave je priročno vnaprej izračunatimatriko razdalje med vrhovi mi štejem. V tem primeru bo to matrika velikosti, v kateri je razdalja od točke do točke na mestu:

Za vsako vrstico matrike poiščemo največji element in ga zapišemo z a wa iz pomišljaja. Največje od teh števil je enako premeru grafa, najmanjše p a dius grafa. Središče grafa tvorita osrednja vozlišča in.

Koncepti osrednjega vozlišča in središča grafa so se pojavili v povezavi s problemi optimizma. in majhne lokacije točk javnih služb, kot so bolnišnice, gasilski oddelki, postaje javnega reda itd., ko je pomembno čim bolj zmanjšati in večja razdalja od katere koli točke nekega omrežja do najbližje servisne točke a niya.

1. Matrike dosegljivosti in nasprotno dosegljivosti

Matrika dosegljivostije opredeljeno kot sledi:

Množica vozlišč grafa, ki so dosegljiva iz dane vozlišča, je sestavljena iz tistih elementov, za katere je th element v matriki 1. Ta niz lahko predstavimo kot

Matrika nasprotne dosegljivosti (inverzna dosegljivost) definirati kot sledi:

Podobno kot pri konstrukciji dostopne množice lahko oblikujemo množico približno gesta z naslednjim izrazom:

Iz definicij sledi, da -ti stolpec matrike sovpada z -to vrstico matrike t , tj. kje je matrika transponirana v matriko.

Primer 2 Poiščite matriko dosegljivosti in nasprotno dosegljivosti za graf itd. in prikazano na sl. 5.

riž. 5.

Določimo nabore dosegljivosti za vozlišča grafa:

Zato imata matriki dosegljivosti in nasprotno dosegljivosti obliko:

Ker je množica takšnih vozlišč, od katerih vsako pripada vsaj eni poti, ki vodi od do, se vozlišča te množice imenujejo so bistvene ali neodtujljive glede na končna oglišča in. Vsa druga oglišča so poklicananepomemben ali odveč , saj njihova odstranitev ne vpliva na poti od do.

Določite lahko tudi matrike omejeno dosegljivost in protidosegljivost in mostov, če zahtevamo, da dolžine poti ne presegajo določenega števila. Nato bo zgornja meja dolžine dopustnih poti.

Za graf pravimo, da je prehoden če iz obstoja lokov in sledi pri obstaja obstoj loka.prehodno zaprtjegraf je graf, kjer je najmanjša možna množica lokov, potrebnih, da je graf tranzitiven. Očitno je, da matrika dosegljivosti grafa sovpada z matriko sosednosti grafa, če enote postavimo na glavno diagonalo v matriki.