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.
Řešení:
|