Seminář 7 (1.11.) Orientované grafy

Přehledy a ukázky
Kuchařkovitý přehled o základních postupech s orientovanými grafy je zde.
Jednoduché ilustrace jsou zde.
Topologické řazení si lze osvěžit zde, d a f představují otvírací/zavírací časy, obsah zásobníku definuje topologické uspořádání.
Hledání silných komponent máme pěkně provedeno v přednášce o pokročilých algoritmech zde.


Příklady k rozmyšlení

71. Začněme topologickým řazením Ordering Tasks, (záložní odkaz)

72. Spočtěme počet cest v grafu Walking Around Wisely, (záložní odkaz)

73. Najděme nejdelší cestu Hippity Hopscotch , (záložní odkaz)

74. Najděme nejdelší váženou cestu Liftless EME, (záložní odkaz)

75. Určeme počet silných komponent Trust groups, (záložní odkaz)

76. Určeme jen některé silné komponenty Lighting Away, (záložní odkaz)


Něco navíc pro odhodlanější účastníky

77. Může být lexikografické uspořádání zároveň topologickým uspořádáním? Stacking Boxes, (záložní odkaz)

78. Stačí trochu přizpůsobit Tarjanův algoritmus? Cactus, (záložní odkaz)

courses/a4b36acm2/2012_zs/seminar_7_111.txt · Last modified: 2018/02/21 22:30 (external edit)