Le graphe complémentaire

Théorie des graphes · Matrice d'adjacence · niveau 2

Énoncé

Soit $G$ un graphe non orienté sans boucle à $n$ sommets, de matrice d'adjacence $A$ . On note $G$ le graphe où deux sommets distincts sont reliés exactement lorsqu'ils ne le sont pas dans $G$ . Exprimer la matrice d'adjacence de $G$ à l'aide de $A$ , puis les degrés de $G$ .

Corrigé

La matrice. Notons $J$ la matrice de $M_{n} (R)$ dont tous les coefficients valent $1$ . Pour $i \neq = j$ , le coefficient cherché vaut $1 - a_{ij}$ ; pour $i = j$ , il vaut $0$ , car $G$ est lui aussi sans boucle. Or $J - I_{n}$ a des $1$ hors de la diagonale et des $0$ sur la diagonale, et $a_{ii} = 0$ . Donc $A = J - I_{n} - A .$ Au passage, $J - I_{n}$ est la matrice du graphe complet à $n$ sommets, où tout est relié : le complémentaire s'obtient en lui retranchant $G$ .

Les degrés. Pour tout sommet $i$ : $de g_{G} (i) = j \neq = i \sum (1 - a_{ij}) = (n - 1) - de g_{G} (i) .$

Vérification par la formule d'Euler. La somme des degrés de $G$ vaut $n (n - 1) - 2 m$ , où $m$ est le nombre d'arêtes de $G$ : $G$ a donc $\frac{n ( n - 1 )}{2} - m$ arêtes, c'est-à-dire exactement les arêtes du graphe complet que $G$ n'utilise pas.

Le point à retenir. $A$ est symétrique comme $J$ , $I_{n}$ et $A$ : le complémentaire d'un graphe non orienté l'est encore.

Énoncé

Corrigé

Exercices semblables