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 ktorých sa koncept používa dosiahnuteľnosť, dosť málo.
Tu je jeden z nich. Graf 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 takáto cesta existuje, potom vrcholy j dosiahnuteľné 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 vrcholov v grafe atď. úlohy.
Dosiahnuteľnosť v grafe je opísaná 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,
r ij = 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. Je zrejmé, že všetky diagonálne prvky v matici R sú rovná 1, keďže každý vrchol je dosiahnuteľný sám od seba cestou dĺžky 0. Keďže priame zobrazenie 1. rádu Г +1 (xi) je množina takých vrcholov xj, ktoré sú dosiahnuteľné z xi pomocou ciest dĺžky 1, potom množina Г + (Г +1 (xi)) = Г +2 (xi) pozostáva z vrcholov dosiahnuteľných z xi pomocou ciest dĺžky 2. Podobne Γ + 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, ... alebo p, množinu vrcholov dosiahnuteľných pre vrchol x i možno znázorniť ako
R (x i) = (x i) Г +1 (x i) Г +2 (x i) ... Г + 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.
Ryža. 4.1. Dosiahnuteľnosť v grafe: a - graf; b - matica susednosti; c - matica dosiahnuteľnosti; r - matica protidosiahnuteľnosti.
Pre graf znázornený na obr. 4.1, a, súbor 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) = (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).
Matica dosiahnuteľnosti má tvar znázornený na obr. 4.1, c. Matica dosiahnuteľnosti môže byť postavené matica susednosti(obr. 4.1, b), tvoriace množiny T + (x i) pre každý vrchol x i.
Protidosiahnuteľná matica 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ľné množina Q (x i) je množina takých vrcholov, že z ktoréhokoľvek vrcholu tejto množiny je možné dosiahnuť vrchol 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) = (x i) Г -1 (x i) Г - 2 (x i) ... Г -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ľná matica znázornené na 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 z x i 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.
Ryža. 4.2. Digraph
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 a a jk rovnajú 1, inak sa rovná 0. Keďže z rovnosti a ij = a jk = 1 vyplýva existencia cesty dĺžky 2 z vrcholu xi do vrcholu k, prechádzajúceho cez vrchol x j, potom sa (i-tý, k-tý) prvok matice А 2 rovná počtu dráh dĺžky 2 idúcich z x i do x k.
Tabuľka 4.1a ukazuje maticu susednosti grafu znázorneného na 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 na 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. Odpoveďou na túto otázku je vyššie uvedený vzťah dosiahnuteľnosti vo vrcholoch grafu 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žine V. V neorientovanom grafe sú triedy ekvivalencie vzhľadom na dosiahnuteľnosť sa nazývajú spojené komponenty. V prípade orientovaných grafov nemusí byť dosiahnuteľnosť vo všeobecnosti symetrickým vzťahom. Vzájomná dosiahnuteľnosť je symetrická.
Definícia 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 spojené komponenty graf.
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.
Definícia 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 grafe G je vrchol v dosiahnuteľný z vrcholu u ).
Príklad 9.3. Uvažujme graf G z príkladu 9.2.
Ryža. 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é):
Ryža. 9.3. Počet G *
Ako sa dá 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ĺžky 0, 1, 2 atď.
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 identity n × n. Dali sme 
... Nech je náš postup konštrukcie G * založený na nasledujúcom tvrdení.
Lema 9.2. Nechaj . Potom
Dôkaz indukciou na k.
Základ. Pre k = 0 ak = 1 je tvrdenie z definície pravdivé a.
Indukčný krok. Nech platí lemma 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 a a ij (k + 1) = 1. Ak je dĺžka najkratšej cesty z v i do v j rovná k + 1, potom nech v r je jej predposledný vrchol. Potom existuje dráha dĺžky k z v i do v r a podľa indukčnej hypotézy a ir (k) = 1. Keďže (v r, v j) E, potom a_ (rj) ^ ((1)) = 1. Preto a ir (k) a rj (1) = 1 a a 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 r j, potom a ir (k) = 1 a a rj (1) = 1. To znamená, že G má cestu z v i do v r dĺžky k a hranu (v r, v j) E. Ich spojením dostaneme cestu z v i do v j dĺžky k + 1.
Z Lem 9.1 a 9.2 okamžite získame
Dôsledok 1. Nech G = (V, E) je orientovaný graf s n vrcholmi a G * jeho graf dosiahnuteľnosti. Potom A_ (G *) =. Dôkaz. 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ť.
Príklad 9.3. Uvažujme ako príklad výpočet matice grafu dosiahnuteľnosti A G * pre graf G znázornený na Obrázok 9.2... V tomto prípade
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 Obrázok 9.3.
Vzájomná dostupnosť, pevne prepojené komponenty a základne grafov
Analogicky s grafom dosiahnuteľnosti definujeme silný graf dosiahnuteľnosti.
Definícia 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 rovnajú 1, t.j.
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 vrchol 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 príklade 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.
Definícia 9.11. Nech K a K "sú silne spojené komponenty grafu G. Komponent K dosiahnuteľný 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ľný z K ^ \ prvočíslo, ak K K "a K je dosiahnuteľné z K". Zložka K sa nazýva minimálny, 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 vrcholov u K a v K ".
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". Na ryža. 9.4 tento graf komponentov je znázornený pre graf G uvažovaný vyššie.
Ryža. 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.
Definícia 9.12. Nech G = (V, E) je orientovaný graf. Podmnožina vrcholov W V sa nazýva generovanie 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.
Dôkaz 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 minimálneho komponentu sa stanú nedosiahnuteľnými. Preto je W základ.
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 implikuje nasledujúci postup na zostavenie jednej alebo vymenovania všetkých báz grafu G.
Nájdite všetky komponenty silného 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.
Príklad 9.5. Definujeme všetky bázy orientovaného grafu G znázorneného v Obrázok 9.5.
Ryža. 9.5. Graf G
V prvej fáze nájdeme komponenty silného spojenia G:
V druhej fáze vytvoríme striktný graf dosiahnuteľnosti pomocou týchto komponentov.
Ryža. 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) ...
Úlohy
Úloha 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.
Úloha 9.2. Uveďte všetky neizomorfné neorientované grafy s najviac štyrmi vrcholmi.
Úloha 9.3. Dokážte, že neorientovaný súvislý graf zostane spojený po odstránení nejakej hrany ↔ táto hrana patrí do nejakého cyklu.
Úloha 9.4. Dokážte, že neorientovaný súvislý graf s n vrcholmi
obsahuje aspoň n-1 hrán,
ak obsahuje viac ako n-1 hrán, tak má aspoň jeden cyklus.
Úloha 9.5. Dokážte, že v každej skupine 6 ľudí sú tri páry známych alebo tri páry neznámych ľudí.
Úloha 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.
Úloha 9.7. Dokážte, že ak má neorientovaný graf práve dva vrcholy nepárneho stupňa, potom sú spojené cestou.
Úloha 9.8. Nech G = (V, E) je neorientovaný graf s | E |< |V|-1. Докажите, что тогда G несвязный граф.
Úloha 9.9. Dokážte, že v prepojenom neorientovanom grafe majú akékoľvek dve jednoduché cesty maximálnej dĺžky spoločný vrchol.
Úloha 9.10. Nech neorientovaný graf bez slučiek G = (V, E) má k spojených komponentov. Tak to dokáž
Úloha 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:
Úloha 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.
Úloha 9.13. Stavať na dané ryža. 9.7 orientovaný graf G 1 = (V, E) jeho matica susednosti A G1, matica incidencie B G1 a zoznamy susedností. Vypočítajte maticu dosiahnuteľnosti A G1 * a zostrojte zodpovedajúci graf dosiahnuteľnosti G 1 *.
Ryža. 9.7.
Neorientované a orientované stromy
Stromy sú jednou z najzaujímavejších tried grafov používaných na reprezentáciu rôznych druhov hierarchických štruktúr.
Definícia 10.1. Neorientovaný graf sa nazýva strom, ak je spojený a nemá žiadne cykly.
Definícia 10.2. Orientovaný graf G = (V, E) sa nazýva (orientovaný) strom ak
Na ryža. 10.1 sú znázornené 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.
Ryža. 10.1. Neorientované a orientované stromy
To nie je náhoda. 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ýsledný orientovaný graf G "usmerovaný strom.
Neorientované a orientované stromy majú mnoho ekvivalentných vlastností.
Veta 10.1. Nech G = (V, E) je neorientovaný graf. Potom sú nasledujúce podmienky ekvivalentné.
G je strom.
Pre akékoľvek dva vrcholy v G existuje jedna cesta, ktorá ich spája.
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.
Dôkaz(1) (2): Ak by nejaké dva vrcholy v G boli spojené dvoma cestami, potom by G mal zjavne cyklus. To je však v rozpore s definíciou stromu v (1).
(2) (3): Ak je G spojené, ale po odstránení nejakej hrany (u, v) E nestráca konektivitu, potom medzi u a v existuje cesta, ktorá túto hranu neobsahuje. 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 (pozri problém 9.4).
(4) (5): Ak G obsahuje cyklus a je spojený, odstránenie akejkoľvek hrany z cyklu by 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 E 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 by G nebolo spojené, potom by 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 spojené a je stromom.
Pre orientované stromy je často vhodné použiť nasledujúcu induktívnu definíciu.
Definícia 10.3. Definujme indukciou triedu orientovaných grafov nazývaných stromy. Zároveň pre každý z nich definujeme vyhradený vrchol – koreň.
Ryža. 10.2 ilustruje túto definíciu.
Ryža. 10.2. Induktívna definícia orientovaných stromov
Veta 10.2. Definície riadených stromov v 10.2 a 10.3 sú ekvivalentné.
Dôkaz Nech graf G = (V, E) spĺňa podmienky definície 10.2. Ukážme indukciou na počte vrcholov | V | že.
Ak | V | = 1, potom jedinečný vrchol v V je podľa vlastnosti (1) koreň stromu, tj. tento graf nemá hrany: E =. Potom .
Predpokladajme, že je zahrnutý každý graf s n vrcholmi, ktorý spĺňa definíciu 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 čitateľ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 nazýva vetva stromu. Výš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 - syna 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 nazýva predok w a w je potomkom v. Vertices, ktoré majú spoločného otca, sa nazývajú bratia alebo sestry.
Vyberme si ďalšiu triedu grafov zovšeobecňujúcich orientované stromy – orientované acyklické. Dva 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čítač technológie, najmä program ... 2009 roku Základná škola je experimentálne miesto na zavedenie federálneho štát ...
M MONITORING MÉDIÍ Modernizácia odborného vzdelávania marec - august 2011
ZhrnutieUnited štát skúšky" na výber ": informácie počítačtechnológie, biológia a literatúra. Mimochodom, v tomto rok Jednotná štátna skúška... otázka„O výsledkoch realizácie programy rozvoj národných výskumných univerzít v 2009 -2010 roky". ...
STRATEGICKÝ ROZVOJOVÝ PROGRAM Tver 2011
ProgramV 2009 rok... Štrukturálne zmeny pozorované v roku 2010 rokna vzťah k 2009 , ... Profesionálne – orientovaný cudzí jazyk "," Moderné vzdelávanie technológie"... V každom program pokročilé školenie, modul “ Štát ...
DOSTUPNOSŤ A PREPOJENIE V GRAFOCH Osnova prednášky: Okruhové trasy a cykly. Grafová konektivita a komponenty konektivity. 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 Pavlovič. Diskrétna matematika. Časť 3.Grafy, siete, kódy.
Prednáška 8. Dosah a konektivita v grafoch
Prednáška 8. DOSAH A KONEKTIVITA V GRAFOCH
Plán prednášok:
- Trasy, reťazce a cykly.
- Grafová konektivita a komponenty konektivity.
- Priemer, polomer a stred grafu.
- Matrice dosiahnuteľnosti a kontradosiahnuteľnosti.
- Cesty, reťaze a slučky
Orientovaná 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 sekvencia oblúkov
, (1)
, (2)
(3)
sú cesty.
Ryža. jeden.
Orientovaná reťaz(alebo reťaz ) sa nazýva dráha, v ktorej každý oblúk 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.
Jednoduché sa nazýva reťazec, v ktorom je každý vrchol použitý najviac jeden O tý krát. 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 poslednej, je spojená koncovými vrcholmi s hranami a. Lišta nad symbolom oblúka 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. Napríklad a opatrenia, cestu (1) možno zapísať ako:.
Cesta sa nazýva uzavretá ak sa počiatočný vrchol oblúka v ňom zhoduje s koňom h noah vrchol oblúka. Uzavreté orchainy (reťazce) sú tzv orcycles (cykly ). Orcycles sú tiež tzv obrysy ... Uzavreté jednoduché orchainy (reťaze) sa nazývajú sú jednoduché orcykle(v cykloch). Uzavretá trasaje neorientovaný n dvojnásobok uzavretého n na odpalisku.
- Grafová konektivita a komponenty konektivity
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 nazýva silne spojený alebo silný. ak sú v ňom nejaké dva vrcholy a Sú veľmi dostupní. Príklad silného digrafu je znázornený na obr. 2a. Keďže v grafe ich e je orcyklus, ktorý zahŕňa všetky vrcholy, potom ktorékoľvek dva z nich zaberú ale sú veľmi dostupné.
° ° °
° ° ° ° ° °
° ° ° ° ° °
a B C
Ryža. 2.
Digraf sa nazývajednosmerne pripojené alebo jednostranné ak v ktorejkoľvek dvojici jeho vrcholov je aspoň jeden dosiahnuteľný z druhého. Príklad jednostranného 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 nazýva slabo pripojený alebo slabý ak existujú nejaké dva vrcholy s o zjednotený na polceste ... Polovičná cesta, na rozdiel od cesty, môže mať opačný smer v lemované oblúky. Príklad slabého digrafu je na obr. 2 c. Je zrejmé, že graf neobsahuje n pri medzi vrcholmi a, ale existuje polovičná cesta pozostávajúca z opaku a vládnuce oblúky a.
Ak pre niektorú dvojicu vrcholov neexistuje trasa, ktorá by ich spájala, potom m a ktorý digraf sa nazýva nesúvislý.
Pre digraf sú definované tri typy komponentov konektivity:silná zložka- ma k extrémne silný podgraf,jednostranný komponent- maximálne jeden O ronny podgraf aslabý komponentJe najslabším podgrafom.
Koncept silnej zložky je znázornený na obr. 3.
° ° ° ° ° °
° ° ° °
° ° ° ° ° °
° ° ° ° ° °
° ° °
° ° ° ° °
Ryža. 3
Jednosmerne prepojený graf obsahuje šesť silných palcov d grafov, z ktorých sú len silné zložky n tami. Koncept jednostranného komponentu je znázornený podobným spôsobom. V tomto príklade e Jednostranná zložka je rovnaká ako samotný graf. Ak zmeníte 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 pneumatiky.
Pre neorientovaný 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 reflexivity, symetrie a priechodnosti, teda ide o T ekvivalencia nosenia. Rozdeľuje množinu vrcholov do disjunktných tried:. 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 konca 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 sú prepojené a tvoria jeden graf. Tieto grafy sa nazývajúkomponenty pripojeniagraf. Čí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é sú spojené. Preto má vo väčšine prípadov zmysel predpokladať, že daný graf je súvislý.
- Priemer, polomer a stred grafu
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 axiómy metriky:
2) ;
3) .
Určme vzdialenosť od každého vrcholu grafu k vrcholu, ktorý je od neho najďalej
ktorá sa volávýstrednosť... Je zrejmé, že excentricita pre všetky vrcholy v úplnom grafe sa rovná jednej a pre vrcholy jednoduchého cyklu -.
Maximálna excentricita je tzv priemer graf a minimum je polomer graf. V kompletnom grafe máme, a v jednoduchom cykle -.
Vrchol sa nazýva centrálny if. Graf môže mať niekoľko b k takýmto vrcholom a v niektorých grafoch sú všetky vrcholy centrálne. V jednoduchom reťazci je pre nepárny počet vrcholov iba jeden stredový a pre párny počet vrcholov S Existujú dva takéto vrcholy. V úplnom grafe a pre jednoduchý cyklus sú všetky vrcholy centrálne. Množina stredových vrcholov je tzv stred grafu.
Príklad 1 Nájdite priemer, polomer a stred grafu znázorneného na obr. 4.
° °
° ° °
° °
° °
Ryža. 4.
Na vyriešenie tohto problému je vhodné predbežne vypočítaťmatica vzdialenosti medzi vrcholmi a mi počítať. 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 pomlčky. Najväčšie z týchto čísel sa rovná priemeru grafu, najmenšie je p a dius počet. 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ľnostije definovaný 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ť) definovať i sa robí 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 transponovaná do matice.
Príklad 2 Nájdite matice dosiahnuteľnosti a kontrareachability pre graf, pr a znázornené na obr. 5.
Ryža. 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 koncové vrcholy a. Všetky ostatné vrcholy sú tzvbezvýznamný alebo nadbytočné keďže ich vymazanie neovplyvní cesty od do.
Môžete tiež definovať matice obmedzené 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 nazýva tranzitívny ak z existencie oblúkov a stopy pri existencia oblúka.Tranzitívny uzávergraf 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 oblúkov zodpovedá opačnému vzťahu.
Digrafy a binárne vzťahy sú rovnaká trieda objektov opísaný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 diagramu. To vysvetľuje rozšírené používanie diagramov rôznych typov v kódovaní a dizajne.
Vrchol b digrafu (grafu) G sa nazýva dosiahnuteľné 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á konektivita v digrafoch. Konektivita a silná matica konektivity. Komponenty pripojenia. Definícia matice silnej konektivity na základe matice dosiahnuteľnosti.
G (V, X) sa nazýva pripojený ak je niektorý z jeho vrcholov dosiahnuteľný z akéhokoľvek iného vrcholu.
Digraf G (V, X) sa nazýva jednosmerne pripojené ak pre ktorékoľvek dva jeho vrcholy je najviac jeden dosiahnuteľný z druhého.
Digraf G (V, X) sa nazýva silne prepojený ak je niektorý z jeho vrcholov dosiahnuteľný z akéhokoľvek iného.
Digraf G (V, X) sa nazýva slabo pripojený ak je pripojený zodpovedajúci nedigraf získaný odstránením orientácie oblúkov.
Digraf, ktorý nie je slabo spojený, sa nazýva nesúvislý.
Silný 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 orientovaného grafu F, E- mnohé jeho okraje. Každé rebro eÎ E má začiatok v 'Î V a 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 digrafe F.
1. Cesta z vrcholov a hrán 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 Volá sa 0 začiatok cesty L,vrchol v n - koniec cesty L, číslo n hrany - jeho dĺžka... Cesta s jedným vrcholom má nulovú dĺžku.
2. Okrajová cesta je postupnosť ( e 1 ,e 2 ,...,e n). Tento koncept cesty je analogický s konceptom trasy v neorientovanom grafe.
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 reťaz 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.
Príklad... cesta ( e 5 ,e 6 ,e 7 ,e 1 ,e 4 ,e 3) (obr. 3.11) je or.reťaz a cesta ( e 7 ,e 1 ,e 4 ,e 3) - jednoduchý op. reťaz.
| Ryža. 3.11. |
Cesta je tzv orientovaný cyklus(alebo jednoducho cyklu 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 pevný. Cyklus je tzv jednoduché ak každý vrchol, ktorý k nemu patrí, je incidentný presne s dvoma jeho okrajmi.
Príklad... 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. Potom v 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: oblúk spájajúci dva vrcholy grafu F 2 a cez všetky vrcholy grafu prechádza jednoduchý smerovaný reťazec.
Predpokladajme, že pre n= m pre graf F m veta je pravdivá.
Dokážme to pre n= m+1 pre graf F m Veta +1 je pravdivá.
Zostavme si graf F m+1 pridaním do grafu F m nejaký top v m+1, ktorý má hrany ku všetkým vrcholom v i (i=1,2,...,m) od F m... Podľa predpokladu existuje jednoduchý riadený reťazec prechádzajúci všetkými vrcholmi grafu F m: Popoludnie=(v 1 ,v 2 ,...,v m). Pre hrany dopadajúce na vrchol v m+1, sú tri možnosti.
1. Je tu oblúk ( v m +1, v jeden). Pridaním do reťazca Popoludnie„Naľavo“ dostaneme požadovaný reťazec prechádzajúci cez všetky vrcholy grafu F m +1: Popoludnie +1 =(v m +1 ,v 1 ,v 2 ,...,v m).
2. Je tu oblúk ( v m , v m+1). Pridaním do reťazca Popoludnie„Vpravo“ dostaneme požadovaný reťazec prechádzajúci cez všetky vrcholy grafu F m +1: Popoludnie +1 =(v m +1 ,v 1 ,v 2 ,...,v m,v m +1).
3. Ak je v grafe F m+1 bez oblúka ( v m +1 ,v 1), bez oblúka ( v m,v m+1), potom pre niektorých k (k=2,3,...,m-1) určite bude obsahovať oblúky ( v k,v m+1) a ( v m +1 ,v k+1). Urobme reťaz
Popoludnie +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 F m +1 .
Na mnohých vrcholoch V nastaviť postoj dosiahnuteľnosť R D takto: Vertex v 'Î V je vo vzťahu R D s vrcholom v ''Î V(v tomto prípade sa hovorí, že vrchol je v '' dosiahnuteľný z vrchu v '), ak existuje cesta L(v ',... ,v '') so začiatkom v ' a koniec v ''.
Podobne ako vzťah spojenia pre vrcholy neorientovaného grafu, vzťah dosiahnuteľnosť pre vrcholy orientovaného grafu reflexívne a tranzitívne, ale na rozdiel od vzťahu prepojenosti, vzťahu dosiahnuteľnosti nie nevyhnutne symetrické.
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ľný z v ', a v ' dosiahnuteľný z v ''.
Nechaj L 1 (v ', ... ,v '') a L 2 (v '', ... ,v ') - zodpovedajúce cesty spájajúce tieto vrcholy. Potom spolu tvoria cyklus cez vrcholy v ' a v ''... Akékoľvek vrcholy rovnakej triedy ekvivalencie teda patria do určitého cyklu. Ak v grafe nie sú žiadne cykly, potom každá trieda ekvivalencie pozostáva z jedného vrcholu.
| Ryža. 3.13. |
Minimálny graf F B, indukujúce na množine vrcholov V rovnaký vzťah dosiahnuteľnosti ako daný orientovaný graf F, t.j. sa nazýva graf s neredukovateľnou množinou hrán základný graf pre graf F.
Ak existuje základný graf, potom nemusí byť nevyhnutne jediný. Takže pre graf na obr. 3.13, akýkoľvek radiálna hrana a orientovaný polygonálny cyklus definujú základný graf.
Ak F- konečný digraf, potom existujú základné grafy; možno ich získať postupným odstraňovaním „nepotrebných“ okrajov ( v 0 ,v n), pre ktoré existuje okraj bez ( v 0 ,v n) orientovaný reťazec R(v 0 ,v n).
Načítava ...