Graf skierowany

[Instru]

Niech będzie dany pewien graf skierowany \(\displaystyle{ G = \left\langle V, A \right\rangle}\), gdzie \(\displaystyle{ A \subseteq V^{2}}\)
a) Jaką interpretację można przypisać złożeniu relacji \(\displaystyle{ A}\)?
b) Co oznaczają elementy relacji \(\displaystyle{ A^{2}, ..., A^{n}}\)?
c) Co oznacza \(\displaystyle{ A^{*}}\)?
d) W jaki sposób można zbadać, czy graf posiada cykl?

[jutrvy]

Jeśli chodzi o (b), to elementem relacji \(\displaystyle{ A^k}\) będzie para wierzchołków, które są \(\displaystyle{ k}\)-incydentne, tj istnieje droga (czy tam ścierzka, nie wiem za dużo o terminologii) długości \(\displaystyle{ k}\), która łączy te dwa wierzchołki.

Wydaje mi się też, że domknięcie relacji reprezentowanej przez taki graf skierowany na fajną "grafową" interpretacje. To są po prostu wszystkie pary, wierzchołków, między którymi istnieje ścierzka skończonej długości.

A, i graf ma cykl, jeśli istnieje taki \(\displaystyle{ v\in V}\) oraz takie \(\displaystyle{ k\in\omega}\), że \(\displaystyle{ (v,v)\in A^k}\).