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í:
|
|
A
|
B
|
C
|
D
|
E
|
|
A
|
1
|
0
|
0
|
0
|
0
|
|
B
|
1
|
1
|
0
|
0
|
0
|
|
C
|
1
|
0
|
1
|
0
|
0
|
|
D
|
1
|
0
|
0
|
1
|
0
|
|
E
|
1
|
1
|
0
|
1
|
1
|
|
