Graphe biparti et chaînes impaires

Exercice · niveau 2 · mathématiques appliquées (ECG 1re année), chapitre 3 — Théorie des graphes · Puissances et comptage des chemins

Énoncé

Un graphe est biparti si l'on peut colorier ses sommets en deux couleurs sans qu'aucune arête relie deux sommets de même couleur. Montrer qu'un graphe biparti n'a aucune chaîne de longueur impaire d'un sommet vers lui-même. Que vaut alors $(A^{2 k + 1})_{ii}$ ?

Corrigé

Colorions les sommets en noir et blanc comme le permet l'hypothèse. Chaque arête change la couleur : c'est exactement la définition.

Une chaîne de longueur $ℓ$ partant de $i$ franchit $ℓ$ arêtes, donc change $ℓ$ fois de couleur. Si elle revient en $i$ , elle doit retrouver la couleur de départ : le nombre de changements est donc pair. Ainsi $ℓ$ est pair, et aucune chaîne fermée de longueur impaire n'existe.

Par conséquent, pour tout sommet $i$ et tout $k \geq 0$ :

$(A^{2 k + 1})_{ii} = 0.$

Autrement dit, toutes les puissances impaires de $A$ ont une diagonale nulle.

La réciproque est vraie aussi (un graphe sans cycle de longueur impaire est biparti), ce qui donne un critère : biparti $⟺$ aucune diagonale non nulle en puissance impaire.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.