Dosažitelnost v orientovaném grafu
Úloha číslo: 3363
Uvažme orientovaný graf \(G\) a relaci \(R\) na jeho vrcholech definovanou tak, že \(xRy\) právě tehdy, když z \(x\) vede orientovaná cesta do \(y\).
Varianta
Dokažte, že \(R\) je kvaziuspořádání (relace, která je reflexivní a transitivní, ale ne nutně antisymetrická).
Varianta
Definujme symetrické jádro relace jako \(R_s=R\cap R^{-1}\). Dokažte, že \(R_s\) je ekvivalence.
Varianta
Jaký význam mají třídy ekvivalence \(R_s\)?
Varianta
Definujme relaci \(R_f\) faktorizací \(R\) podle \(R_s\). Jinými slovy \(R_f\) bude relace na ekvivalenčních třídách relace \(R_s\) definovaná tak, že \(A R_f B\) právě tehdy, když pro \(a\in A\) a \(b\in B\) platí \(a R b\). Dokažte, že tato definice je korektní, tedy že nezáleží na výběru prvků \(a\) a \(b\).
Varianta
Ukažte, že relace \(R_f\) je (částečné) uspořádání.
Varianta
Jak vypadají grafy, pro něž je \(R_s\) triviální ekvivalence? (Každý vrchol je ekvivalentní pouze se sebou samým.)
Varianta
Jak vypadají grafy, pro něž je uspořádání \(R_f\) lineární?
