Prehlad´
avanie grafu
Kostra grafu
Topologick´
e usporiadanie
Informatick´y kr´uˇzok - Grafy II
Rastislav Krivoˇs-Belluˇs
´
Ustav
informatiky
Pr´ırodovedeck´
a fakulta
ˇ arika v Koˇsiciach
Univerzita Pavla Jozef Saf´
23.10.2012 Koˇsice
Rastislav Krivoˇs-Belluˇs
Informatick´
y kr´
uˇzok - Grafy II
Prehlad´
avanie grafu
Kostra grafu
Topologick´
e usporiadanie
Klebetn´a Veronika
Klebetn´a Veronika sa pr´ave dozvedela, ˇze ˇskared´y Mirko chod´ı s peknou Vierkou. Veronika nebude mat’ pokoja, k´ym t´
uto inform´aciu nebude poznat’ cel´a trieda. Klebetn´a Veronika je vˇsak navyˇse straˇsne
leniv´a, a teda by nerada str´avila ˇs´ıren´ım klebiet viac ˇcasu, ako je
nevyhnutn´e. Veronika o kaˇzdom spoluˇziakovi vie, s ktor´ymi d’alˇs´ımi
spoluˇziakmi sa kamar´ati, a tieˇz vie, ˇze ak niektor´emu spoluˇziakovi
povie klebetu, dozvedia sa ju r´ychlo aj vˇsetci jeho kamar´ati. Vaˇsou
u
´lohou je zistit’, najmenej kol’k´ym spoluˇziakom mus´ı Veronika povedat’ klebetu, aby sa ju dozvedela cel´a trieda.
Rastislav Krivoˇs-Belluˇs
Informatick´
y kr´
uˇzok - Grafy II
Prehlad´
avanie grafu
Kostra grafu
Topologick´
e usporiadanie
Rastislav Krivoˇs-Belluˇs
Informatick´
y kr´
uˇzok - Grafy II
Prehlad´
avanie grafu
Kostra grafu
Topologick´
e usporiadanie
Komponenty s´
uvislosti
Rastislav Krivoˇs-Belluˇs
Informatick´
y kr´
uˇzok - Grafy II
Prehlad´
avanie grafu
Kostra grafu
Topologick´
e usporiadanie
Motiv´
acia
Te´
oria grafov
Algoritmy
Motiv´acia
Uvaˇzujme dopravn´
u (cestn´
u) siet’, ktor´
u chceme vylepˇsit’ vd’aka peniazom z eurofondov.
Ktor´e cesty m´ame prerobit’ na dial’nice, aby existovalo (nie nutne
priame) spojenie medzi kaˇzd´ymi 2 mestami v´yhradne po dial’niciach
a pritom aby sme minuli, ˇco najmenej peˇ
naz´ı?
Pre kaˇzd´y u
´sek sp´ajaj´
uci 2 mest´a uˇz m´ame projekt, teda n´aklady na
jeho prestavbu na dial’nicu.
Rastislav Krivoˇs-Belluˇs
Informatick´
y kr´
uˇzok - Grafy II
Prehlad´
avanie grafu
Kostra grafu
Topologick´
e usporiadanie
Motiv´
acia
Te´
oria grafov
Algoritmy
Kostra grafu (spanning tree)
Kostra s´
uvisl´eho grafu G je s´
uvisl´y acyclick´y podgraf grafu G , ktor´y
obsahuje vˇsetky vrcholy grafu G .
Minim´alna kostra grafu (Minimal Spanning Tree)
Minim´alna kostra grafu hranovo ohodnoten´eho s´
uvisl´eho grafu G je
to kostra grafu G s minim´alnym ohodnoten´ım (s´
uˇcet hodnˆot hr´an v
kostre).
Rastislav Krivoˇs-Belluˇs
Informatick´
y kr´
uˇzok - Grafy II
Prehlad´
avanie grafu
Kostra grafu
Topologick´
e usporiadanie
Motiv´
acia
Te´
oria grafov
Algoritmy
Zdroj:
http://ics.upjs.sk/paz1b/files/prednasky/prednaska11.pdf
Rastislav Krivoˇs-Belluˇs
Informatick´
y kr´
uˇzok - Grafy II
Prehlad´
avanie grafu
Kostra grafu
Topologick´
e usporiadanie
Motiv´
acia
Te´
oria grafov
Algoritmy
Primov algoritmus
Tvorbu kostry zaˇcneme jedn´ym vrcholom, dostaneme strom
T1 .
V kaˇzdom kroku zabezpeˇc´ıme ”zv¨aˇcˇsovanie”stromu o jeden
vrchol/jednu hranu.
Takto skonˇstruujeme postupnost’ expanduj´
ucich stromov
T1 , T2 , . . .
V kaˇzdom kroku skonˇstruujeme Ti+1 z Ti nasledovne: prid´ame
hranu s minim´alnym ohodnoten´ım vych´adzaj´
ucu z vrcholu
v strome (Ti ) a ved´
ucu do vrcholu, ktor´y eˇste nie je v strome
v´yber z ”okrajov´ych” hr´an (greedy krok!)
Rastislav Krivoˇs-Belluˇs
Informatick´
y kr´
uˇzok - Grafy II
Prehlad´
avanie grafu
Kostra grafu
Topologick´
e usporiadanie
Motiv´
acia
Te´
oria grafov
Algoritmy
Kruskalov algoritmus
Zaˇcneme s pr´azdnym lesom stromov.
V kaˇzdom kroku “porastie” MST o jednu hranu.
Medzikroky maj´
u obvykle les stromov (nes´
uvisl´y graf).
V kaˇzdom kroku prid´ame hranu s minim´alnym ohodnoten´ım
medzi uˇz pouˇzit´e hrany tak, aby nevznikol cyklus.
Hrany s´
u na zaˇciatku utrieden´e podl’a rast´
uceho ohodnotenia.
Rastislav Krivoˇs-Belluˇs
Informatick´
y kr´
uˇzok - Grafy II
Prehlad´
avanie grafu
Kostra grafu
Topologick´
e usporiadanie
Orientovan´y graf (digraf)
hrany s´
u orientovan´e, reprezentovan´e ako usporiadan´e dvojice
(jednosmern´e cesty)
Rastislav Krivoˇs-Belluˇs
Informatick´
y kr´
uˇzok - Grafy II
Prehlad´
avanie grafu
Kostra grafu
Topologick´
e usporiadanie
Topologick´e usporiadanie (topological ordening)
Topologick´e usporiadanie grafu G je line´arne usporiadanie vˇsetk´ych
jeho vrcholov tak, ˇze ak G obsahuje hranu (u, v ), potom vrchol u
sa nach´adza v tomto usporiadan´ı pred vrcholom v .
Ak dan´y graf G nie je acyklick´y, tak zjavne tak´eto usporiadanie
existuje.
Rastislav Krivoˇs-Belluˇs
Informatick´
y kr´
uˇzok - Grafy II
Prehlad´
avanie grafu
Kostra grafu
Topologick´
e usporiadanie
Topologick´e usporiadanie:
Rastislav Krivoˇs-Belluˇs
Informatick´
y kr´
uˇzok - Grafy II
Prehlad´
avanie grafu
Kostra grafu
Topologick´
e usporiadanie
Topologick´e usporiadanie:
J K L M A G H I F E D B C
Rastislav Krivoˇs-Belluˇs
Informatick´
y kr´
uˇzok - Grafy II
Prehlad´
avanie grafu
Kostra grafu
Topologick´
e usporiadanie
Reverzn´e topologick´e usporiadanie
Opaˇcn´a interpret´acia hr´an: hrana (x, y ) znamen´a, ˇze vrchol x z´avis´ı
na vrchole y (napr. defin´ıcia v´yrazu pred jeho pouˇzit´ım).
Toto koreˇsponduje s umiestnen´ım vrcholov do radu tak, aby hrany
medzi nimi ˇsli len sprava dol’ava.
Rastislav Krivoˇs-Belluˇs
Informatick´
y kr´
uˇzok - Grafy II
Prehlad´
avanie grafu
Kostra grafu
Topologick´
e usporiadanie
Reverzn´e topologick´e usporiadanie:
D E F C B I H G A K M L J
Rastislav Krivoˇs-Belluˇs
Informatick´
y kr´
uˇzok - Grafy II
Prehlad´
avanie grafu
Kostra grafu
Topologick´
e usporiadanie
Reverzn´e topologick´e usporiadanie
D´a sa z´ıskat’ prehl’ad´avan´ım do hl’bky tak, ˇze vˇzdy ked’
prehl’ad´avanie v rekurzii ¨
odch´adza z vrcholu,”vyp´ıˇseme
ˇc´ıslo/oznaˇcenie vrcholu.
Rastislav Krivoˇs-Belluˇs
Informatick´
y kr´
uˇzok - Grafy II
Download

Informatický krúzok