Zvažujú sa otázky dosiahnuteľnosti pre digrafy a metódy hľadania matíc dosiahnuteľnosti a protidosiahnuteľnosti. Maticová metóda sa zvažuje na nájdenie počtu ciest medzi ľubovoľnými vrcholmi grafu, ako aj na nájdenie množiny vrcholov zahrnutých v ceste medzi dvojicou vrcholov. Účel prednášky: Poskytnúť predstavu o dosiahnuteľnosti a protidosiahnuteľnosti a ako ich nájsť
Dosiahnuteľnosť a protidosah
Úlohy, v ktorych sa concept používa dosiahnuteľnosť, dosmalo.
Tu je jeden z nich. grafic môže byť modelom nejakej organizácie, v ktorej sú ľudia reprezentovaní vrcholmi a oblúky interpretujú komunikačné kanály. Pri zvažovaní takéhoto modelu si možno položiť otázku, či sa informácie od jednej osoby i môžu preniesť na inú osobu j, t. j. či existuje cesta vedúca z vrcholov i do vrcholov j. Ak takato cesta existuje, potom vrcholy j dosiahnuteľne z vrcholov i. Niekoho môže zaujímať dosiahnuteľnosť vrcholov j z vrcholov i len na dráhach, ktorých dĺžky nepresahujú danú hodnotu alebo ktorých dĺžka je menšia ako najväčší počet v graď at. úlohy.
Dosiahnuteľnosť v grafe je opisaná maticou dosiahnuteľnosti R =, i, j = 1, 2, ... n, kde n je počet vrcholov v grafe a každý prvok je definovaný takto:
r ij = 1, ak sú vrcholy j dosiahnuteľné z x i,
rij = 0, inak.
Množina vrcholov R (xi) grafu G dosiahnuteľných z daného vrcholu xi pozostáva z prvkov xi, pre ktoré je (i, j)-tý prvok v matici dosiahnuteľnosti 1. vrchol je dosiahnuteľný sám od sebažuľný sám od sebažuľný sám od sebaľaľný ľožrádu 0. G +1 (xi) je množina takých vrcholov xj, ktoré sú dosiahnuteľné z xi pomocou ciest dĺžky 1, potom množina +1xi ()) = G +2 (xi) pozostáva z vrcholov dosiahnuteľných z xi pomožne z dēbēných z xi pomožcou 2. p (xi) je množina vrcholov dosiahnuteľných z xi pomocou ciest dĺžky p.
Pretože každý vrchol grafu, ktorý je dosiahnuteľný z x i, musí byť dosiahnuteľný pomocou cesty (alebo ciest) dĺžky 0 alebo 1, alebo 2,...
R (x i) \u003d (x i) G +1 (x i) G +2 (x i) ... G + p (x i).
Ako vidíte, množina dosiahnuteľných vrcholov R (x i) je priamym tranzitívnym uzáverom vrcholu x i, t. j. R (x i) = T + (x i). Preto na zostrojenie matice dosiahnuteľnosti nájdeme dosiahnuteľné množiny R (x i) pre všetky vrcholy x i X. Nastavenie r ij = 1, ak x j R (x i) a r ij = 0 inak.
Ryza. 4.1. Dosiahnuteľnosť v graphe: a - graf; b - matică susednosti; c - matica dosiahnuteľnosti; r - matica protidosiahnuteľnosti.
Pre graf znázornený na obr. 4.1a, subor dosiahnuteľnosti sa nachádzajú nasledovne:
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) \u003d (x 2) (x 2, x 4) (x 2, x 4, x 5) (x 2, x 4, x 5) \u003d (x 2, x 4, x 5) ,
R (x 3) \u003d (x 3) (x 4) (x 5) (x 5) \u003d (x 3, x 4, x 5),
R (x 4) \u003d (x 4) (x 5) (x 5) \u003d (x 4, x 5),
R (x 5) \u003d (x 5) (x 5) \u003d (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, x5, x6, x7),
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) ,x7).
Matica dosiahnuteľnosti má tvar znázornený na obr. 4.1, c. Matica dosiahnuteľnosti môže byť postavené tica susednosti(obr. 4.1, b), tvoriace množiny T + (x i) pre každý vrchol x i.
Protidosiahnuteľna matică Q = [q ij], i, j = 1, 2, ... n, kde n je počet vrcholov v grafe, je definovaný takto:
q ij = 1, ak z vrcholu x j je možné dosiahnuť vrchol x i,
q ij = 0, inak.
Protisplniteľne množina Q (x i) Podobne ako pri konštrukcii dosiahnuteľnej množiny R (x i), môžeme napísať výraz pre Q (x i):
Q (x i) \u003d (x i) G -1 (x i) G - 2 (x i) ... G -p (x i).
Je teda možné vidieť, že Q (x i) nie je nič iné ako spätný tranzitívny uzáver vrcholu x i, teda Q (x i) = T - (x i). Z definícií je zrejmé, že stĺpec xi matice Q (v ktorej q ij = 1, ak xj Q (xi) a q ij = 0 inak) sa zhoduje s riadkom xi matice R, tj Q = RT, kde RT je matica transponovaná matica dosiahnuteľnosti R.
Protidosiahnuteľna matică znázornene pe obr. 4,1 g.
Je potrebné poznamenať, že keďže všetky prvky matíc R a Q sú rovné 1 alebo 0, každý riadok môže byť uložený v binárnej forme, čím sa šetria náklady na pamäť počítača. Matice R a Q sú vhodné na spracovanie na počítači, pretože z výpočtového hľadiska sú hlavnými operáciami vysokorýchlostné logické operácie.
Nájdenie množiny vrcholov zahrnutých v ceste
Ak potrebujete vedieť o vrcholoch grafu zahrnutých v týchto cestách, mali by ste si zapamätať definície dopredných a spätných tranzitívnych uzáverov. Keďže T + (xi) je množina vrcholov, ku ktorým vedú cesty z vrcholu xi, a T - (xj) je množina vrcholov, z ktorých vedú cesty k xj, potom T + (xi) T - (xj ) je množina vrcholov, z ktorých každý patrí aspoň jednej ceste vedúcej zxi do x j. Tieto vrcholy sa nazývajú podstatné alebo integrálne vzhľadom na dva koncové vrcholy x i a x j. Všetky ostatné vrcholy grafu sa nazývajú nevýznamné alebo nadbytočné, pretože ich odstránenie neovplyvňuje cesty z x i tox j.
Ryza. 4.2. Digraf
Takže pre graf na obr. 4.2 nájdenie vrcholov zahrnutých v ceste, napríklad z vrcholu x 2 do vrcholu 4, sa zredukuje na nájdenie T + (x 2) = (x 2, x 3, x 4, x 5, x 6),
T - (x 4) = (x 1, x 2, x 3, x 4, x 5) a ich priesečníky T + (x 2) T - (x 4) = (x 2, x 3, x 4, x 5).
Maticová metóda na hľadanie ciest v grafoch
Matica susednosti úplne definuje štruktúru grafu. Urobme druhú mocninu matice susednosti podľa pravidiel matematiky. Každý prvok matice A2 je určený vzorcom
a (2) ik = n j = 1 a ij a jk
Člen vo vzorci sa rovná 1 práve vtedy, ak sa obe čísla a ij aa jk rovnajú 1, inak sa rovna 0 xj, potom sa (i-tý, k-tý) prvok matice А 2 rovná počtu dráh dĺžky 2 idúcichz 2 idúcichz k.
Tabuľka 4.1a ukazuje maticu susednosti grafu znázorneneho pe obr. 4.2. Výsledok kvadratúry matice susednosti A2 je uvedený v tabuľke 4.1b.
Takže "1", stojaca na priesečníku druhého radu a štvrtého stĺpca, označuje existenciu jednej cesty dĺžky 2 z vrcholu x 2 do vrcholu 4. Skutočne, ako vidíme v stĺpec pe obr. 4.2 existuje taká cesta: a 6, a 5. "2" v matici A2 označuje existenciu dvoch ciest dĺžky 2 z vrcholov 3 do vrcholov 6: a 8, a 4 a a 10, a 3.
Podobne pre maticu susednosti umocnenú na tretiu mocninu A 3 (tabuľka 4.1c), a (3) ik sa rovná počtu dráh dĺžky 3 idúcich od x i do x k. Zo štvrtého riadku matice A 3 je vidieť, že existujú cesty dĺžky 3: jedna z x 4 v 4 (a 9, a 8, a 5), jedna z x 4 v
x 5 (a 9, a 10, a 6) a dve cesty z x 4 v 6 (a 9, a 10, a 3 a a 9, a 8, a 4). Matica A 4 ukazuje existenciu dráh dĺžky 4 (tabuľka 4.1d).
Ak je teda p ik prvkom matice A p, potom sa p ik rovná počtu dráh (nie nevyhnutne reťazcov alebo jednoduchých reťazcov) dĺžky p vychádzajúcich z x i kx k.
Graf dosiahnuteľnosti
Jednou z prvých otázok, ktoré sa vynárajú pri štúdiu grafov, je otázka existencie ciest medzi danými alebo všetkými pármi vrcholov. G = (V, E): vrchol w je dosiahnuteľný z vrcholu v, ak v = w alebo G má cestu z v do w. Inými slovami, vzťah dosiahnuteľnosti je reflexným a tranzitívnym uzavretím vzťahu E. Pre neorientované grafy je tento vzťah tiež symetrický, a preto je vzťahom ekvivalencie na vrcholovej množúnom savým vzťahu na vrcholovej množúnom sp. V prípade orientovaných grafov nemusí byť dosiahnuteľnosť vo všeobecnosti symetrickým vzťahom. Vzájomná dosiahnuteľnosť je symetrická.
Definiție 9.8. Vrcholy v a w orientovaného grafu G = (V, E) sa nazývajú vzájomne dosiahnuteľné, ak G má cestu z v do w a cestu z w do v.
Je zrejmé, že vzťah vzájomnej dosiahnuteľnosti je reflexívny, symetrický a tranzitívny, a teda ekvivalencia na vrcholovej množine grafu. Triedy ekvivalencie vzhľadom na vzájomnú dosiahnuteľnosť sa nazývajú silne spojené zložky, príp dvojito spojene komponenty grafic.
Najprv sa zamyslime nad otázkou budovania vzťahu dosiahnuteľnosti. Pre každý graf definujeme jeho graf dosiahnuteľnosti (niekedy nazývaný aj graf tranzitívneho uzavretia), ktorého okraje zodpovedajú dráham pôvodného grafu.
Definiție 9.9. Nech G = (V, E) je orientovaný graf. Graf dosiahnuteľnosti G * = (V, E *) pre G má rovnakú množinu vrcholov V a nasledujúcu množinu hrán E * = ((u, v) | v graphe G je vrchol v dosiahnuteľný z vrcholu u ).
Priklad 9.3. Uvažujme graf G z prikladu 9.2.
Ryza. 9.2. Graf G
Potom môžeme skontrolovať, či graf dosiahnuteľnosti G * pre G vyzerá takto (nové okrajové slučky v každom z vrcholov 1-5 nie sú zobrazené):
Ryza. 9.3. Buzunar G*
Ako sa da zostrojiť graf G*z grafu G? Jedným zo spôsobov je určiť pre každý vrchol grafu G množinu z neho dosiahnuteľných vrcholov, postupne k nemu pridávať vrcholy, ktoré sú z neho dosiahnuteľné cestami dĺ1, ďžky vrcholov
Budeme uvažovať o inej metóde založenej na použití matice susednosti A G grafu G a booleovských operáciách. Nech množina vrcholov V = (v 1,…, v n). Potom matica A G je n × n booleovská matica.
Nižšie, aby sme zachovali podobnosť s bežnými operáciami na maticách, použijeme pre booleovské operácie "aritmetickú" notáciu: pomocou + označujeme disjunkciu a pomocou - konjunkciu.
Nech E n označuje maticu identitate n × n. Dali sme 
... Nech je náš postup konštrukcie G *založený na nasledujúcom tvrdení.
Lema 9.2. Nechaj. Potom
Dokaz indukciou na k.
Zaklad. Pre k = 0 ak = 1 je tvrdenie z definície pravdivé a.
Indukčny krok. Nech plati lema pre k. Ukážme, že zostáva v platnosti aj pre k + 1. Podľa definície máme:
Predpokladajme, že graf G od v i do v j má dráhu dĺžky k + 1. Zvážte najkratšiu z týchto ciest. Ak je jeho dĺžka k, potom podľa indukčnej hypotézy a_ (ij) ^ ((k)) = 1. Navyše a jj (1) = 1. Preto a ij (k) a jj (1) = 1 aa ij (k + 1) = 1. Ak je dĺžka najkratšej cesty zvi do vj rovná k + 1, potom nech vr je jej predposledný vrchol. Potom existuje dráha dĺžky kzvi do vra podľa indukčnej hypotézy a ir (k) = 1. Keďže (vr, vj) E, potom a_ (rj) ^ ((1)) = 1. Preto a ir (k) a rj (1) ) = 1 aa ij (k + 1) = 1.
Naopak, ak a ij (k + 1) = 1, potom aspoň pre jedno r sa sčítanec a ir (k) a rj (1) rovná 1. Ak je toto r = j, potom a ij (k) = 1 a podľa indukčnej hypotézy má G cestu z vi do vj dĺžky k. Ak rj, potom a ir (k) = 1 aa rj (1) = 1. To znamená, že G má cestu zvi do vr dĺžky ka hranu (vr, vj) E. Ich spojením dostaneme cestu zvi do vj dĺžky k + 1 .
Z Lem 9.1 a 9.2 okamžite ziskame
Dôsledok 1. Nech G = (V, E) je orientovaný graf s n vrholmi a G * jeho graf dosiahnuteľnosti. Potom A_(G*)=. Dokaz. Z lemmy 5.1 vyplýva, že ak má G cestu z u do v u, potom obsahuje aj jednoduchú cestu z u do v dĺžky n-1. A podľa Lemy 5.2 sú všetky takéto cesty reprezentované v matici.
Postup konštrukcie matice susednosti A G* grafu dosiahnuteľnosti pre G je teda redukovaný na zvýšenie matice na mocninu n-1. Urobme niekoľko poznámok na zjednodušenie tohto postupu.
kde k je najmenšie číslo také, že 2 k n.
existuje r také, že a ir = 1 a a rj = 1, potom celý súčet a ij (2) = 1. Preto možno ostatné výrazy ignorovať.
Priklad 9.3. Uvažujme ako príklad výpočet matice grafu dosiahnuteľnosti A G * pre graf G znázornený na Obrazok 9.2... V tomto pripade
Pretože G má 6 vrcholov, potom. Vypočítajme túto maticu:
a (posledná rovnosť sa dá ľahko skontrolovať). touto cestou,
Ako môžete vidieť, táto matica skutočne definuje graf znázornený na Obrazok 9.3.
Vzájomná dostupnosť, pevne prepojené komponenty a základne grafov
Analogicky s grafom dosiahnuteľnosti definujeme silný graf dosiahnuteľnosti.
Definiția 9.10. Nech G = (V, E) je orientovaný graf. Graf silnej dosiahnuteľnosti G * * = (V, E * *) pre G má rovnakú množinu vrcholov V a nasledujúcu množinu hrán E * * = ((u, v) | v grafe G vrcholy v a ste vzájomne dosiahnuteľný).
Z matice grafu dosiahnuteľnosti je ľahké zostaviť silnú maticu grafu dosiahnuteľnosti. Z definícií dosiahnuteľnosti a silnej dosiahnuteľnosti totiž hneď vyplýva, že potom pre všetky dvojice (i, j), 1 i, jn je hodnota prvku 1 práve vtedy, ak oba prvky AG * (i, j) a AG * (j, i) * sa rovnaju 1, tj
Zložky silnej spojitosti grafu G možno od matice odlíšiť nasledovne.
Do komponentu K 1 umiestnime vrchol v 1 a všetky také vrcholy v j, aby A_ (G _ * ^ *) (1, j) = 1.
Nech už sú zostrojené komponenty K 1,…, K i a v k - toto je vchol s minimálnym počtom, ktorý ešte nebol zahrnutý do komponentov. Potom do komponentu K_ (i + 1) umiestnime vrchol v k a všetky takéto vrcholy v j,
že A_ (G _ * ^ *) (k, j) = 1.
Opakujte krok (2), kým nebudú všetky vrcholy rozdelené na komponenty.
V našom priklade pre graf G na obr maticou získame nasledujúcu maticu grafu silnej dosiahnuteľnosti
Vyššie popísaným postupom zistíme, že vrcholy grafu G sú rozdelené na 4 zložky silného spojenia: K 1 = (v 1, v 2, v 3), \ K 2 = (v 4), \ K 3 = (v 5), \ K4 = (v 6). Na množine silne prepojených komponentov definujeme aj vzťah dosiahnuteľnosti.
Definiția 9.11. Nech K a K "sú silne spojené komponenty grafu G. Komponent K dosiahnuteľny z zložky K ^ \ prvočíslo, ak K = K "alebo existujú dva vrcholy u K a v K" také, že u je dosiahnuteľné z v. K prísne dosiahnuteľny z K ^ \prvočíslo, ak K K "a K je dosiahnuteľné z K". Zložka K sa nazyva minim, ak to nie je striktne dosiahnuteľné zo žiadneho komponentu.
Keďže všetky vrcholy v jednom komponente sú vzájomne dosiahnuteľné, je ľahké pochopiť, že vzťahy dosiahnuteľnosti a prísnej dosiahnuteľnosti na komponentoch nezávisia od výberu Kvrcho".
Nasledujúca charakteristika prísnej dosiahnuteľnosti je ľahko odvoditeľná z definície.
Lema 9.3. Striktný vzťah dosiahnuteľnosti je čiastočným objednávacím vzťahom, t.j. je antireflexný, antisymetrický a tranzitívny.
Tento vzťah možno znázorniť ako orientovaný graf, ktorého vrcholy sú komponentmi a hrana (K ", K) znamená, že K je striktne dosiahnuteľné z K". N / A ryza. 9.4 tento graf komponentov je znázornený pre graf G uvažovaný vyššie.
Ryza. 9.4.
V tomto prípade existuje jedna minimálna zložka K2.
V mnohých aplikáciách je orientovaný graf distribučnou sieťou nejakého zdroja: produktu, produktu, informácie atď. V takýchto prípadoch prirodzene nastáva problém nájsť minimálny počet takých bodov (vrcholov), z ktorých môže byť tento zdroj doručený do ktoréhokoľvek bodu v sieti.
Definiția 9.12. Nech G = (V, E) je orientovaný graf. Podmnožina vrcholov W V sa nazyva generaţie ak je možné dosiahnuť niektorý vrchol grafu z vrcholov W. Podmnožina vrcholov W V sa nazýva základňa grafu, ak generuje, ale negeneruje žiadna z jej vlastných podmnožín.
Nasledujúca veta nám umožňuje efektívne nájsť všetky bázy grafu.
Veta 9.1. Nech G = (V, E) je orientovaný graf. Podmnožina vrcholov W V je základňou G práve vtedy, ak obsahuje jeden vrchol z každého minimálneho komponentu silného spojenia G a neobsahuje žiadne ďalšie vrcholy.
Dokaz Najprv si všimnite, že každý vrchol grafu je dosiahnuteľný z vrcholu patriacemu nejakému minimálnemu komponentu. Preto sa generuje množina vrcholov W, ktorá obsahuje jeden vrchol z každého minimálneho komponentu, a keď sa z neho akýkoľvek vrchol odstráni, prestane ním byť, pretože vrcholy z príslušného komponentu minim. Preto je W zaklad.
Naopak, ak W je báza, potom musí obsahovať aspoň jeden vrchol z každého minimálneho komponentu, inak budú vrcholy takéhoto minimálneho komponentu neprístupné. W nemôže obsahovať žiadne ďalšie vrcholy, pretože každý z nich je dosiahnuteľný z už zahrnutých vrcholov.
Táto veta implicuje nasledujúci postup na zostavenie jednej alebo vymenovania všetkých báz grafu G.
Nájdite všetky komponenty silneho spojenia G.
Určite poradie na nich a vyberte komponenty, ktoré sú minimálne vzhľadom na toto poradie.
Vygenerujte jednu alebo všetky bázy grafu a vyberte jeden vrchol z každého minimálneho komponentu.
Priklad 9.5. Definujeme všetky bázy orientovaného grafu G znázorneneho v Obrazok 9.5.
Ryza. 9.5. Graf G
V prvej fáze nájdeme komponenty silneho spojenia G:
V druhej fáze vytvoríme striktný graf dosiahnuteľnosti pomocou týchto komponentov.
Ryza. 9.6. Graf pomeru dosiahnuteľnosti komponentov G
Určte minimálne zložky: K 2 = (b), K 4 = (d, e, f, g) a K 7 = (r).
Nakoniec uvedieme všetky štyri základy G: B 1 = (b, d, r), B 2 = (b, e, r), B 3 = (b, f, r) a B 1 = (b, g, r) ...
Ulohy
Uloha 9.1. Dokážte, že súčet stupňov všetkých vrcholov ľubovoľného orientovaného grafu je párny.
Tento problém má populárnu interpretáciu: dokázať, že celkový počet podaní rúk medzi ľuďmi, ktorí prišli na párty, je vždy párny.
Uloha 9.2. Uveďte všetky neizomorfné neorientované grafy s najviac štyrmi vrcholmi.
Uloha 9.3. Dokážte, že neorientovaný súvislý graf zostane spojený po odstránení nejakej hrany ↔ táto hrana patrí do nejakého cyklu.
Uloha 9.4. Dokážte, že neorientovaný súvislý graf s n vrcholmi
obsahuje aspoň n-1 hran,
ak obsahuje viac ako n-1 hrán, tak má aspoň jeden cyklus.
Uloha 9.5. Dokážte, že v každej skupine 6 ľudí sú tri páry známych alebo tri páry neznámych ľudí.
Uloha 9.6. Dokážte, že neorientovaný graf G = (V, E) je spojený ↔ pre každý oddiel V = V 1 V 2 s neprázdnym V 1 a V 2 existuje hrana spájajúca V 1 s V 2.
Uloha 9.7. Dokážte, že ak má neorientovaný graf práve dva vrcholy nepárneho stupňa, potom su spojené cestou.
Uloha 9.8. Nech G = (V, E) je nonorientovaný graf s | e |< |V|-1. Докажите, что тогда G несвязный граф.
Uloha 9.9. Dokážte, že v prepojenom neorientovanom grafe majú akékoľvek dve jednoduché cesty maximálnej dĺžky spoločný vrchol.
Uloha 9.10. Nech neorientovaný graf bez slučiek G = (V, E) má k spojených komponentov. Deci pentru a dovedi
Uloha 9.11. Určte, načo slúži graf dosiahnuteľnosti
graf s n vrcholmi a prázdnou množinou hrán;
graf s n vrcholmi: V = (v 1, ..., v n), ktorého hrany tvoria cyklus:
Uloha 9.12. Vypočítajte maticu grafu dosiahnuteľnosti pre graf
a vytvorte zodpovedajúci graf dosiahnuteľnosti. Nájdite všetky základy grafu G.
Uloha 9.13. Stavať na dane ryza. 9.7 orientovaný graf G 1 = (V, E) jeho matica susednosti A G1, matica incidente B G1 a zoznamy susedností. Vypočítajte maticu dosiahnuteľnosti A G1 * a zostrojte zodpovedajúci graf dosiahnuteľnosti G 1 *.
Ryza. 9.7.
Neorientovane a orientevané stromy
Stromy sú jednou z najzaujímavejších a încercat graficov používaných na reprezentáciu rôznych druhov hierarchických štruktúr.
Definiție 10.1. Neorientovaný graf sa nazyva strom, ak je spojený a nemá žiadne cykly.
Definiția 10.2. Orientovaný graf G = (V, E) sa nazýva (orientovaný) strom ak
N / A ryza. 10.1 sú znázornene príklady neorientovaného stromu G1 a orientovaného stromu G2. Všimnite si, že strom G 2 je odvodený od G 1 výberom c ako koreňa a orientáciou všetkých hrán preč od koreňa.
Ryza. 10.1. Neorientovane a orientevané stromy
To nie je nahoda. Dokážte nasledujúce tvrdenie o vzťahu medzi neusmernenými a orientovanými stromami.
Lema 10.1. Ak v ľubovoľnom neusmernenom strome G = (V, E) zvolíme za koreň ľubovoľný vrchol v V a všetky hrany orientujeme v smere "od koreňa", t.j. urobte v začiatkom všetkých hrán, ktoré k nemu priliehajú, vrcholov susediacich s v - začiatok všetkých dopadajúcich hrán, ktoré k nemu ešte nie sú orientované, atď., potom bude všetkých orientovanmmer.ýsled "orientovanmmer.ýsled"
Neorientované a orientované stromy majú mnoho ekvivalentných vlastností.
Veta 10.1. Nech G = (V, E) je nonorientovaný graf. Potom sú nasledujúce podmienky ekvivalentné.
G je strom.
Pre akékoľvek dva vrcholy v G existuje jedna cesta, ktorá ich spaja.
G je pripojený, ale keď sa odstráni ktorýkoľvek okraj z E, prestane byť spojený.
G je pripojený a | e | = | v | - Jeden.
G je acyklické a |E | = | v | - Jeden.
G je acyklický, ale pridanie akejkoľvek hrany k E generuje cyklus.
Dokaz(1) (2): Ak de nejaké dva vrcholy v G boli spojené dvoma cestami, potom de G mal zjavne cyklus. To je však v rozpore s definíciou stromu v (1).
(2) (3) Ale potom G obsahuje aspoň dve cesty spájajúce u a v, čo je v rozpore s podmienkou (2).
(3) (4): Poskytnuté čitateľovi (problema pozri 9.4).
(4) (5): Ak G obsahuje cyklus a je spojený, odstránenie akejkoľvek hrany z cyklu de nemalo prerušiť spojenie, ale hrany zostanú | e | = V -2 a podľa úlohy 9.4 (a) , pripojený graf by mal obsahovať aspoň V -1 rebrá. Výsledný rozpor ukazuje, že v G nie sú žiadne cykly a podmienka (5) je splnená.
(5) (6): Predpokladajme, že pridanie hrany (u, v) k En neviedlo k cyklu. Potom v G sú vrcholy u a v v rôznych spojených komponentoch. Keďže | e | = V -1, potom v jednej z týchto zložiek, nech je (V 1, E 1), sa počet hrán a počet vrcholov zhodujú: | E 1 | = | V 1 |. Potom však obsahuje cyklus (pozri úlohu 9.4 (b)), ktorý je v rozpore s acyklickosťou G.
(6) (1): Ak de G nebolo spojené, potom de existovali dva vrcholy u a v z rôznych spojených komponentov. Potom pridanie hrany (u, v) k E neviedlo k vzniku cyklu, čo je v rozpore (6). Preto je G spojene a je stromom.
Pre orientované stromy je často vhodné použiť nasledujúcu induktívnu definíciu.
Definiție 10.3. Definujme indukciou triedu orientovaných grafov nazyvaných stromy. Zároveň pre každý z nich definujeme vyhradený vrchol - koreň.
Ryza. 10.2 ilustruje túto definíciu.
Ryza. 10.2. Induktívna definícia orientovaných stromov
Veta 10.2. Definície riadených stromov v 10.2 a 10.3 su ekvivalentné.
Dokaz Nech graf G = (V, E) spĺňa podmienky definície 10.2. Ukážme indukciou na počte vrcholov | v | ze.
Ak | v | = 1, potom jedinečný vrchol v V je podľa vlastnosti (1) koreň stromu, tj. tento graf nemá hrany: E =. Potom.
10.2. Nech graf G = (V, E) s (n + 1) vrcholom spĺňa podmienky definície 10.2. Podľa podmienky (1) má koreňový vrchol r 0. Nech k hrán vychádza z r 0 a vedie k vrcholom r 1,…, r k (k 1). Graf, ktorý obsahuje vrcholy V i = (v V | v \ textit (dosiahnuteľný z) ri) a spojovacie hrany E i E, označíme G i, (i = 1, ..., k). pochopiť, že G i spĺňa podmienky definície 10.2. V skutočnosti r i neobsahuje hrany, tj. tento vrchol je koreňom G i. Každý z ostatných vrcholov z V i obsahuje jednu hranu, ako v G. Ak v V i, potom je dosiahnuteľný od koreňa r i definíciou grafu G i. Od | V i | n, potom induktívnym predpokladom. Potom graf G získame indukčným pravidlom (2) z Definície 10.3 zo stromov G 1,…, G k a preto patrí do triedy.
⇐ Ak nejaký graf G = (V, E) patrí do triedy, potom splnenie podmienok (1) - (3) z definície 10.2 možno preň ľahko zistiť indukciou definíciou 10.2. Necháme to na citateľa ako cvičenie.
K orientovaným stromom sa viaže bohatá terminológia, ktorá pochádza z dvoch zdrojov: botaniky a oblasti rodinných vzťahov.
Koreň je jediný vrchol, ktorý nevstupuje do okrajov, listy sú vrcholy, ktoré z okrajov nevychádzajú. Cesta od koreňa k listu sa nazyva vetva stromu. Vyška stromu je maximálna dĺžka jeho konárov. Hĺbka vrcholu je dĺžka cesty od koreňa k tomuto vrcholu. Pre vrchol v V tvorí podgraf stromu T = (V, E), ktorý zahŕňa všetky vrcholy dosiahnuteľné z v a hrany z E, ktoré ich spájajú, podstrom T v stromu T s koreňom v (pozri Problém 10.3). Výška vrcholu v je výška stromu T v. Graf, ktorý je spojením niekoľkých nesúrodých stromov, sa nazýva les.
Ak hrana vedie z vrcholu v do vrcholu w, potom sa volá v otec w a w - sina v (nedávno sa v anglofónnej literatúre používa asexuálna dvojica výrazov: rodič - dieťa). Z definície stromu priamo vyplýva, že každý vrchol, okrem koreňa, má jediného otca. Ak cesta vedie z vrcholu v do vrcholu w, potom v sa nazyva predok w a w je potomkom v. Vertice, ktoré majú spoločného otca bratia alebo sestry.
Vyberme si ďalšiu triedu grafov zovšeobecňujúcich orientované stromy – orientované acyklické. Două typy takto označených grafov budú použité nižšie na znázornenie boolovských funkcií. Tieto grafy môžu mať niekoľko koreňov - vrcholov, ktoré neobsahujú hrany a každý vrchol môže obsahovať niekoľko hrán a nie jednu, ako je to v stromoch.
počítac tehnologie, najma program ... 2009 roku Zakladna skola je experimentalne miesto n / A zavedenie federalneho stat ...
M MONITORING MÉDIÍ Modernizácia odborného vzdelávania marec - august 2011
ZhrnutieUnit stat skúsky" n / A výber": informácie počítactehnologie, biologie a literaturii. Mimochodom, v tomto stâncă Jednotná státna skúška... otazka„O výsledkoch realizácie program rozvoj národnych výskumnych univerzít v 2009 -2010 stâncos". ...
PROGRAM STRATEGICKÝ ROZVOJOVÝ Tver 2011
programV 2009 stâncă... Štrukturálne zmeny pozorovane v roku 2010 stâncăn / A vzah k 2009 , ... Profesionale – orientavany cudzi jazyk "," Moderne vzdelávanie tehnologie"... V každom program pokročile školenie, modul " Stat ...
DOSTUPNOSŤ A PREPOJENIE V GRAFOCH Osnova prednášky: Okruhové trasy a cykly. Grafová online a komponenty onlinevity. Priemer je polomer a stred grafu.
Zdieľajte svoju prácu na sociálnych sieťach
Ak vám táto práca nevyhovovala, v spodnej časti stránky je zoznam podobných prác. Môžete tiež použiť tlačidlo vyhľadávania
Baranov Viktor Pavlovic. Diskretna matematica. Chas 3.Grafy, siete, kody.
Prednaška 8. Dosah a onlinevita v grafoch
Prednaska 8. DOSAH A KONEKTIVITA V GRAFOCH
Plan prednašok:
- Trasy, reťazce un cykly.
- Grafová online a komponenty onlinevity.
- Priemer, polomer a stred grafu.
- Matrice dosiahnuteľnosti a kontradosiahnuteľnosti.
- Cesty, reťaze un slucky
Orientovana trasa(alebo podľa ) digrafu je postupnosť oblúkov, v ktorej konečný vrchol akéhokoľvek oblúka okrem posledného je počiatočným vrcholom nasledujúceho. Na obr. 1 consecință oblukov
, (1)
, (2)
(3)
su cesty.
Ryza. jeden.
Orientovana reťaz(alebo reťaz ) sa nazýva dráha, v ktorej každý obluk a S nepoužíva viac ako raz. Takže napríklad cesty (2) a (3) sú reťazce, ale cesta (1) nie, pretože oblúk je v nej použitý dvakrát.
Jednoduche sa nazýva reťazec, v ktorom je každý vrchol použitý najviac jeden O ty krat. Napríklad reťazec (3) je jednoduchý, ale reťazec (2) nie je.
Trasa je neusmernené dvojča cesty, teda postupnosť hrán, v ktorej každá hrana, okrem prvej a postlednej, je spojená koncovými vrcholmi s hranami a. Lišta nad symbolom obluka znamená, že sa považuje za hranu.
Podobne ako sme definovali reťazce a jednoduché reťazce, môžeme definovať reťazce a jednoduché reťazce.
Cesta alebo trasa môže byť tiež znázornená ako postupnosť vrcholov. Napriklad A opatrenia, cestu (1) možno zapísať ako:.
Cesta sa nazyva uzavreta ak sa počiatočný vrchol oblúka v ňom zhoduje s koňom h noah vchol obluka. Uzavreté orchainy (reťazce) sú tzv saucicluri (ciclu ). Orcycles su tiež tzv obrysy ... Uzavreté jednoduché orchainy (reťaze) sa nazývajú su jednoduche orcykle(ciclu v). Uzavreta trasaje nonorientovany n dvojnasobok uzavretého n na odpalisku.
- Grafova online a komponenty online
Hovorí sa, že vrchol v digrafe je dosiahnuteľný z vrcholu, ak existuje cesta. Ak je zároveň dosiahnuteľný z, potom sa hovorí, že tieto vrcholy sú vzájomne dosiahnuteľné.
Digraf sa nazyva silne spojený alebo silny. ak su v ňom nejaké dva vrcholy A Sú veľmi disponibile. Príklad silneho digrafu je znázornený na obr. 2a. Keďže v graphe ich e je orcyklus, ktorý zahŕňa všetky vrcholy, potom ktorékoľvek dva z nich zaberu ale su veľmi dostupne.
° ° °
° ° ° ° ° °
° ° ° ° ° °
a B C
Ryza. 2.
Digraf sa namevajednosmerne pripojene alebo jednostranne ak v ktorejkoľvek dvojici jeho vrcholov je aspoň jeden dosiahnuteľný z druhého. Príklad jednostranneho grafu je na obr. 2b. Tento graf obsahuje orcyklus obsahujúci štyri vzájomne dosiahnuteľné vrcholy. Vrchol má nulový stupeň priblíženia, čo znamená, že do tohto vrcholu nevedú žiadne cesty. V tomto prípade je možné dosiahnuť ktorýkoľvek z ostatných štyroch vrcholov.
Digraf sa nameva slabo pripojený alebo slaby ak existujú nejaké dva vrcholy s o zjednoteny na polceste ... Polovičná cesta v lemovane obluky. Príklad slabého digrafu je na obr. 2 c. Je zrejme, ze graf neobsahuje n pri medzi vrcholmi a, ale existuje polovičná cesta pozostávajúca z opaku A vládnuce obluky a.
Ak pre niektorú dvojicu vrcholov neexistuje trasa, ktorá by ich spájala, potom m A ktory digraf sa nazyva nevăzut.
Pre digraf sú definované tri typy komponentov connectivity:silna zlozka- ma k podgraf extrem de puternic,componenta jednostranny- maxim jeden O ronny podgraf acomponentă slabăJe najslabsim podgrafom.
Koncept silnej zložky je znázornený na obr. 3.
° ° ° ° ° °
° ° ° °
° ° ° ° ° °
° ° ° ° ° °
° ° °
° ° ° ° °
Ryza. 3
Jednosmerne prepojený graf obsahuje šesť silných palcov d grafov, z ktorých su len silné zložky n tami. Koncept jednostranného komponentu je znázornený podobným spôsobom. V tomto priklade e Jednostranná zložka je rovnaká ako samotný graf. Ak zmenite orientáciu A oblúk, napríklad do opačného, potom získame slabý graf s dvoma jednosmernými O tretie zložky, z ktorých jedna je tvorená vrcholmi a druhá je p pneumatice.
Pre nonorientovaný graf definujeme na množine jeho vrcholov zásobník R vzťah, za predpokladu, že existuje reťazové prepojenie s. Tento postoj je obl A dáva vlastnosti reflexivitate, symetrie a priechodnosti, teda ide o T echivalencia nosenia. Rozdeľuje množinu vrcholov do disjunktných a încercat:. Dva vrcholy z rovnakej triedy sú ekvivalentné, to znamená, že v grafe existuje reťazec, ktorý ich spája, pre vrcholy z rôznych tried takýto reťazec neexistuje. Od conca l Yu Ak sú hrany vo vzťahu, potom sa množina hrán grafu tiež rozdelí na disjunktné triedy:, kde označuje množinu všetkých hrán, ktorých konce patria do,.
Grafy su prepojené a tvoria jeden graf. Tieto graffy sa nazyvajucomponentry pripojeniagrafic. Číslo je ďalšou číselnou charakteristikou grafu. Pre pripojený graf, ak je graf odpojený, potom.
Ak daný graf nie je spojený a rozdeľuje sa na niekoľko komponentov, potom sa riešenie akejkoľvek otázky týkajúcej sa tohto grafu spravidla môže zredukovať na štúdium jednotlivých komponentov, ktoré senúcej. Preto má vo väčšine prípadov zmysel predpokladať, že daný graf je súvislý.
- Priemer, polomer a stred graf
Pre spojený graf definujte vzdialenosť medzi jeho dvoma vrcholmi a ako dĺžku najkratšieho reťazca spájajúceho tieto vrcholy a označíme. Dĺžka reťaze je počet hrán, ktoré tvoria reťaz. Je ľahké skontrolovať, či ste zadali n Táto vzdialenosť spĺňa axiomie metrica:
2) ;
3) .
Určme vzdialenosť od každého vrcholu grafu k vrcholu, ktorý je od neho najďalej
ktora sa volavýstrednosť... Je zrejmé, že excentricita pre všetky vrcholy v úplnom grafe sa rovná jednej a pre vrcholy jednoduchého cyklu -.
Maximalna excentricita je tzv grund graf un minimum je polomer grafic. V kompletnom grafe máme, a v jednoduchom cykle -.
Vrchol sa nazyva centrallny dacă. Graf môže mať niekoľko b k takýmto vrcholom a v niektorých grafoch sú všetky vrcholy centralálne. V jednoduchom reťazci je pre nepárny počet vrcholov iba jeden stredový a pre párny počet vrcholov S Existuju dva taketo vrcholy. V úplnom grafe a pre jednoduchý cyklus sú všetky vrcholy centralálne. Množina stredových vrcholov je tzv stred grafic.
Priklad 1 Nájdite priemer, polomer a stred grafu znázorneneho on obr. 4.
° °
° ° °
° °
° °
Ryza. 4.
Na vyriešenie tohto problemu je vhodné predbežne vypočítaťmatica vzdialenosti medzi vrholmi a mi pocitať. V tomto prípade to bude matica veľkosti, v ktorej je vzdialenosť od vrcholu k vrcholu na mieste:
Pre každý riadok matice nájdeme najväčší prvok a zapíšeme ho ako A wa z pomlky. Najväčšie z týchto čísel sa rovná primeru grafu, najmenšie je p A dius pocket. Stred grafu tvoria stredové vrcholy a.
Pojmy centrálny vrchol a stred grafu sa objavili v súvislosti s problémami veľkoobchodu A minimálne umiestnenie čakacích miest, ako sú nemocnice, hasiči, stanice verejného poriadku atď., keď je dôležité minimalizovať A väčšia vzdialenosť od ktoréhokoľvek bodu určitej siete k najbližšiemu servisnému bodu niya.
- Matrice dosiahnuteľnosti a kontradosiahnuteľnosti
Matica dosiahnuteľnostiam definit nasledovne:
Množina vrcholov grafu dosiahnuteľná z daného vrcholu pozostáva z prvkov, pre ktoré je tý prvok v matici 1. Túto množinu možno znázorniť ako
Matica protidosiahnuteľnosti (spätná dosiahnuteľnosť) definivať i sa robi nasledovne:
Podobne ako pri konštrukcii dosiahnuteľnej množiny možno vytvoriť mn O gesto s použitím nasledujúceho výrazu:
Z definícií vyplýva, že tý stĺpec matice sa zhoduje s tý riadkom ma T matice, t.j. kde je matica transponovana do matice.
Priklad 2 Nájdite matice dosiahnuteľnosti a kontrareachability pre graf, pr A znázornene pe obr. 5.
Ryza. 5.
Definujme množiny dosiahnuteľnosti pre vrcholy grafu:
V dôsledku toho majú matice dosiahnuteľnosti a kontraprístupnosti tvar:
Keďže existuje množina takýchto vrcholov, z ktorých každý patrí aspoň jednej ceste vedúcej z do, vrcholy tejto množiny sa nazývajú sú nevyhnutné alebo inherentné vzhľadom na koncove vrcholy a. Všetky ostatné vrcholy sú tzvbezvyznamny alebo nadbytočne keďže ich vymazanie neovplyvní cesty od do.
Môžete tiež definivať matice obmedzene dosiahnuteľnosť a protiúspech A mosty, ak požadujete, aby dĺžky ciest nepresiahli určitý daný počet. Potom to bude horná hranica dĺžky prípustných ciest.
Graf sa nazyva transitivny ak z existencie oblukov a stopy pri existența obluka.Transitivny uzavergraf je graf, kde je minimálna možná množina oblúkov potrebná na to, aby bol graf tranzitívny. Je zrejmé, že matica dosiahnuteľnosti grafu sa zhoduje s maticou susednosti grafu, ak do matice umiestnime jednotky na hlavnej diagonále.
G (V, X) so slučkami, ale bez viacerých oblúkov definuje binárnu reláciu X na množine V. Úplný graf zodpovedá univerzálnemu vzťahu. Neorientovaný graf zodpovedá symetrickému vzťahu. Doplnok grafu zodpovedá doplnku vzťahu. Zmena smeru oblukov zodpovedá opačnému vzťahu.
Digrafy a binárne vzťahy sú rovnaká trieda objektov opisaných rôznymi prostriedkami. Binárne vzťahy, funkcie sú základnými nástrojmi na zostavenie drvivej väčšiny matematických modelov, ktoré sa používajú na riešenie praktických problémov, a grafy je možné vizualizovať vo forme diagrama. To vysvetľuje rozšírené používanie diagramov rôznych typov v kódovaní a dizajne.
Vrchol b digrafu (grafu) G sa nazyva dosiahnuteľne z U vtedy a len vtedy, ak U = V alebo existuje cesta (trasa) spájajúca U s V (U je počiatočný vrchol, V je konečný vrchol). Na množine vrcholov digrafu (grafu) je teda definovaný nielen vzťah susednosti A, ale aj vzťah dosiahnuteľnosti T.
Matica dosiahnuteľnosti T digraf (graf) G sa nazýva T 2 n × n, ktorého prvky sa nachádzajú z podmienky: 1, ak je dosiahnuteľný z; 0, ak nie je dosiahnuteľný z.
Určenie matice dosiahnuteľnosti digrafu ako matice reflexného a tranzitívneho uzavretia vzťahu susednosti.
Zavedený vzťah dosiahnuteľnosti vo vrcholoch grafu G (V, X): vrchol w je dosiahnuteľný z vrcholu v, ak v = w alebo G má cestu z v do w. Inými slovami, dosiahnuteľnosť je reflexívne a tranzitívne uzavretie vzťahu susedstva.
Nájdite maticu susednosti, tranzitívne a reflexné uzavretie.
Konektivita v grafoch. Slabá, jednostranná a silná online v digrafoch. Konektivita a silna matica onlinevity. Komponenty pripojenia. Definiție matice silnej onlinevity na základe matice dosiahnuteľnosti.
G (V, X) sa nazyva pripojený ak je niektorý z jeho vrcholov dosiahnuteľný z akéhokoľvek iného vrcholu.
Digraf G (V, X) sa nazyva jednosmerne pripojene ak pre ktorékoľvek dva jeho vrcholy je najviac jeden dosiahnuteľný z druhého.
Digraf G (V, X) sa nazyva silne prepojený ak je niektorý z jeho vrcholov dosiahnuteľný z akéhokoľvek iného.
Digraf G (V, X) sa nazyva slabo pripojený ak je pripojený zodpovedajúci nedigraf získaný odstránením orientácie oblukov.
Digraf, ktorý nie je slabo spojený, sa nazyva nevvis.
Silny spojovací komponent Digraf G (V, X) sa nazýva maximálny, podľa počtu výskytov vrcholov, silne spojený podgraf daného digrafu. Spojená zložka nedigrafu je definovaná podobným spôsobom.
Silne prepojená (spojená) matica digraf (graf) G (V, X) sa nazýva S n × n, ktorého prvky sa nachádzajú z podmienky: 1, ak je dosiahnuteľný z a dosiahnuteľný z; 0, ak nie je dosiahnuteľný z a nedosiahnuteľný z.
(digraf) silne spojený alebo spojený, na to stačí určiť prítomnosť 0 v matici ak
0 nie je prítomný, potom je graf (digraf) spojený (silne spojený), inak nie.
Pevne spojená matica môže byť vytvorená z matice dosiahnuteľnosti pomocou vzorca
Nechaj V- množina vrcholov orientovaneho grafu F, E- mnohe jeho okraje. Kazde rebro eÎ E ma zaciatok v'Î V un koniec v''Î V... Sú teda dané dve zobrazenia j 1 a j 2, kde v'= j 1 ( e) - začiatok okraja e, v''= j 2 ( e) - koniec rebra e.
Je možné uviesť niekoľko definícií cesta v digraf F.
1. Cesta z vrcholov a hran je postupnosť L(v 0 ,e 1 ,v 1 ,e 2 ,...,e n,v n), kde v i- 1 = j 1 ( e i), v i= j 2 ( e i). Vertex v Vola sa 0 zaciatok cesty L,vchol v n - koniec cesty L, număr n hrany - jeho dĺžka... Cesta s jedným vrcholom má nulovú dĺžku.
2. Okrajova cesta je postupnosť ( e 1 ,e 2 ,...,e n). Tento concept cesty je analogicky s konceptom trasy v nonorientovanom graffe.
3. Cesta z vrcholov je postupnosť ( v 0 ,v 1 ,...,v n). Cesta z vrcholov je definovaná pre grafy, ktoré neobsahujú viacero hrán.
V praxi môžete použiť definíciu cesty, ktorá bude v tejto konkrétnej úlohe vhodnejšia.
Cesta je tzv orientovaný reťazec(alebo jednoducho reshaz keď sa berú do úvahy iba digrafy), ak sa v ňom každá hrana vyskytuje najviac 1-krát a jednoduchý orientovaný reťazec ak každý vrchol grafu F zasahuje najviac do dvoch jeho okrajov.
Priklad...cesta( e 5 ,e 6 ,e 7 ,e 1 ,e 4 ,e 3) (arr. 3.11) je or.reťaz a cesta ( e 7 ,e 1 ,e 4 ,e 3) - jednoduchý op. reshaz.
| Ryza. 3.11. |
Cesta je tzv orientovany cyklus(alebo jednoducho ciclu ak sa berú do úvahy iba digrafy), ak pozostáva z viac ako jedného prvku a jeho začiatok sa zhoduje s jeho koncom. Rovnako ako v prípade neorientovaného grafu, začiatok cyklu zvyčajne nie je pevny. Cyclus je tzv jednoduche ak každý vrchol, ktorý k nemu patrí, je incidentný presne s dvoma jeho okrajmi.
Priklad...cesta( e 1 ,e 4 ,e 3 ,e 2 ,e 5 ,e 6 ,e 7) - bicykel, cesta ( e 5 ,e 6 ,e 7) je jednoduchý cyklus.
V súvislosti s orientovanými reťazcami platí veta, ktorú dokázal Redei pri štúdiu kvadratických polí.
Veta 3.3. Nechaj F- konečný digraf, v ktorom je každá dvojica vrcholov spojená hranou. Potomv F cez všetky jeho vrcholy prechádza jednoduchý orientovaný reťazec.
ÿ Dôkaz sa vykoná metódou MI. Počet vrcholov v grafe označujeme ako n.
· n= 2: obluk spájajúci dva vrcholy grafu F 2 a cez všetky vrcholy grafu prechádza jednoduchý smerovaný reťazec.
Predpokladajme, ze pre n= m pre-graf Fm veta je pravdiva.
Dokažme to pre n= m+1 înainte de grafic Fm Veta +1 je pravdiva.
Zostavme si graf Fm+1 pridanim do grafu Fm nejaky top v m+1, ktorý má hrany ku všetkým vrcholom v i (i=1,2,...,m)od Fm... Podľa predpokladu existuje jednoduchý riadený reťazec prechádzajúci všetkými vrcholmi grafu Fm: Populudnie=(v 1 ,v 2 ,...,v m). Pre hrany dopadajuce na vrchol v m+1, sú tri možnosti.
1. Je tu obluk ( v m +1, v jeden). Pridaním do reťazca Populudnie„Naľavo“ dostaneme požadovaný reťazec prechádzajúci cez všetky vrcholy grafu Fm +1: Populudnie +1 =(v m +1 ,v 1 ,v 2 ,...,v m).
2. Je tu obluk ( v m , v m+1). Pridaním do reťazca Populudnie„Vpravo“ dostaneme požadovaný reťazec prechádzajúci cez všetky vrcholy grafu Fm +1: Populudnie +1 =(v m +1 ,v 1 ,v 2 ,...,v m,v m +1).
3. Ak je v graphe Fm+1 bez obluka ( v m +1 ,v 1), bez obluka ( v m,v m+1), potom pre niektorych k (k=2,3,...,m-1) určite bude obsahovať obluky ( v k,v m+1) a ( v m +1 ,v k+1). Urobme reťaz
Populudnie +1 =(v 1 ,v 2 ,...,v k,v m +1 ,v k +1 ,...,v m).
Tento reťazec prechádza všetkými vrcholmi grafu Fm +1 .
Na mnohych vrholoch V nastaviť postoj dosiahnuteľnosť R D takto: Vertex v'Î V je vo vzťahu R D svrcholom v''Î V(v tomto prípade sa hovori, že vrchol je v '' dosiahnuteľny zvrchu v'), ak existuje cesta L(v',... ,v'') deci začiatkom v' un koniec v''.
Podobne ako vzťah spojenia pre vrcholy neorientovaného grafu, vzťah dosiahnuteľnosť pre vrcholy orientevaneho grafu reflectorizant A tranzitiv, ale na rozdiel od vzťahu prepojenosti, vzťahu dosiahnuteľnosti nie nevyhnutne symetricke.
Vzťah dosiahnuteľnosti sa používa na definovanie rozdelenia množiny vrcholov digrafu do tried ekvivalencie: vrcholov v', v'' patria do rovnakej triedy, ak je vzťah symetrický, t.j. v'' dosiahnuteľny z v', A v' dosiahnuteľny z v''.
Nechaj L 1 (v', ... ,v'') A L 2 (v'', ... ,v') - zodpovedajuce cesty spájajúce tieto vrcholy. Potom spolo tvoria cyklus cez vrcholy v' A v''... Akékoľvek vrcholy rovnakej triedy ekvivalencie teda patria do určiteho cyklu. Ak v grafe nie sú žiadne cykly, potom každá trieda ekvivalencie pozostáva z jedného vrcholu.
| Ryza. 3.13. |
Grafică minimă FB, indukujuce na množine vrcholov V rovnaký vzťah dosiahnuteľnosti ako daný orientovaný graf F, t.j. sa nazyva graf s neredukovateľnou množinou hrán zakladny graf pre-graf F.
Ak existuje základný graf, potom nemusí byť nevyhnutne jediný. Takže pre graf na obr. 3.13, akykoľvek radiálna hrana a orientovaný polygonálny cyklus definujú základný graf.
Ak F- konečný digraf, potom existujú základné grapy; možno ich získať postupným odstraňovaním "nepotrebných" okrajov ( v 0 ,v n), pre ktore existuje okraj bez ( v 0 ,v n) orientovaný reťazec R(v 0 ,v n).
Nachitava...