ORIENTOVANÉ GRAFY

transcript

TI 3.1

ORIENTOVANÉ GRAFY

V této části se seznámíme s následujícími pojmy:• orientovaný graf (OG), orientovaný multigraf,

prostý/obyčejný OG, zrušení/zavedení orientace, opačná orientace

• spojení, orientovaný tah, orientovaná cesta, cyklus, silně souvislý OG, silná komponenta, kondenzace OG

• vstupní/výstupní stupeň uzlu, množina následníků / předchůdců uzlu

Skripta odstavec 2.2, strana 28 - 33

TI 3.2

Co je to orientovaný graf ?

: H U U (množina uspořádaných dvojic)(h) = (u, v) ... počáteční / koncový uzel hrany h

u je následník uzlu v, v je předchůdce uzlu u

(h1) = (h2) ... rovnoběžné hrany => multigraf

Orientované grafy

G = H, U,

hrany grafu G uzly grafu G incidence

prostý orientovaný graf = graf bez rovnoběžných hran, tzn. hranu určují její krajní uzly => je zbytečné, G = H, U obyčejný orientovaný graf = prostý OG bez smyček

TI 3.3

Jinými slovy ...

Orientované grafy

Hrany v OG jsou orientované, tzn. pořadí uzlů je významné.

zrušení orientace

opačná orientace

zavedení orientace

TI 3.4

Jeden malý trik ...

Orientované grafy

Následující pojmy z neorientovaných grafů lze přenést do orientovaných grafů tak, že je uvažujeme na grafu vzniklém zrušením orientace:• sled (otevřený / uzavřený), složení sledů, tah, cesta, kružnice, souvislý graf, • komponenta grafu, strom, kostra grafu

Další pojmy lze zavést pro orientované grafy analogicky jako pro neorientované grafy:• podgraf, faktor, indukovaný podgraf • operace s grafy (sjednocení, průnik, rozdíl, symetrická diference a doplněk), disjunktní a hranově disjunktní grafy, • konečný / nekonečný graf, izomorfismus grafů

TI 3.5

orientovaný tah - spojení bez opakovaných hranorientovaná cesta – spojení bez opakovaných uzlů ( ani hran)otevřené x uzavřené spojení (orient. tah, orient. cesta)cyklus – uzavřená orientovaná cesta

Orientované grafy

? Tak proč vůbec orientovat hrany ?

Spojení (délky n) v orientovaném grafu G z uzlu u do uzlu v:

S = u0, h1, u1, h2, …, hn, un,

kde (hi) = (ui-1, ui), u0 = u, un = v

cbSpojení délky 10 z uzlu a do uzlu b (a b):

a, (a,b), b, (b,e), e, (e,a), a, (a,b), b, (b,c), c, (c,f), f, (f,b), b, (b,e), e, (e,a), a, (a,b), b

TI 3.6Orientované grafy

POZOR – spojení a sled v OG

Sled délky 3 z uzlu a do uzlu f (a f): a, [a,b], b, [b,e], e, [e,f], f(jako kdybychom zrušili orientaci)

Spojení délky 3 z uzlu a do uzlu f (a f): a, (a,b), b, (b,c), c, (c,f), f

Tento graf je souvislý.

Silně souvislý orientovaný graf G - pro každou dvojici uzlů u,v existují spojení jak z u do v tak i z v do u (u v & v u)

Spojení: a f ANO f a NEc d NE d c NEe ... NE ... a NE

graf není silně souvislý

cb Podmnožiny vzájemně propojitelných uzlů:{a}, {b,c,f}, {d}, {e}

Silná komponenta =maximální silně souvislý podgraf

Podmnožiny vzájemně propojitelných uzlů:{a,b,c,d,e,f}

graf je silně souvislý (tzn. je tvořen jedinou silnou komponentou)

Co dalšího lze říci o silně souvislých grafech?

Následující tvrzení jsou ekvivalentní:1) G je silně souvislý orientovaný graf2) G je souvislý a každá jeho hrana je v (nějakém) cyklu3) pro každý rozklad {U1, U2} množiny uzlů existují hrany

U1 U2 a U2 U1 D: 1 2 3 1

Důsledek: Když z grafu odebereme všechny silné komponenty, vznikne podgraf, který nemá žádné cykly ani hrany z nějakého cyklu původního grafu.

G' = G-( Gi), Gi - silné komponenty grafu GG' je bez cyklů

Základem silných komponent jsou cykly !

Kondenzace O.G. - silná komponenta se stane uzlem + hrany

Stupně a sousedi uzlů v orientovaném grafu G:• výstupní stupeň +(u) – kolik hran vystupuje z uzlu u

(je-li +(u)=0 u je list grafu G)• vstupní stupeň -(u) – kolik hran vstupuje do uzlu u

(je-li -(u)=0 u je kořen grafu G)• (u) - množina následníků uzlu u• 1(u) - množina předchůdců uzlu u

Lze něco zjistit o stupních ??

u)( = |H|

Vysvětlení: Každá hrana přispívá +1 výstupnímu stupni svého počátečního uzlu a +1 vstupnímu stupni svého koncového uzlu.

TI 3.11

Kontrolní otázky

1. Bude graf vzniklý zrušením orientace libovolného obyčejného orientovaného grafu obyčejným neorientovaným grafem ?

2. Je možné, aby byl silně souvislý nějaký orientovaný graf, jehož všechny uzly mají vstupní stupeň rovný nule ?

3. Orientovaný graf G vznikl jako sjednocení několika cyklů. Je graf G silně souvislý ?

4. Kolik silných komponent má orientovaný graf G = H,U,, který neobsahuje žádný cykl?

5. Jaký je minimální počet hran silně souvislého orientovaného grafu s n (2) uzly ?

6. Pokuste se formulovat nutnou a postačující podmínku pro to, aby orientovaný graf G obsahoval nekonečně mnoho spojení z uzlu u do uzlu v.

7. Jaký je minimální počet hran orientovaného grafu, který má n (3) uzlů a k (2 k n-1) silných komponent ?

8. Souvislý orientovaný graf G obsahuje aspoň dva uzly a má konečně mnoho různých spojení. Může být tento graf silně souvislý ?

TI 3.12

Orientované grafy a binární relace

Orientované grafy

V této části se seznámíme s pojmy:

• acyklický graf, testování acykličnosti, topologické uspořádání uzlů/hran orientovaného grafu

• graf binární relace na množině, graf složení relací, složení grafů, tranzitivní uzávěr grafuSkripta odstavec 2.2, str. 33 - 36

Co víme: silně souvislý graf má každou hranu v nějakém cykluJak vypadá opačný extrém ?Acyklický graf = orientovaný graf bez cyklů

Jak nejlépe testovat, zda je graf acyklický ???? Hledáním cyklů ???

Zjištění: Pokud pro uzly orientovaného grafu G platí uU: (u)1 nebo uU: (u)1 ,

potom graf G obsahuje alespoň jeden cyklus.

nesplňuje podmínku(u) 1

nesplňuje podmínku+(u) 1

cyklus!

Naše zjištění představuje podmínku postačující, nikoliv nutnou! Pro testování acykličnosti se nehodí.

Nové zjištění: Orientovaný graf G je acyklický G - {u} je acyklický pro libovolný kořen nebo list u.

Teď už můžeme formulovatALGORITMUS TESTOVÁNÍ ACYKLIČNOSTI

nemá ani kořen ani list !

K čemu je dobrý acyklický graf ?

Tyto akce NELZE reálně naplánovat. Proč? Odpovídající graf není acyklický

Plánujeme pořadí provádění nějakých akcí, např.:a < b, a < c, b < d, c < d, d < e, d < f, e < g, e < c, f < h, g < h

Topologické uspořádání uzlů (obyčejného) orientovaného grafu je posloupnost u1, u2, ..., un taková, že každá hrana (ui, uj) má i<j.

Topologické uspořádání hran (obyčejného) orientovaného grafu je posloupnost h1, h2, ..., hm taková, že každá dvojice navazujících hran hi, hj má i<j (co jsou to "navazující" hrany ?)

c e g h

Jak bychom našli topologické uspořádání uzlů ?

Budeme postupně odebírat kořeny grafu (-(u)=0) jako při testu acykličnosti. Jak to efektivně zařídit ?• pro každý uzel spočítáme

- -(u) ... vstupní stupeň (je-li =0, je to kořen) - (u) ... množinu následníků

• při každém vypuštění kořene upravíme -(u) pro jeho následníky, při poklesu na 0 zařadíme mezi kořeny.Pořadí odebrání uzlů je jejich topologickým uspořádáním.

! Později uvedeme ještě jednodušší algoritmus !

Vztah orientované grafy :: binární relace

Binární relace na množině X : R X XProstý OG s množinou uzlů U : H U U

Složení grafů GR GS = GRS

(RE), (SY), (TR), (ANS), (AS), (IR) - jak se projeví v grafu ??Tranzitivní uzávěr grafu G

(orientovaný) graf binární relace R ... GR :h = (u, v) vyjadřuje platnost u R v

TI 3.18

Kontrolní otázky

1. Navrhněte algoritmus topologického očíslování hran acyklického orientovaného grafu.

2. Zdůvodněte, proč pro testování acykličnosti (resp. hledání topologického uspořádání uzlů) orientovaného grafu stačí vypouštět jenom kořeny (nebo jenom listy).

3. Je topologické uspořádání uzlů (hran) orientovaného grafu určeno jednoznačně ?

4. Kolika různými způsoby lze orientovat úplný neorientovaný graf o n uzlech Kn tak, aby byl výsledný graf acyklický ?

5. Popište strukturu obyčejného orientovaného grafu s n uzly, který má pro danou hodnotu k (1 k n-1) přesně k! . (n-k)! různých topologických uspořádání uzlů.

6. Popište strukturu grafu binární relace, která je reflexivní (resp. symetrická, antisymetrická, asymetrická, tranzitivní, ireflexivní).

Orientované grafy

TI 3.19

REPREZENTACE GRAFŮ

maticovéspojové

další ...

Reprezentace grafů, odst. 4.1

V této části se seznámíme s pojmy:• matice incidence NG/OG, matice sousednosti NG/OG• (základní) spojová reprezentace NG/OGSkripta odstavec 4.1, str. 64 - 73

TI 3.20

Matice incidence NG

A = [ aik ] obdélníková matice typu |U| x |H| nad tělesem mod 2 (pozor na základní operace!)

1 .... hrana hk inciduje s uzlem uiaik =

0 .... jinak

b c1 2 3 4 5 6 7

? Co nám říká matice incidence o grafu ? ? Smyčky, rovnoběžné hrany ?

TI 3.21

Poznáme podle matic incidence, zda jsou dva grafy izomorfní?Např.: G1 G2 ?? právě když ?? A1 A2

Zjištění:• součet (mod 2) ve sloupci je 0 (vždy dvě jedničky!)

řádky jsou lineárně závislé, takže hodnost matice A ...• h(A) |U| - 1 (rovnost platí pro souvislé grafy) • h(A) = |U| - p obecný vztah pro graf s p komponentami

TI 3.22

Matice sousednosti NG

V = [ vij ] čtvercová matice typu |U| x |U| nad okruhem celých čísel: vij = počet hran mezi uzly ui a uj

b c a b c d e

? Co nám říká matice sousednosti o grafu ? ? Smyčky, rovnoběžné hrany ?

TI 3.23

Poznáme podle matic incidence, zda jsou dva grafy izomorfní?Např.: G1 G2 ?? právě když ?? A1 A2

Zjištění:

• V = VT

• Vr = [vik(r) ] ... počet sledů délky r mezi ui a uk

• A . AT = V + D, D = [ dii ], kde dii = (ui)

TI 3.24

Matice incidence OG

A = [ aik ] obdélníková matice typu |U| x |H| nad okruhem celých čísel:

1 ... hrana hk vychází z uzlu uiaik = -1 ... hrana hk končí v uzlu ui

0 ... jinak

b c1 2 3 4 5 6 7

Vlastnosti podobné jako pro NG

TI 3.25

Matice sousednosti OG

V = [ vij ] čtvercová matice typu |U| x |U| nad okruhem celých čísel: vij = počet hran z uzlu ui do uzlu uj

b c a b c d e

? Poznáme izomorfní orientované grafy ? ? V = VT ?

a b c d e

TI 3.26

Zjištění:

• Vr = [vik(r) ] ... počet spojení délky r z ui do uk

• V* = Vi , i=0, ... d, kde d = min(|H|, |U|-1)?? Co asi říká o grafu tato matice V* ??

• A . AT = D - V - VT , D = [ dii ], kde dii = +(ui)+

TI 3.27

Spojová reprezentace grafu

NG - seznamy sousedů OG - seznamy následníků (příp. ještě seznamy předchůdců)

Adj[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|

ORIENTOVANÉ GRAFY

Documents