![Logo Matematická biologie](images/logo-matbiol.png)
Matice dostupnosti
Vrchol orientovaného grafu
dostupný z vrcholu
právě když v grafu existuje orientovaná cesta z
do
Jsou-li vrcholy grafu
uspořádány do posloupnosti
pak můžeme vytvořit matici
dostupnosti uzlů, která je následujícím předpisem pro její prvky
jestliže uzel
je dostupný z uzlu
v ostatních případech.
Algoritmus pro získání matice dostupnosti:
- inicializace: Označkujeme vrchol
ostatní značku nemají.
- test ukončení: Je-li množina neoznačkovaných vrcholů rázdná, algoritmus končí.
- volba hrany: Zvolíme libovolně hranu
jejíž očáteční vrchol je označkován a koncový vrchol v označkován není.
- značkování: označkujeme vrchol
a pokračujeme bodem 2.
Příklad: Pro následující orientovaný graf sestrojte matici dostupnosti.
![](/res/image/teoreticke_zaklady_informatiky/obr-tzi-11.png)
Řešení:
|