Terminale maths expertes

Graphes : degrés, chemins et parcours — 20 exercices corrigés

S'entraîner à comprendre les réseaux, leurs parcours et le dénombrement de marches à l'aide de matrices.

L'essentiel à retenir

Pour un graphe non orienté, la somme des degrés vaut deux fois le nombre d'arêtes.
Un graphe connexe possède un circuit eulérien si tous ses sommets ont un degré pair, et une chaîne ouverte s'il en possède exactement deux de degré impair.
Si $M$ est la matrice d'adjacence, $(M^k)_{ij}$ compte les marches de longueur $k$ du sommet $i$ au sommet $j$ .

Exercice 1 — Cycle de 3 sommets

Soit le cycle non orienté

C_{3}

où chaque sommet

k

est relié à

k+1

et le dernier au premier.

Combien y a-t-il d'arêtes ?
Calculer les degrés.
Existe-t-il un circuit eulérien ?

Corrigé détaillé

1. Le cycle compte 3 sommets et exactement

\boxed{3\text{ arêtes}}

. 2. Chaque sommet a deux voisins : tous les degrés valent 2, et leur somme 6 représente deux fois le nombre d'arêtes. 3. Le graphe est connexe et tous les degrés sont pairs : il admet un circuit eulérien, par exemple

1,2,\ldots,3,1

Exercice 2 — Cycle de 4 sommets

Soit le cycle non orienté

C_{4}

où chaque sommet

k

est relié à

k+1

et le dernier au premier.

Combien y a-t-il d'arêtes ?
Calculer les degrés.
Existe-t-il un circuit eulérien ?

Corrigé détaillé

1. Le cycle compte 4 sommets et exactement

\boxed{4\text{ arêtes}}

. 2. Chaque sommet a deux voisins : tous les degrés valent 2, et leur somme 8 représente deux fois le nombre d'arêtes. 3. Le graphe est connexe et tous les degrés sont pairs : il admet un circuit eulérien, par exemple

1,2,\ldots,4,1

Exercice 3 — Cycle de 5 sommets

Soit le cycle non orienté

C_{5}

où chaque sommet

k

est relié à

k+1

et le dernier au premier.

Combien y a-t-il d'arêtes ?
Calculer les degrés.
Existe-t-il un circuit eulérien ?

Corrigé détaillé

1. Le cycle compte 5 sommets et exactement

\boxed{5\text{ arêtes}}

. 2. Chaque sommet a deux voisins : tous les degrés valent 2, et leur somme 10 représente deux fois le nombre d'arêtes. 3. Le graphe est connexe et tous les degrés sont pairs : il admet un circuit eulérien, par exemple

1,2,\ldots,5,1

Exercice 4 — Cycle de 6 sommets

Soit le cycle non orienté

C_{6}

où chaque sommet

k

est relié à

k+1

et le dernier au premier.

Combien y a-t-il d'arêtes ?
Calculer les degrés.
Existe-t-il un circuit eulérien ?

Corrigé détaillé

1. Le cycle compte 6 sommets et exactement

\boxed{6\text{ arêtes}}

. 2. Chaque sommet a deux voisins : tous les degrés valent 2, et leur somme 12 représente deux fois le nombre d'arêtes. 3. Le graphe est connexe et tous les degrés sont pairs : il admet un circuit eulérien, par exemple

1,2,\ldots,6,1

Exercice 5 — Étoile à 3 feuilles

Une étoile possède un centre

O

relié à 3 feuilles, sans autre arête.

Déterminer ses degrés.
Dénombrer les sommets de degré impair.
Décider si le graphe possède une chaîne eulérienne.

Corrigé détaillé

1. Le centre a degré 3, chaque feuille degré 1 ; il y a 3 arêtes. 2. Le nombre de sommets de degré impair est 4, car les feuilles sont toutes de degré impair et le centre l'est seulement si 3 est impair. 3. Comme 4>2, ce graphe connexe n'admet aucune chaîne eulérienne : il est impossible d'emprunter chaque arête exactement une fois.

Exercice 6 — Étoile à 4 feuilles

Une étoile possède un centre

O

relié à 4 feuilles, sans autre arête.

Déterminer ses degrés.
Dénombrer les sommets de degré impair.
Décider si le graphe possède une chaîne eulérienne.

Corrigé détaillé

1. Le centre a degré 4, chaque feuille degré 1 ; il y a 4 arêtes. 2. Le nombre de sommets de degré impair est 4, car les feuilles sont toutes de degré impair et le centre l'est seulement si 4 est impair. 3. Comme 4>2, ce graphe connexe n'admet aucune chaîne eulérienne : il est impossible d'emprunter chaque arête exactement une fois.

Exercice 7 — Étoile à 5 feuilles

Une étoile possède un centre

O

relié à 5 feuilles, sans autre arête.

Déterminer ses degrés.
Dénombrer les sommets de degré impair.
Décider si le graphe possède une chaîne eulérienne.

Corrigé détaillé

1. Le centre a degré 5, chaque feuille degré 1 ; il y a 5 arêtes. 2. Le nombre de sommets de degré impair est 6, car les feuilles sont toutes de degré impair et le centre l'est seulement si 5 est impair. 3. Comme 6>2, ce graphe connexe n'admet aucune chaîne eulérienne : il est impossible d'emprunter chaque arête exactement une fois.

Exercice 8 — Étoile à 6 feuilles

Une étoile possède un centre

O

relié à 6 feuilles, sans autre arête.

Déterminer ses degrés.
Dénombrer les sommets de degré impair.
Décider si le graphe possède une chaîne eulérienne.

Corrigé détaillé

1. Le centre a degré 6, chaque feuille degré 1 ; il y a 6 arêtes. 2. Le nombre de sommets de degré impair est 6, car les feuilles sont toutes de degré impair et le centre l'est seulement si 6 est impair. 3. Comme 6>2, ce graphe connexe n'admet aucune chaîne eulérienne : il est impossible d'emprunter chaque arête exactement une fois.

Exercice 9 — Matrice d'adjacence et marche de longueur 2 — 1

Un graphe non orienté sur A,B,C,D a les arêtes AB, BC, CD.

Écrire sa matrice $M$ d'adjacence.
Calculer $(M^2)_{1,4}$ .
Interpréter le résultat.

Corrigé détaillé

1. La matrice, symétrique avec diagonale nulle, est

M=\begin{pmatrix}0&1&0&0\\1&0&1&0\\0&1&0&1\\0&0&1&0\end{pmatrix}

. 2.

(M^2)_{1,4}=\sum_{k=1}^4M_{1,k}M_{k,4}=\boxed{0}

. 3. Ce nombre compte les marches A-vers-D constituées de deux arêtes, chaque marche étant caractérisée par son sommet intermédiaire.

Exercice 10 — Matrice d'adjacence et marche de longueur 2 — 2

Un graphe non orienté sur A,B,C,D a les arêtes AB, BC, CA, CD.

Écrire sa matrice $M$ d'adjacence.
Calculer $(M^2)_{1,4}$ .
Interpréter le résultat.

Corrigé détaillé

1. La matrice, symétrique avec diagonale nulle, est

M=\begin{pmatrix}0&1&1&0\\1&0&1&0\\1&1&0&1\\0&0&1&0\end{pmatrix}

. 2.

(M^2)_{1,4}=\sum_{k=1}^4M_{1,k}M_{k,4}=\boxed{1}

. 3. Ce nombre compte les marches A-vers-D constituées de deux arêtes, chaque marche étant caractérisée par son sommet intermédiaire.

Exercice 11 — Matrice d'adjacence et marche de longueur 2 — 3

Un graphe non orienté sur A,B,C,D a les arêtes AB, BC, CD, DA.

Écrire sa matrice $M$ d'adjacence.
Calculer $(M^2)_{1,4}$ .
Interpréter le résultat.

Corrigé détaillé

1. La matrice, symétrique avec diagonale nulle, est

M=\begin{pmatrix}0&1&0&1\\1&0&1&0\\0&1&0&1\\1&0&1&0\end{pmatrix}

. 2.

(M^2)_{1,4}=\sum_{k=1}^4M_{1,k}M_{k,4}=\boxed{0}

. 3. Ce nombre compte les marches A-vers-D constituées de deux arêtes, chaque marche étant caractérisée par son sommet intermédiaire.

Exercice 12 — Matrice d'adjacence et marche de longueur 2 — 4

Un graphe non orienté sur A,B,C,D a les arêtes AB, AC, BC, BD, CD.

Écrire sa matrice $M$ d'adjacence.
Calculer $(M^2)_{1,4}$ .
Interpréter le résultat.

Corrigé détaillé

1. La matrice, symétrique avec diagonale nulle, est

M=\begin{pmatrix}0&1&1&0\\1&0&1&1\\1&1&0&1\\0&1&1&0\end{pmatrix}

. 2.

(M^2)_{1,4}=\sum_{k=1}^4M_{1,k}M_{k,4}=\boxed{2}

. 3. Ce nombre compte les marches A-vers-D constituées de deux arêtes, chaque marche étant caractérisée par son sommet intermédiaire.

Exercice 13 — Plus court chemin à trois sommets — 1

Dans un graphe pondéré, les arêtes AB, BC, AC ont pour coûts respectifs 3, 4 et 9.

Énumérer les chemins simples de A à C.
Comparer leurs coûts.
Identifier le plus court.

Corrigé détaillé

1. Les chemins simples sont

A-C

A-B-C

. 2. Le chemin direct coûte 9, alors que le chemin par B coûte 3+4=7. 3. Le coût minimal est

\boxed{7}

et le(s) meilleur(s) itinéraire(s) : A-B-C. Avec des coûts positifs, un chemin contenant un détour cyclique ne peut améliorer la solution.

Exercice 14 — Plus court chemin à trois sommets — 2

Dans un graphe pondéré, les arêtes AB, BC, AC ont pour coûts respectifs 4, 5 et 7.

Énumérer les chemins simples de A à C.
Comparer leurs coûts.
Identifier le plus court.

Corrigé détaillé

1. Les chemins simples sont

A-C

A-B-C

. 2. Le chemin direct coûte 7, alors que le chemin par B coûte 4+5=9. 3. Le coût minimal est

\boxed{7}

et le(s) meilleur(s) itinéraire(s) : A-C. Avec des coûts positifs, un chemin contenant un détour cyclique ne peut améliorer la solution.

Exercice 15 — Plus court chemin à trois sommets — 3

Dans un graphe pondéré, les arêtes AB, BC, AC ont pour coûts respectifs 6, 2 et 6.

Énumérer les chemins simples de A à C.
Comparer leurs coûts.
Identifier le plus court.

Corrigé détaillé

1. Les chemins simples sont

A-C

A-B-C

. 2. Le chemin direct coûte 6, alors que le chemin par B coûte 6+2=8. 3. Le coût minimal est

\boxed{6}

et le(s) meilleur(s) itinéraire(s) : A-C. Avec des coûts positifs, un chemin contenant un détour cyclique ne peut améliorer la solution.

Exercice 16 — Plus court chemin à trois sommets — 4

Dans un graphe pondéré, les arêtes AB, BC, AC ont pour coûts respectifs 5, 8 et 10.

Énumérer les chemins simples de A à C.
Comparer leurs coûts.
Identifier le plus court.

Corrigé détaillé

1. Les chemins simples sont

A-C

A-B-C

. 2. Le chemin direct coûte 10, alors que le chemin par B coûte 5+8=13. 3. Le coût minimal est

\boxed{10}

et le(s) meilleur(s) itinéraire(s) : A-C. Avec des coûts positifs, un chemin contenant un détour cyclique ne peut améliorer la solution.

Exercice 17 — Caractère eulérien d'un réseau — 1

Le graphe non orienté sur A,B,C,D possède les arêtes AB, BC, CD.

Calculer le degré de chaque sommet.
Compter les sommets de degré impair.
Décider si toutes les arêtes peuvent être parcourues une seule fois.

Corrigé détaillé

1. Les degrés des sommets A,B,C,D valent respectivement (1, 2, 2, 1). 2. Le graphe connexe possède 2 sommets de degré impair. 3. Un graphe connexe admet un circuit eulérien si le nombre est 0, une chaîne ouverte si le nombre est 2, et aucune chaîne eulérienne sinon. Ici :

\boxed{\text{chaîne ouverte}}

Exercice 18 — Caractère eulérien d'un réseau — 2

Le graphe non orienté sur A,B,C,D possède les arêtes AB, BC, CD, DA.

Calculer le degré de chaque sommet.
Compter les sommets de degré impair.
Décider si toutes les arêtes peuvent être parcourues une seule fois.

Corrigé détaillé

1. Les degrés des sommets A,B,C,D valent respectivement (2, 2, 2, 2). 2. Le graphe connexe possède 0 sommets de degré impair. 3. Un graphe connexe admet un circuit eulérien si le nombre est 0, une chaîne ouverte si le nombre est 2, et aucune chaîne eulérienne sinon. Ici :

\boxed{\text{circuit fermé}}

Exercice 19 — Caractère eulérien d'un réseau — 3

Le graphe non orienté sur A,B,C,D possède les arêtes AB, BC, CD, DA, AC.

Calculer le degré de chaque sommet.
Compter les sommets de degré impair.
Décider si toutes les arêtes peuvent être parcourues une seule fois.

Corrigé détaillé

1. Les degrés des sommets A,B,C,D valent respectivement (3, 2, 3, 2). 2. Le graphe connexe possède 2 sommets de degré impair. 3. Un graphe connexe admet un circuit eulérien si le nombre est 0, une chaîne ouverte si le nombre est 2, et aucune chaîne eulérienne sinon. Ici :

\boxed{\text{chaîne ouverte}}

Exercice 20 — Caractère eulérien d'un réseau — 4

Le graphe non orienté sur A,B,C,D possède les arêtes AB, AC, AD.

Calculer le degré de chaque sommet.
Compter les sommets de degré impair.
Décider si toutes les arêtes peuvent être parcourues une seule fois.

Corrigé détaillé

1. Les degrés des sommets A,B,C,D valent respectivement (3, 1, 1, 1). 2. Le graphe connexe possède 4 sommets de degré impair. 3. Un graphe connexe admet un circuit eulérien si le nombre est 0, une chaîne ouverte si le nombre est 2, et aucune chaîne eulérienne sinon. Ici :

\boxed{\text{aucune chaîne}}

Besoin d'aide sur ce chapitre ?

Réserver le bilan offert de 30 min Cours particuliers de maths expertes