Polo-dosažitelnost v grafu
Úloha číslo: 4324
Pro orientovaný graf definujme relaci \(R\) na množině vrcholů tak, že \(uRv\) právě tehdy, když existuje cesta z \(u\) do \(v\) nebo z \(v\) do \(u\). Ověřte, zda je tato relace reflexivní, symetrická, tranzitivní.
Řešení
Relace je reflexivní, protože z vrcholu do téhož vrcholu vždy vede cesta nulové délky.
Symetrie relace plyne přímo z definice.
Relace není tranzitivní. Uvažme graf s vrcholy 1, 2, 3 a hranami \((1{,}2)\) a \((3{,}2)\). Mezi 1 a 2 existuje cesta, mezi 2 a 3 také, ale mezi 1 a 3 neexistuje ani jedním směrem.
