[A-L] (20 Giugno 2024) Esercizio 3

[FeddyLix17]

Sia $\Large G$ il grafo orientato in figura sull’insieme dei vertici $\Large V = \{0,\ 1,\ 2,\ 3,\ 4\}$.

Sia $\Large E$ la relazione di arco orientato tra vertici di $\Large G$, ossia

per $\Large i, j \in V$ vale $\Large (i, j) \in E$ se e solo se esiste un arco dal vertice $\Large i$ al vertice $\Large j$.

1. Calcolare la relazione $\Large E^{-1}$. Disegnare il grafo risultante.

2. Calcolare $\Large E \circ E$. Disegnare il grafo risultante.

3. Calcolare la chiusura transitiva di $\Large E$. Disegnare il grafo risultante.

[FeddyLix17]

La relazione E risultante dal grafo orientato sarà $\Large E = \{(0,2),\ (0,3),\ (1,0),\ (2,1),\ (3,4),\ (4,0)\}$

$$ \Large E^{-1} = \{(2,0),\ (3,0),\ (0,1),\ (1,2),\ (4,3),\ (0,4)\} $$

---

$$ \Large E \circ E = \{(i,k),\ i,k \in V\ |\ (i,x),(x,k) \in E,\ x \in V \} = \{(0,1), (0,4), (1,2), (1,3), (2,0), (3,0)\} $$

---

$$ \Large E^+ = E \cup (E \circ E) = \{(0,1),(0,2),(0,3),(0,4),(1,0),(1,2),(1,3),(2,0),(2,1),(3,0),(3,4),(4,0)\} $$