Matematické Fórum

jozef12345 · 20. 11. 2022 10:36

Dobrý den, prosim poraďte mi, tady: http://najada.fav.zcu.cz/~ryjacek/stude … matic1.pdf jsem našel v textu zmínku o "věte o acyklických grafech", ví někdo o jakou větu se jedná? Bez toho se nevím s tímhle příkladem pohnout.

petrkovar · 03. 12. 2022 14:13

Tipnul byh si, že se tím myslí klasická věta, která říká: Pokud máme acyklický digraf (orientovaný graf) s $n$ vrcholy, tak můžeme seřadit jeho vrcholy do posloupnosti $v_{1}, v_{2}, \dots, v_{n}$ tak, že pro každou orientovanou hranu $v_{i} v_{j}$ platí $i < j$ .

Matematické Fórum

#1 20. 11. 2022 10:36

věta o acyklickych grafech

#2 03. 12. 2022 14:13

Re: věta o acyklickych grafech

Zápatí