Quiz : Graphes, Arbres, Cycles et Coloration

Réponse : B. Dans un graphe simple non orienté, chaque arête relie deux sommets distincts. Le nombre maximal d'arêtes est obtenu lorsque chaque paire de sommets est reliée par une arête. C'est donc le nombre de façons de choisir 2 sommets parmi $n$, soit $\binom{n}{2} = \frac{n(n-1)}{2}$. L'option C est le nombre d'arêtes d'un arbre à $n$ sommets.

Réponse : D. Un arbre est un graphe connexe qui ne contient aucun cycle (acyclique). Si un graphe est connexe et contient $n$ sommets et $n-1$ arêtes, c'est un arbre. L'option A décrit un pseudographe ou une structure différente. L'option B décrit une forêt (un ensemble d'arbres).

Réponse : A. Une propriété fondamentale des arbres est que pour $n$ sommets, il y a toujours $n-1$ arêtes. C'est une condition nécessaire et suffisante, avec la connexité ou l'acyclicité, pour qu'un graphe soit un arbre.

Réponse : C. Un cycle est un chemin simple dont les deux extrémités sont le même sommet. Il ne répète pas d'arêtes. Un sentier est plus général (peut répéter arêtes et sommets). Un chemin simple ne répète aucun sommet (sauf potentiellement les extrémités si c'est un cycle). Une chaîne ne répète pas d'arêtes.

Réponse : B. Un cycle dans un graphe orienté est une séquence d'arêtes orientées qui part d'un sommet et y revient. Il peut y avoir d'autres sommets intermédiaires qui sont visités une seule fois (dans un cycle simple) ou plusieurs fois (dans un cycle plus complexe). L'essentiel est de revenir au point de départ.

Réponse : A. Le degré d'un sommet dans un graphe non orienté est défini comme le nombre d'arêtes qui sont connectées à ce sommet. Dans le cas d'une boucle (une arête allant d'un sommet à lui-même), elle compte deux fois pour le degré du sommet. L'option B est généralement égale au degré dans un graphe simple sans boucles.

Réponse : C. Le nombre chromatique, noté $\chi(G)$, est le plus petit entier $k$ pour lequel il existe une coloration valide du graphe $G$ avec $k$ couleurs. Une coloration est valide si aucun deux sommets adjacents ne partagent la même couleur.

Réponse : D. L'algorithme de Dijkstra est utilisé pour trouver le chemin le plus court d'un sommet source vers tous les autres sommets dans un graphe pondéré dont les poids des arêtes sont non négatifs. Prim et Kruskal sont utilisés pour trouver des arbres couvrants minimaux. La coloration gloutonne est pour la coloration de graphes.

Réponse : A. La définition d'un graphe biparti est précisément qu'il peut être partitionné en deux ensembles de sommets tels que toutes les arêtes relient un sommet d'un ensemble à un sommet de l'autre. Une propriété importante est qu'un graphe est biparti si et seulement s'il ne contient aucun cycle d'une longueur impaire.

Réponse : C. Dans un graphe complet $K_n$, chaque sommet est adjacent à tous les autres $n-1$ sommets. Par conséquent, chaque sommet doit avoir une couleur différente. Il faut donc $n$ couleurs pour colorier $K_n$. Le nombre chromatique $\chi(K_n) = n$. Pour $n=1$, $\chi(K_1)=1$. Pour $n=2$, $\chi(K_2)=2$. Pour $n=3$, $\chi(K_3)=3$, etc.

Réponse : D. Un arbre binaire est bien un arbre au sens de la théorie des graphes : il est connexe et acyclique. Il possède des propriétés supplémentaires liées à la distinction entre fils gauches et fils droits, et au degré maximal des nœuds (au plus 3, si l'on considère la racine avec un lien vers un parent et deux enfants). Les options A, B, C ne sont pas toujours vraies pour un arbre binaire.

Réponse : B. Le problème de décision "le nombre chromatique d'un graphe $G$ est-il inférieur ou égal à $k$ ?" est NP-complet pour $k \ge 3$ dans la classe générale des graphes. Pour les graphes bipartis, le nombre chromatique est au plus 2 (ou 1 pour les graphes sans arêtes). Pour les arbres, il est au plus 2. Pour les graphes de degré borné, il existe des algorithmes polynomiaux.

Réponse : C. Une propriété fondamentale des graphes bipartis est qu'ils ne contiennent aucun cycle d'une longueur impaire. Réciproquement, si un graphe ne contient aucun cycle d'une longueur impaire, alors il est biparti. Donc, la présence d'un cycle impair garantit que le graphe n'est pas biparti.

Réponse : A. Un arbre est un graphe connexe et acyclique. Cette acyclicité garantit qu'il n'existe qu'un seul chemin simple entre deux sommets quelconques de l'arbre. Si deux chemins distincts existaient, leur combinaison (en prenant une partie de chaque chemin) créerait un cycle, ce qui contredirait la définition d'un arbre.

Réponse : D. Si $G$ est biparti avec partitions $V_1$ et $V_2$, alors $\bar{G}$ a des arêtes entre deux sommets de $V_1$ ou entre deux sommets de $V_2$. $\bar{G}$ est biparti si et seulement si $G$ est le graphe complet $K_n$ ou le graphe nul $N_n$. Si $G$ est biparti mais pas complet, alors $\bar{G}$ n'est pas biparti (il aura des cycles impairs). Par exemple, un chemin $P_3$ (3 sommets, 2 arêtes) est biparti. Son complémentaire a 3 sommets et 1 arête (celle qui manquait pour être $K_3$), donc il est aussi biparti. Mais si $G=C_5$ (cycle impair), il est biparti (car il est connexe et n'a pas de cycle impair, ce qui est faux, $C_5$ a un cycle impair et n'est pas biparti). L'énoncé dit que $G$ est biparti. Si $G$ est un cycle pair $C_6$, il est biparti. Son complémentaire $ \bar{C_6} $ contient un $K_3$ et donc n'est pas biparti. La réponse D est donc la plus prudente et la plus générale.

Correction de la réponse suite à une analyse plus poussée : Un graphe $G$ est biparti si et seulement s'il ne contient aucun cycle d'impair. Si $G$ est biparti, il peut être composé de deux partitions $V_1, V_2$. Dans $\bar{G}$, les arêtes qui n'existent pas dans $G$ existent. Si $G$ est biparti, cela ne garantit pas que $\bar{G}$ le soit. Par exemple, si $G$ est un chemin $P_3$, $G$ est biparti. $V_1=\{v_1, v_3\}, V_2=\{v_2\}$. $\bar{G}$ a une arête entre $v_1$ et $v_3$. $\bar{G}$ est donc biparti. Si $G$ est un graphe complet $K_n$, il n'est biparti que pour $n=1, 2$. Son complémentaire $N_n$ (graphe sans arête) est biparti. Si $G$ est un graphe tel que ses partitions $V_1, V_2$ ont des tailles $k_1, k_2$, alors $\bar{G}$ aura des arêtes dans $V_1$ et dans $V_2$, donc il ne sera biparti que dans des cas très spécifiques (comme $K_n$ ou $N_n$). La réponse D est la plus appropriée car il n'y a pas de règle générale simple. Par exemple, si $G$ est $P_3$, $\bar{G}$ est $P_3$ (biparti). Si $G$ est $C_4$ (biparti), $\bar{G}$ est $2K_2$ (biparti). Mais si $G$ est $C_6$, $\bar{G}$ contient $K_3$ et n'est pas biparti.

Réponse corrigée : D. L'appartenance de $\bar{G}$ à la classe des graphes bipartis n'est pas une conséquence directe de celle de $G$. Si $G$ est biparti, il ne contient pas de cycle impair. Cependant, $\bar{G}$ peut en contenir un. Par exemple, si $G$ est un cycle pair $C_6$ (qui est biparti), son complémentaire contient un $K_3$ et n'est donc pas biparti. Si $G$ est un chemin $P_3$ (biparti), son complémentaire est aussi $P_3$ (biparti). La relation n'est donc pas simple, et $\bar{G}$ peut être biparti ou non.