# OLA, TD3 : Composantes connexes et relations d'équivalence

## Exercice 1 : _Vrai ou faux ?_

1) Vrai : il y a un chemin de $x$ à $x$ (réflexivité), si $path(x, y)$ et $path(y, z)$ sont vrais alors on a $path(x,z)$ en concatenant les chemins (transitivité) et si il ya un chemin entre $x$ et $y$ il y en a un entre $y$ et $x$ en prenant les flèches dans l'autre sens (symmétrie).
2) Faux : cette relation n'est pas symmétrique.
3) a) Faux : le sommet $E$ est de degré 6.
b) Faux : $K_5$ est un sous-graphe de $G$ et on sait que $K_5$ n'est pas 4-colorable.
c) Vrai : tous ses sommets sont de degré pair, par le théorème d'Euler-Hierholzer il existe un cycle eulérien pour $G$.

## Exercice 2 : _Relations d'équivalence_

1) $cl(a) = \{x \in A | f(x) = f(a)\} = f^{-1}(\{a\})$
2) La relation $\subseteq$ n'est pas une relation d'équivalence. En effet la relation n'est pas symétrique, par exemple $\emptyset \subset \mathbb{N}$ mais $\mathbb{N} \not\subset \emptyset$.

## Exercice 3 : _Composantes connexes_

1) La composante connexe de de $a$ contient $a$ donc est non vide.
Tout sommet $a$ apartient à la composante connexe de $a$.
Soit $C_1, C_2$ des composantes connexes, soit $C_1 \cap C_2 = \emptyset$ et il n'y a rien à prouver soit $\exists c \in C_1 \cap C_2$ et dans ce cas $\forall x \in C_1, y \in C_2$ il existe un chemin de de $x$ à $c$ et et un chemin de $c$ à $y$ donc un chemin de $x$ à $y$ (et inversement). Donc $C_1 = C_2$
2) Pour un graphe à $n$ sommets on peut avoir entre 1 composante connexe (ex: clique) et $n$ (ex: un graphe sans arêtes).
3) Il y a deux possibilités. La première est $CC(a) = CC(b)$ ce qui veut dire, par définition, il existe une chemin de $a$ vers $b$ : $\rho = a \rightarrow\rightarrow b$, on peut y ajouter la nouvelle arête : $\rho' = a \rightarrow\rightarrow b \rightarrow a$ pour obtenir un cycle. La deuxième possibilité est $CC_{G}(a) \neq CC_{G}(b)$, dans ce cas, la composante connexe de $a$ dans $G'$ contient $b$ (puis qu'on a un chemin $a \rightarrow b$) donc dans $G'$, $CC_{G'}(a) = CC_{G'}(b) = CC(a)_G \cup CC(b)_G$ : il y a une composante connexe en moins.
5) Considérons un graphe acyclique $G = (V, E)$. On part du graphe sans arêtes $G_0 = (V, \emptyset)$ et on ajoute les arêtes une à une. Comme lors du processus on ne crée pas de cycle on est toujours dans la sitution 2 de la question précédente : le nombre de composantes connexes diminue de 1 à chaque étape. Au départ il y a $n$ composantes connexes et on ne peut plus ajouter d'arêtes dans le situation 2 quand il n'y a plus qu'une composante connexe. Donc au plus on peut ajouter $n-1$ arêtes.

## Exercice 4 : _Graphes des composantes_

1)
2)
3)
4)
5)

## Exercice 5 : _Relations qui commutent_

1) $\forall x, y \in A, xR_1R_2y \Leftrightarrow xR_2R_1y$.
2) 
On veut montrer que si $xR_1R_2y$ et $yR_1R_2z$ alors $xR_1R_2z$. Etape A : par définition, il existe $x', z'$ vérifiant les relations indiquées en noir sur le schéma. Etape B : on a $x'R_2y$ et $yR_1z'$ donc $x'R_2r_1z'$ et par commutatitivité on obtient la flèche rouge sur le schéma. Etape C : en applicant la définition à $x'R_1r_2z'$ on obtient $y'$ vérifiant les relations indiquées en noir sur le schéma. Etape D : par transitivité de $R_1$ et $R_2$, on obtient les flèches vertes : $xR_1y'$ et $y'R_2z$. Par défintion, on a donc bien $xR_1R_2z$.
4) 
5) Cf diagramme ci dessus.
6) Si on prend $A = \{0,1,2,3,4\}$, $R_1 = \{(0,1),(2,3)\}$, $R_2 = \{(1,2), (3,4)\}$ alors on a $(0,2)\in R_1R_2$, $(2,4) \in R_1R_2$ mais $(0,4) \notin R_1R_2$.