Exercice 5, § 2

a) Soit $n$ un entier naturel $\geqslant 1$ et soit G un graphe dont l’ensemble des sommets est l’ensemble $\mathbf{Z}/n\mathbf{Z}$ et tel que deux sommets $i$ et $j$ sont reliés par une flèche si et seulement si $i-j=\pm 1$ (mod$. n$). Expliciter l’ensemble des forêts maximales de G.

b) Soit G un graphe et soit S l’ensemble de ses sommets. On suppose que pour tout couple $(x, y)$ de sommets de G, l’ensemble des flèches de G d’origine $x$ et de terme $y$ est de cardinal 1 si $x=\not y$ et 0 sinon (« graphe complet »). Calculer le cardinal de l’ensemble des forêts maximales de G.

c) Soit G un graphe et soit S l’ensemble de ses sommets. Soit $(S_1,S_2)$ une partition de S ; on suppose que pour tout couple $(x, y)$ de sommets de G, l’ensemble des flèches de G d’origine $x$ et de terme $y$ est de cardinal 1 si $(x, y)\in S_1\times S_2$ et 0 sinon (« graphe bipartite complet »). Calculer le cardinal de l’ensemble des forêts maximales de G.