Exercici 3 · Matemática Discreta UAB 2025

a) i b) Representeu mitjançant un dibuix el graf dirigit G(A, R) i el seu complementari.

Solución: a. Graf dirigit $G(A, R)$: Té com a conjunt de vèrtexs $V = \{1, 2, 3, 4, 5\}$. Hi ha un arc dirigit de $a$ a $b$ si i només si $a < b$: - Des de l'1 surten arcs cap a 2, 3, 4 i 5. - Des del 2 surten arcs cap a 3, 4 i 5. - Des del 3 surten arcs cap a 4 i 5. - Des del 4 surt un arc cap a 5. - El vèrtex 5 té grau de sortida 0. b. Graf complementari $\bar{G}$: Conté tots els parells ordenats que no formen part de $R$, és a dir, tots els arcs dirigits $(a, b)$ tals que $a > b$ (arcs en sentit contrari a $G$), així com els bucles $(a, a)$ si es consideren sobre el producte cartesià complet.

c. Justifiqueu de manera raonada quina relació binària genera el graf complementari $\bar{G}$.

Solución: $\bar{R} = \{(a, b) \in A \times A \mid a \ge b\}$ / $\bar{R} = (A \times A) \setminus R$ (o $a > b$ en grafs simples sense bucles)