Matematické Fórum

kalkulacka · 12. 04. 2009 12:09

Ahoj,
potreboval bych poradit s matici sousednosti orientovaneo grafu.
1. Jakym algoritmem ziskam matici sousednosti ????
2. matice sousednosti = matice dosazitelnosti ????
3. jak se ziska s matice dosazitelnosti silne zavisle komponenty ???

prosim nejak polopate :) nebo sem se do toho nejak nemile zamotal :-D
diky.....

gladiator01

ad1)
graf 1 je oritentovany, 2 neorientovany

(zdroj: Teoretické základy informatiky, J. Vaníček a kol.)
Matici sousednosti $S_G$ definujeme předpisem
$S_G = (s_{i,j}), kde \nl s_{i,j} = mG^+(u_i, u_j)$
$(mG^+$ je nasobnost orientovane hrany)

prostě když např. bod a je spojen hranou s bodem b tak napíšeš 1, když ne tak 0, když jsou ty body spojeny více hranami (jako např. b a c, viz. obrázek) tak napíšeš, v tomto případě, 2.

gladiator01

ad b)
Jestli je matice dosazitelnosti to samé co matice dostupnosti tak ne.

(zdroj: skripta prof. Mišoviče)

Matematické Fórum

#1 12. 04. 2009 12:09

matice sousednosti orientovaneho grafu

#2 12. 04. 2009 17:17 — Editoval gladiator01 (12. 04. 2009 17:36)

Re: matice sousednosti orientovaneho grafu

#3 12. 04. 2009 17:28 — Editoval gladiator01 (12. 04. 2009 17:28)

Re: matice sousednosti orientovaneho grafu

Zápatí