0000040 2
<.x.y>c6° <=> [V (Ua .^(jc.y)] A [ V -^(y.X)]
Z określonla tej relacji wynika, że jeot ona zwrotna, oymetry-czna i przechodnio. Oeat zatem relacją równoważności, która dziali zbiór wierzchołków X na jej rozłączne klaoy obotrekcji 1 tym samym dziali graf (hlpergraf) na ekłodowa ollnoj epój -noócl.
Składowo allnaj spójności Jeat to maksymalny podgraf, który jeat grafea ailnie opójnyo.
Ilość składowych silnej spójności oznaczymy przez 3£D(G)
1 4 JC*(G) 4 n; n • |X|
Efaktywnya algorytmom wyznaczania wszystkich składowych silnej spójności jest olgorytm Lelfmane [29] opisany w rozdzlolo 6. dotyczącym dróg w grafach skierowanych.
5.4. Łańcuchy najkrótoze
Oznoczymy przez ^ (xp,xk) łańcuch
dla którego x. •
d k° *
Przez t(*p,x ) oznaczymy zbiór różnych łańcuchów
Długość każdego łońcucha jest równo 1 xp ,xk )J .
oroz
Ł a
ustalone
ń c u c h e
najkrótszy
dwa wierzchołki
^Bin(xP.* )€Ł(xP.x ). <*!« którego
nazywamy
1[y«inłxP‘xk>]- Bin 1 [^1(xP.xk)]
ijCŁOW
Hożo być wiele różnych łańcuchów najkrótszych w zbiorze *Ł(xp,xk).
TWIERDZENIE 5.8
Oeóli łańcuch jest najkrótezy, to jest łańcucha# prootyn.
Dowód tago twierdzenia nożna pooinęć za względu no oczywistość jago tezy.
TWIERDZENIE 5.9
Łańcuch jaot najkrótszy wtedy 1 tylko wtedy, gdy każdy jago odcinek jest odpowiednim łańcuchem najkrótszym.
O o w ó d s
Oeśli każdy odcinak jest łańcuchem najkrótszym, to oczy -wlóclo 1 cały łańcuch, jako azczególny odcinek, jest najkrótszy. Wystarczy zetem dowieóć, że Jeżeli łańcuch ^min(xP.*k) Jeat najkrótszym, to każdy odcinek tego łańcucha jest odpowiednia łańcuchem najkrótszym. Załóżmy przeolwnle, że istnieje odcinek
Sytuaojs taka jest możliwa tylko w tym przypadku, gdy niektóre gałęzie tworzęce łońcuch m^xi'xi) występuję w łańcuchu irln(xp,xk) przed wierzchołkiem lub po wierzchołku Xj. Wtedy Jednak można skrócić łańcuch ^min(xP*xk)* 00 #toi w sprzeczności z definicję łańcucha najkrótszego 1 przeczy założeniu. Uzyskana sprzeczność kończy dowód twierdzenia.
Teza twierdzenia 5.9 umożliwia zastosowanie motody programowania dynamicznego (patrz 0.2) do wyznaczanie łańcuchów najkrótszych, łęczęcych ustalony wierzchołek xp z pozostałymi wlerzchołkooi grafu (hipergrefu), epójnyoi z wierzchołkiem xp. Etapy toj metody okreólajo następująco podzbiory wierzchołków]
|
x0*.. |
. j , |
gdzie |
|
xo • |
{*1 . | |
|
X1 • |
(*, £ * \ *0 ■ |
r13 > 0 A «1 e x„} |
|
• |
k*f |
% |
|
xk • |
{*3 tX\yox. |
i rij > o a e |
79
Wyszukiwarka
Podobne podstrony:
PTDC0044 ;go relacji wynika, że pomiędzy Rzymem a Galią istnia gole cnie więzi handlowe, a galijscy
2 (644) stykę ładowania akumulatora. Z przebiegu tej charakterystyki wynika, że przy wartości napięc
P1360889 I takich relacji wynika, że bio-jgchanika Meyerholda rzeczywiście „jfoywała w teatrze to, c
P1360889 I takich relacji wynika, że bio-jgchanika Meyerholda rzeczywiście „jfoywała w teatrze to, c
P1360889 I takich relacji wynika, że bio-jgchanika Meyerholda rzeczywiście „jfoywała w teatrze to, c
9 WYKŁAD i. PODSTAWY RACHUNKU PRAWDOPODOBIEŃSTWA Z definicji gęstości wynika, że ma ona własności: a
DSC07120 (4) 170 Badanie funkcji Z postaci funkcji d wynika, że przyjmuje ona warto# najmniejszy w p
skanuj0009 (243) teratury do literatury. W tej relacji ipo obu atroiM^fe występują takie cechy jak b
IMG$60 IĘZYK I MbTODA 144 KS. lf IŁ. i i że porządek diatoniczny powstaje z tej progresji, wyni
skanuj0008 Z wypowiedzi tej wynika, że używane w języku potocznym synonimi-cznie: język i mowa, w ję
16212 ullman068 (2) 142 3. RELACYJNY MODEL DANYCH sy i broń, które pochodzą z pozostałych dwóch nadk
Nazwa tej konstrukcji wynika z zastosowanego w niej podziału masy koła zamachowego na dwie osobne ta
organizacyjnych, zakresie i rodzaju kontroli i oceny pracy uczniów, a także określają charakter rela
więcej podobnych podstron