Matice sousednosti NG V = [ vij ] celočíselná čtvercová matice řádu |U| vij = | ρ-1( [ui, uj] ) | ... tedy počet hran mezi ui a uj ?Jaké vlastnosti má matice sousednosti? ? Smyčky, rovnoběžné hrany? V = VT Vr = [vij(r) ] ... počet sledů délky r mezi ui a uj A . AT = V + D, D = [ dii ], kde dii = δ(ui) Reprezentace grafů - odst. 4.1
TI 4 / 1
Matice incidence OG
A = [ aik ] celočíselná obdélníková matice typu |U| x |H| 1 .... hrana hk vystupuje z uzlu ui aik = -1 .... hrana hk vstupuje do uzlu ui 0 .... jinak ? Co nám říká matice incidence o grafu? Vlastnosti matice incidence OG jsou podobné jako jsme viděli u NG.
Reprezentace grafů - odst. 4.1
TI 4 / 2
Matice sousednosti OG V = [ vij ] celočíselná čtvercová matice řádu |U| vij = | σ-1( [ui, uj] ) | ... tedy počet hran z ui do uj ?Jaké vlastnosti má matice sousednosti? V* = ∑ Vi , i=0, ... d,
kde d = min(|H|, |U|-1)
matice dostupnosti R = [rij ], rij = 1 pokud ui →* uj, jinak 0 rozklad na silné komponenty R’ = R ∩ RT A . AT = D - V - VT , D = [ dii ], kde dii = δ +(ui)+ δ -(ui) Reprezentace grafů - odst. 4.1
TI 4 / 3
Spojová reprezentace grafu N.G. - seznamy sousedů Adj[u]
O.G. - seznamy následníků
1: 2: 3:
|U|:
Srovnání paměťové složitosti: NG A: |U|.|H| (bitů!) V: |U|.|U| (integer ? Boolean) Adj: |U| + 2.|H| OG Adj: |U|+|H| Reprezentace grafů - odst. 4.1
TI 4 / 4
Prohledávání grafu do šířky BFS - Breadth-First Search Je zadán graf G = 〈H,U,σ〉 (není podstatné, zda NG nebo OG) a jeho uzel u ∈ U. Prohledáním do šířky dostaneme strom (nejkratších) s →* u cest Stavy uzlů: FRESH - nový (dosud neobjevený) uzel OPEN - právě objevený („nadějný“) uzel CLOSED - vyčerpaný uzel Prohledávání do šířky - odst. 4.2
TI 4 / 5
s
k
k+1
u v
Datové struktury: stav[u] - FRESH / OPEN / CLOSED d[u] - zjištěná vzdálenost s →* u p[u] - předchůdce uzlu u (viz fronta OPEN uzlů Prohledávání do šířky - odst. 4.2
)
TI 4 / 6
BFS (G, s) . . . pseudokód 1 for každý uzel u ∈U-{s} do 2 stav[u]:=FRESH; d[u]:=∞; p[u]:=nil 3 stav[s]:=OPEN; d[s]:=0; p[s]:=nil; 4 InitQueue; Enqueue(s); 5 while not EmptyQueue do 6 u:=QueueFirst; 7 for každé v ∈ Adj[u] do 8 if stav[v]=FRESH 9 then stav[v]:=OPEN; d[v]:=d[u]+1; 10 p[v]:=u; Enqueue(v); 11 Dequeue; 12 stav[u]:=CLOSED Prohledávání do šířky - odst. 4.2
TI 4 / 7
OPEN 0
CLOSED
strom
1
1
Prohledávání do šířky - odst. 4.2
TI 4 / 8
Vlastnosti BFS algoritmu cykl 1 - 4 .... O(|U|) Složitost: operace s frontou O(1) na uzel ⇒ celkem O(|U|) cykly 5 + 7 pro každého souseda ... O(|H|) ⇒ O(|U| + |H|) Vlastnosti: • pro každou hranu h∈H : h=(u, v) platí d(s,v) ≤ d(s, u)+1 • d[v] ≥ d(s, v) • pokud fronta obsahuje uzly v1, v2, ..., vr, potom platí d[vr] ≤ d[v1] + 1 d[vi] ≤ d[vi+1] pro i=1,2,...,r-1 • konec: d[v]=d(s,v) a (p[v],v) je hrana nejkratší cesty s →* v Prohledávání do šířky - odst. 4.2
TI 4 / 9
Prohledávání grafu do hloubky DFS - Depth-First Search Výsledkem bude DF strom (nebo les) Uzly jsou opět FRESH, OPEN nebo CLOSED, ale mají časové značky s hodnotami 1 … 2*|U| – d[u] přidělí se uzlu při jeho otevření – f[u] přidělí se uzlu při jeho uzavření (tzn. d[u]
TI 4 / 10
DFS (G) pseudokód 1 for každý uzel u ∈U do 2 stav[u]:=FRESH; p[u]:=nil; 3 i:=0; 4 for každý uzel u ∈U do 5 if stav[u] = FRESH then DFS-Projdi(u); DFS-Projdi(u) 1 stav[u]:=OPEN; i:=i+1; d[u]:=i; 2 for každý uzel v ∈Adj[u] do 3 if stav[u] = FRESH 4 then p[v]:=u; DFS-Projdi(v); 5 stav[u]:=CLOSED; i:=i+1; f[u]:=i; Prohledávání do hloubky - odst. 4.3
TI 4 / 11
OPEN
CLOSED
strom
1/
1/
1/
2/
2/
2/
3/
2/5
Prohledávání do hloubky - odst. 4.3
3/4
2/5
2/
3/4 7/
1/6
1/
3/4
1/
1/
1/
3/
2/
1/6
2/5
3/4 TI 4 / 12
Složitost DFS
cykly 1 - 2 a 4 - 5 ...
O(|U|)
DFS-Projdi ... volá se |U|/krát cykl 2 - 4 ... |Adj[u]|-krát , tedy celkem ∑|Adj[u]| = Θ(|H|) ⇒ O(|U|+|H|)
Prohledávání do hloubky - odst. 4.3
TI 4 / 13
Vlastnosti DFS • závorkový teorém: nastává právě jedna z možností – 〈d[u], f[u]〉 ∩ 〈d[v], f[v]〉 = ∅ (vztah intervalů) – 〈d[u], f[u]〉 ⊂ 〈d[v], f[v]〉 - potom v → u (v DFS stromu) – 〈d[v], f[v]〉 ⊂ 〈d[u], f[u]〉 - potom u → v (v DFS stromu)
• vnořování intervalů: u → v (v DFS lese) ⇔ d[u] < d[v] < f[v] < f[u] • teorém o nové cestě: u → v (v DFS lese) ⇔ v okamžiku d[u] existuje „nová“ cesta P(u, v) • stromové / zpětné / dopředné / příčné hrany Prohledávání do hloubky - odst. 4.3
TI 4 / 14
? Jak se pozná typ hrany (u, v)? FRESH v ⇒ stromová OPEN v ⇒ zpětná CLOSED v ⇒ dopředná nebo příčná ? d[u] < d[v] d[u] > d[v] ? DFS neorientovanáho grafu ? Orientace hrany se provede podle prvního průchodu, takže dostaneme jen stromové a zpětné hrany.
Prohledávání do hloubky - odst. 4.3
TI 4 / 15
Topologické uspořádání Top-Sort-1 (G) • S:=∅ • prováděj DFS(G) a v okamžiku f[u] ulož uzel u na začátek seznamu S • S obsahuje uzly v topologickém uspořádání V:
G je acyklický ⇔ DFS(G) neobjeví zpětnou hranu
Top-Sort-2 (G)
eliminací kořenů - viz dříve
δ[u] = δG[u] M - množina kořenů (fronta) Prohledávání do hloubky - odst. 4.3
TI 4 / 16
Silné komponenty
S-COMP (G) • pomocí DFS(G) se určí f[u] pro všechny u ∈ U • vytvoří se G- (opačně orientovaný graf) • provede se DFS(G-) s tím, že uzly v hlavním cyklu se berou v klesajícím pořadí f[u] • stromy DFS-lesa určují silné komponenty
Prohledávání do hloubky - odst. 4.3
TI 4 / 17
1/22
2/21
19/20
1/6
15/16
3/18
10/17
4/9
5/8
12/13
11/14
6/7
3/4
7/12
17/22
2/5
8/11
14/15 Prohledávání do hloubky - odst. 4.3
9/10
13/16
19/20
18/21 TI 4 / 18
