Graphes et matrice d'adjacence

On considère le graphe non orienté à 5 sommets A, B, C, D, E dont les arêtes sont $A-B$, $B-C$, $C-D$, $D-E$ et $E-A$.
a) Quelle est la longueur de la chaîne $A-B-C-D$ ?
b) La suite de sommets $A-B-C-D-E-A$ est-elle un cycle ? Quelle est sa longueur ?

Peut-il exister un graphe dont les degrés des sommets sont 1, 2, 3, 4 et 5 ? Justifier de deux façons différentes.

Un graphe non orienté possède 6 sommets dont les degrés sont 1, 2, 2, 3, 3 et 5.
a) Combien d'arêtes possède ce graphe ?
b) Vérifier la propriété portant sur le nombre de sommets de degré impair.

Voici la matrice d'adjacence d'un graphe dont les sommets sont A, B, C, D (dans cet ordre) :
M =
( 0 1 1 0 )
( 1 0 1 1 )
( 1 1 0 0 )
( 0 1 0 0 )
a) Le graphe est-il orienté ?
b) Quel est le degré de B ?
c) Combien le graphe a-t-il d'arêtes ?

Écrire la matrice d'adjacence M du graphe non orienté à 4 sommets numérotés 1, 2, 3, 4 dont les arêtes sont $1-2$, $2-3$, $3-4$ et $4-1$.

Un graphe non orienté a pour sommets A, B, C, D et pour arêtes $A-B$, $A-C$, $B-C$ et $C-D$. Sa matrice d'adjacence M et son carré valent :
M =
( 0 1 1 0 )
( 1 0 1 0 )
( 1 1 0 1 )
( 0 0 1 0 )
$M^{2}$ =
( 2 1 1 1 )
( 1 2 1 1 )
( 1 1 3 0 )
( 1 1 0 1 )
Sans refaire de calcul, répondre.
a) Combien y a-t-il de chaînes de longueur 2 allant de A à D ?
b) Combien y a-t-il de chaînes de longueur 2 partant de C et revenant en C ?
c) Expliquer pourquoi $(M^{2})_{CD} = 0$.

On considère le graphe non orienté d'ordre 5 dont les sommets sont A, B, C, D, E et les arêtes $A-B$, $A-C$, $B-C$, $C-D$, $D-E$.
a) Donner l'ordre du graphe.
b) Donner le degré de chaque sommet.
c) Ce graphe est-il connexe ?

Un réseau routier relie 6 villes A, B, C, D, E, F. Les routes (sans sens de circulation) sont : $A-B$, $A-C$, $B-C$, $B-D$, $C-E$, $D-E$ et $E-F$.
a) Donner l'ordre du graphe et son nombre d'arêtes.
b) Donner le degré de chaque ville et vérifier le lemme des poignées de main.
c) Quelles villes sont les mieux desservies ? Le réseau est-il connexe ?

Soit le graphe non orienté « triangle » à 3 sommets 1, 2, 3 tous reliés deux à deux, de matrice d'adjacence
M =
( 0 1 1 )
( 1 0 1 )
( 1 1 0 )
a) Calculer $M^{2}$.
b) Combien y a-t-il de chaînes de longueur 2 reliant le sommet 1 à lui-même ? Et du sommet 1 au sommet 2 ?

On considère le graphe orienté à 4 sommets A, B, C, D dont les arcs sont $A\to B$, $A\to D$, $B\to C$, $C\to A$ et $D\to C$.
a) Écrire la matrice d'adjacence M (ordre A, B, C, D).
b) La matrice est-elle symétrique ? Qu'en déduit-on ?
c) Donner le degré sortant et le degré entrant du sommet C.