Graphes et matrice d'adjacence

a) Un graphe est dit k-régulier lorsque tous ses sommets ont le même degré k. Combien d'arêtes possède un graphe 3-régulier à 8 sommets ?
b) Existe-t-il un graphe 3-régulier à 7 sommets ? Justifier.

On considère un graphe à 4 sommets A, B, C, D dont les seules arêtes sont $A-B$ et $C-D$.
a) Écrire la matrice d'adjacence M.
b) Le graphe est-il connexe ? Justifier en s'appuyant sur les chaînes.

On considère le graphe complet à 4 sommets 1, 2, 3, 4 (chaque sommet est relié à tous les autres), de matrice d'adjacence M dont tous les coefficients hors diagonale valent 1 et la diagonale est nulle.
a) Combien y a-t-il de chaînes de longueur 2 reliant deux sommets distincts, par exemple 1 et 2 ?
b) Combien y a-t-il de chaînes de longueur 2 reliant un sommet à lui-même, par exemple 1 à 1 ?

On considère le graphe non orienté à 4 sommets A, B, C, D dont les arêtes sont $A-B$, $B-C$, $C-D$ et $B-D$.
a) Écrire la matrice d'adjacence M (ordre A, B, C, D).
b) Calculer $M^{2}$.
c) Combien y a-t-il de chaînes de longueur 2 partant de B et revenant à B ? Combien de chaînes de longueur 2 relient A à D ?

On considère le graphe « étoile » à 5 sommets : le sommet A est relié à B, C, D et E, et il n'y a aucune autre arête.
a) Écrire la matrice d'adjacence M (ordre A, B, C, D, E).
b) Calculer $M^{2}$.
c) Combien y a-t-il de chaînes de longueur 2 entre B et C ? entre A et A ? entre A et B ? Interpréter le dernier résultat.

On considère le graphe orienté à 3 sommets 1, 2, 3 dont les arcs sont $1\to 2$, $1\to 3$, $2\to 3$ et $3\to 1$.
a) Écrire la matrice d'adjacence M.
b) Calculer $M^{2}$.
c) Combien y a-t-il de chemins de longueur 2 allant de 1 à 1 ? de 1 à 3 ? Les lister.
d) Pourquoi $(M^{2})_{12} = 0$ ?

On considère le graphe non orienté « en ligne » à 5 sommets 1, 2, 3, 4, 5 dont les arêtes sont $1-2$, $2-3$, $3-4$ et $4-5$.
a) Écrire la matrice d'adjacence M.
b) Calculer $M^{2}$.
c) Combien y a-t-il de chaînes de longueur 2 de 1 à 3 ? de 1 à 5 ? Justifier le second résultat sans calcul.

Un réseau d'amitiés relie 5 personnes A, B, C, D, E. Les amitiés (réciproques) sont : $A-B$, $A-C$, $B-C$, $B-D$, $C-D$ et $D-E$.
a) Écrire la matrice d'adjacence M et donner le nombre d'amis de chacun.
b) Calculer $M^{2}$.
c) Combien A et D ont-ils d'amis communs ? Et A et E ?

On considère le graphe non orienté à 4 sommets A, B, C, D dont les arêtes sont $A-B$, $B-C$ et $C-D$.
a) Écrire M puis calculer $M^{2}$.
b) Calculer $M^{3} = M^{2} \times M$.
c) Combien y a-t-il de chaînes de longueur 3 de A à D ? de A à B ? Les lister.

Un réseau informatique relie 5 machines 1, 2, 3, 4, 5 par les câbles $1-2$, $1-3$, $2-3$ et $4-5$.
a) Écrire la matrice d'adjacence M.
b) Calculer $M^{2}$ et $M^{3}$.
c) La machine 1 peut-elle communiquer avec la machine 4 ? Que peut-on dire du réseau ?