Ressources · Terminale · Maths expertes (option Tle)
Matrice d’adjacence et chemins
Matrice d’adjacence d’un graphe orienté ou non ; degrés et nombre d’arêtes lus sur la matrice ; nombre de chemins de longueur k donné par Mᵏ, avec sa démonstration ; chemins fermés, triangles et coefficients nuls ; distance, diamètre et connexité.
À propos de cette page
Les 36 questions du QCM en version texte
Pour réviser sans écran ou imprimer : chaque question avec ses propositions ; la bonne réponse et son explication se déplient.
Niveau facile ★ — 12 questions
Dans la matrice d’adjacence d’un graphe non orienté, le coefficient de la ligne i et de la colonne j est :
- A. le degré du sommet i
- B. le nombre d’arêtes entre i et j
- C. la distance entre i et j
- D. le nombre de chaînes de i à j
Réponse
B. le nombre d’arêtes entre i et j — C’est la définition : dans un graphe simple, ce coefficient vaut 1 si i et j sont reliés, 0 sinon. Le degré est la somme de toute la ligne.
La matrice d’adjacence d’un graphe non orienté est toujours :
- A. symétrique
- B. inversible
- C. diagonale
- D. à coefficients tous non nuls
Réponse
A. symétrique — L’arête qui relie i à j relie aussi j à i, donc le coefficient (i ; j) est égal au coefficient (j ; i).
Dans un graphe non orienté sans boucle, la somme des coefficients de la ligne i de M est égale :
- A. au nombre total d’arêtes du graphe
- B. au nombre de sommets du graphe
- C. à la plus grande distance depuis i
- D. au degré du sommet i
Réponse
D. au degré du sommet i — Chaque 1 de la ligne correspond à une arête issue de i : la somme de la ligne compte ces arêtes.
Le coefficient de la ligne i et de la colonne j de M³ donne :
- A. la distance du sommet i au sommet j
- B. le nombre d’arêtes reliant i à j
- C. le nombre de chemins de longueur 3 de i à j
- D. le nombre de sommets entre i et j
Réponse
C. le nombre de chemins de longueur 3 de i à j — C’est le théorème du chapitre : les coefficients de Mᵏ comptent les chemins de longueur k.
Dans un graphe orienté, la somme de tous les coefficients de M est égale :
- A. au nombre d’arcs du graphe
- B. au double du nombre d’arcs
- C. au nombre de sommets
- D. au diamètre du graphe
Réponse
A. au nombre d’arcs du graphe — Chaque arc i → j n’apparaît qu’une fois, en ligne i et colonne j ; pour un graphe non orienté, on diviserait par 2.
La distance entre deux sommets d’un graphe est :
- A. le nombre de sommets qui les séparent
- B. le nombre de chaînes qui les relient
- C. la longueur de la plus longue chaîne les reliant
- D. la plus petite longueur d’une chaîne les reliant
Réponse
D. la plus petite longueur d’une chaîne les reliant — On compte les arêtes, pas les sommets, et l’on prend la plus petite longueur possible.
Le diamètre d’un graphe connexe est :
- A. le nombre de sommets du graphe
- B. la plus grande distance entre deux sommets
- C. la plus petite distance entre deux sommets
- D. le plus grand degré d’un sommet
Réponse
B. la plus grande distance entre deux sommets — Le diamètre mesure l’éloignement maximal : c’est la plus grande des distances d(i ; j).
Dans un graphe orienté, la somme des coefficients de la colonne j de M est :
- A. le degré sortant de j
- B. le degré entrant de j
- C. le nombre total d’arcs
- D. le double du degré de j
Réponse
B. le degré entrant de j — La colonne j contient les arcs qui arrivent en j : sa somme est le degré entrant. La ligne j donnerait le degré sortant.
Dans un graphe sans boucle, la diagonale de la matrice d’adjacence :
- A. ne contient que des 1
- B. contient les degrés des sommets
- C. est nulle
- D. contient les distances à chaque sommet
Réponse
C. est nulle — Le coefficient (i ; i) compte les boucles en i : sans boucle, il vaut 0. Ce sont les coefficients diagonaux de M² qui donnent les degrés.
Dans un graphe non orienté simple, le coefficient diagonal (M²)ᵢᵢ est égal :
- A. au nombre de triangles contenant i
- B. au carré du degré de i
- C. au degré du sommet i
- D. à zéro
Réponse
C. au degré du sommet i — Un chemin fermé de longueur 2 est un aller-retour i–r–i vers un voisin r : il y en a autant que de voisins.
La matrice d’adjacence d’un graphe d’ordre 4 est :
- A. une matrice carrée de taille 4
- B. une matrice ligne à 4 coefficients
- C. une matrice à 4 lignes et 2 colonnes
- D. de taille égale au nombre d’arêtes
Réponse
A. une matrice carrée de taille 4 — Il y a une ligne et une colonne par sommet : la matrice est carrée, de taille l’ordre du graphe.
Combien de coefficients égaux à 1 contient la matrice d’adjacence du graphe complet K₄ ?
- A. 6
- B. 16
- C. 12
- D. 4
Réponse
C. 12 — Tous les coefficients hors de la diagonale valent 1 : 16 − 4 = 12, soit le double des 6 arêtes.
Niveau moyen ★★ — 12 questions
Un graphe non orienté a pour sommets X, Y, Z et pour seules arêtes X–Y et Y–Z. Combien vaut le coefficient (X ; Z) de M² ?
- A. 0
- B. 2
- C. 1
- D. 3
Réponse
C. 1 — La seule chaîne de longueur 2 de X à Z est X–Y–Z : le coefficient vaut 1.
Un graphe non orienté simple a cinq sommets de degrés 1, 2, 2, 3 et 4. Combien vaut la somme de tous les coefficients de M ?
- A. 12
- B. 6
- C. 24
- D. 10
Réponse
A. 12 — Les sommes des lignes sont les degrés : 1 + 2 + 2 + 3 + 4 = 12. Le graphe a donc 6 arêtes.
Dans le graphe non orienté de sommets U, V, W, T dont les seules arêtes sont U–V, V–W et W–T, que vaut d(U ; T) ?
- A. 1
- B. 3
- C. 2
- D. 4
Réponse
B. 3 — La seule chaîne de U à T est U–V–W–T : elle a 3 arêtes, donc la distance vaut 3.
Quel est le diamètre du graphe non orienté formé du seul cycle 1–2–3–4–5–1 ?
- A. 1
- B. 4
- C. 3
- D. 2
Réponse
D. 2 — Deux sommets sont voisins ou à distance 2 (par exemple d(1 ; 3) = 2, en passant par 2) : le maximum vaut 2.
Dans un graphe non orienté simple à quatre sommets, la deuxième ligne de M est (1 ; 0 ; 1 ; 1). Que vaut le coefficient (2 ; 2) de M² ?
- A. 0
- B. 9
- C. 1
- D. 3
Réponse
D. 3 — Ce coefficient est la ligne 2 multipliée par la colonne 2 (égale à la ligne, M étant symétrique) : 1 + 0 + 1 + 1 = 3, le degré du sommet 2.
Dans le graphe orienté formé du seul circuit 1 → 2 → 3 → 4 → 5 → 6 → 1, combien y a-t-il de chemins de longueur 9 de 1 à 4 ?
- A. 0
- B. 1
- C. 3
- D. 9
Réponse
B. 1 — Chaque sommet n’a qu’un successeur : le chemin est imposé. En 9 arcs, on fait un tour (6 arcs) puis 3 arcs, et l’on arrive en 4 : un seul chemin.
Dans le graphe orienté d’arcs 1 → 2, 2 → 3 et 3 → 1, que vaut le coefficient (1 ; 1) de M³ ?
- A. 0
- B. 3
- C. 1
- D. 2
Réponse
C. 1 — Le seul chemin fermé de longueur 3 partant de 1 est le circuit 1 → 2 → 3 → 1.
La somme de tous les coefficients de la matrice d’adjacence d’un graphe non orienté vaut 22. Combien a-t-il d’arêtes ?
- A. 22
- B. 11
- C. 44
- D. 10
Réponse
B. 11 — Chaque arête est comptée deux fois (coefficients (i ; j) et (j ; i)) : 22 ÷ 2 = 11 arêtes.
Dans un graphe orienté, la ligne 2 de M² est (1 ; 0 ; 2 ; 1) et la colonne 3 de M est (1 ; 1 ; 0 ; 1). Que vaut le coefficient (2 ; 3) de M³ ?
- A. 2
- B. 3
- C. 4
- D. 1
Réponse
A. 2 — Produit de la ligne par la colonne : 1 × 1 + 0 × 1 + 2 × 0 + 1 × 1 = 2.
Dans un graphe non orienté simple, la somme des coefficients diagonaux de M² vaut 10. Combien le graphe a-t-il d’arêtes ?
- A. 10
- B. 20
- C. 5
- D. 3
Réponse
C. 5 — Les coefficients diagonaux de M² sont les degrés ; leur somme vaut 2m, donc m = 10 ÷ 2 = 5.
Pour un graphe orienté d’ordre 4, la matrice M + M² + M³ a un coefficient nul hors de sa diagonale. Que peut-on conclure ?
- A. Le graphe n’est pas fortement connexe
- B. Le graphe est fortement connexe
- C. Il faut encore calculer M⁴
- D. Le graphe a un circuit
Réponse
A. Le graphe n’est pas fortement connexe — Pour un graphe d’ordre 4, la somme s’arrête à M³ (n − 1 = 3) : un zéro hors de la diagonale prouve qu’un sommet n’en atteint pas un autre.
Dans un graphe orienté, la ligne 3 de M est nulle. Que vaut la ligne 3 de M⁵ ?
- A. elle est égale à celle de M²
- B. elle est nulle
- C. elle ne contient que des 5
- D. on ne peut pas savoir
Réponse
B. elle est nulle — Aucun arc ne part de 3, donc aucun chemin ne part de 3 : la ligne 3 de toute puissance de M est nulle.
Niveau difficile ★★★ — 12 questions
Le coefficient (i ; j) de Mᵏ compte les chemins de longueur k de i à j :
- A. qui ne passent jamais deux fois par un sommet
- B. y compris ceux qui repassent par un même sommet
- C. qui empruntent toutes les arêtes du graphe
- D. qui sont les plus courts de i à j
Réponse
B. y compris ceux qui repassent par un même sommet — Les chemins comptés peuvent repasser par un sommet ou une arête : A–B–A–B est un chemin de longueur 3 de A à B.
Dans un graphe non orienté, le coefficient (i ; j) de M² vaut 4, avec i et j distincts. Que peut-on affirmer ?
- A. d(i ; j) vaut 1 ou 2
- B. d(i ; j) vaut exactement 2
- C. i et j ne sont pas reliés par une arête
- D. il existe quatre arêtes entre i et j
Réponse
A. d(i ; j) vaut 1 ou 2 — Il existe une chaîne de longueur 2, donc d(i ; j) ⩽ 2 ; mais une arête directe peut aussi exister, et la distance vaut alors 1.
Dans un graphe non orienté dont tous les cycles sont de longueur paire, que vaut la somme des coefficients diagonaux de M³ ?
- A. 3
- B. 6
- C. 0
- D. 9
Réponse
C. 0 — Un coefficient diagonal de M³ compte des chemins fermés de longueur 3, c’est-à-dire des triangles, parcourus dans les deux sens : il n’y en a aucun.
Un graphe orienté a 5 sommets. Pour prouver qu’il est fortement connexe à l’aide des puissances de M, il suffit de vérifier que :
- A. M + M² + M³ + M⁴ n’a aucun coefficient nul hors de sa diagonale
- B. M² n’a aucun coefficient nul
- C. M est symétrique et de diagonale nulle
- D. la somme des coefficients diagonaux de M⁵ n’est pas nulle
Réponse
A. M + M² + M³ + M⁴ n’a aucun coefficient nul hors de sa diagonale — Entre deux sommets distincts d’un graphe d’ordre n, s’il existe un chemin, il en existe un d’au plus n − 1 = 4 arcs.
Dans un graphe non orienté simple, la somme des coefficients diagonaux de M³ vaut 18. Combien le graphe a-t-il de triangles ?
- A. 18
- B. 6
- C. 9
- D. 3
Réponse
D. 3 — Chaque triangle est compté six fois : trois sommets de départ et deux sens de parcours. 18 ÷ 6 = 3.
Les sommets d’un graphe non orienté se partagent en deux groupes, et chaque arête relie les deux groupes. Pour i et j dans le même groupe, que vaut le coefficient (i ; j) de M⁵ ?
- A. 5
- B. 0
- C. 1
- D. on ne peut pas savoir
Réponse
B. 0 — Un chemin change de groupe à chaque pas : après 5 pas, il est dans l’autre groupe. Aucun chemin de longueur 5 ne relie deux sommets du même groupe.
Dans un graphe orienté sans boucle, la somme des coefficients diagonaux de M³ vaut 6. Combien a-t-il de circuits de longueur 3 ?
- A. 6
- B. 1
- C. 3
- D. 2
Réponse
D. 2 — Chaque circuit de longueur 3 est compté une fois depuis chacun de ses trois sommets (le sens est imposé) : 6 ÷ 3 = 2.
On sait que les coefficients (i ; j) de M et de M² sont nuls, et que celui de M³ vaut 5. Que vaut d(i ; j) ?
- A. 5
- B. 3
- C. 15
- D. 1
Réponse
B. 3 — La distance est la plus petite puissance qui donne un coefficient non nul : ici 3. Le 5 compte les chemins de longueur 3.
Dans la matrice d’adjacence du graphe complet K₆, que vaut le coefficient (i ; j) de M², pour i et j distincts ?
- A. 5
- B. 4
- C. 6
- D. 30
Réponse
B. 4 — Une chaîne i–r–j de longueur 2 passe par un sommet r distinct de i et de j : il en reste 6 − 2 = 4.
Dans un graphe non orienté, un coefficient diagonal (M²)ᵢᵢ est nul. Que peut-on dire du sommet i ?
- A. il appartient à un triangle
- B. il est relié à tous les autres
- C. il n’appartient à aucun cycle mais a des voisins
- D. il est isolé, de degré 0
Réponse
D. il est isolé, de degré 0 — (M²)ᵢᵢ est le degré de i : il vaut 0 seulement si i n’a aucun voisin.
On change l’ordre des sommets d’un graphe non orienté. La somme des coefficients diagonaux de M³ :
- A. change, car les lignes de M sont permutées
- B. ne change pas : elle vaut 6 fois le nombre de triangles
- C. change, sauf si le graphe est complet
- D. ne change pas, car M reste la même matrice
Réponse
B. ne change pas : elle vaut 6 fois le nombre de triangles — La diagonale de M³ est permutée, mais sa somme compte toujours 6 fois les triangles du graphe, qui ne dépendent pas de l’ordre. La matrice M, elle, change.
Un graphe orienté d’ordre 6 est fortement connexe. La distance d’un sommet à un autre est au plus égale à :
- A. 6
- B. 3
- C. 36
- D. 5
Réponse
D. 5 — Un plus court chemin ne repasse jamais par un même sommet : il visite au plus 6 sommets, donc compte au plus 5 arcs.
Moi c'est Ben, j'ai créé ce site pour aider le plus d'élèves possible, partout en France. Je peux aussi reprendre avec toi ce qui coince en cours particulier : en visio, ou à domicile si tu es à Marseille.
Prof de maths à Marseille · Cours particuliers au lycée · Aide aux devoirs