Vrai/Faux : Chaînes et cycles dans un graphe

[enonce]
Pour chaque affirmation suivante sur les chaînes et cycles dans un graphe (en particulier les eulériens), indiquer si elle est Vraie ou Fausse.
[/enonce]

[etape]
Affirmation : La longueur d'une chaîne est égale au nombre de sommets qu'elle visite.

[qcm]
[option]Vrai[/option]
[option correct="true"]Faux[/option]
[reponse statut="correct"]Bonne réponse !
La longueur d'une chaîne se mesure en nombre d'arêtes parcourues, pas en sommets. Pour une chaîne sans répétition de sommet, on a la relation : nombre de sommets = longueur + $1$ (les deux extrémités plus les sommets intermédiaires).[/reponse]
[reponse statut="incorrect"]Non, cette affirmation est fausse.
Petite erreur classique : la longueur d'une chaîne se compte en arêtes, pas en sommets. La chaîne $A \to B \to C$ a $3$ sommets mais une longueur de $2$ (deux arêtes parcourues).[/reponse]
[/qcm]

[solution]
Cette affirmation est fausse. La longueur d'une chaîne est son nombre d'arêtes ; pour une chaîne sans répétition, le nombre de sommets vaut longueur + $1$.
[/solution]
[/etape]

[etape]
Affirmation : Un graphe non connexe peut admettre une chaîne eulérienne.

[qcm]
[option]Vrai[/option]
[option correct="true"]Faux[/option]
[reponse statut="correct"]Tu as raison !
Une chaîne eulérienne doit utiliser toutes les arêtes du graphe. Si le graphe a deux composantes disjointes, aucune chaîne ne peut traverser de l'une à l'autre, donc aucune ne peut couvrir l'ensemble des arêtes : la connexité est nécessaire.[/reponse]
[reponse statut="incorrect"]Non, cette affirmation est fausse.
Visualiser deux morceaux de graphe non reliés : pour passer de l'un à l'autre, il faut une arête, qui par hypothèse n'existe pas. Toute chaîne reste donc cantonnée à un seul morceau et ne peut pas être eulérienne.[/reponse]
[/qcm]

[solution]
Cette affirmation est fausse. Pour avoir une chaîne eulérienne, il faut que le graphe soit connexe : sinon aucune chaîne ne peut couvrir toutes les arêtes.
[/solution]
[/etape]

[etape]
Affirmation : Dans tout graphe, le nombre de sommets de degré impair est pair.

[qcm]
[option correct="true"]Vrai[/option]
[option]Faux[/option]
[reponse statut="correct"]Exactement !
La somme des degrés vaut $2 \times$ nombre d'arêtes, qui est un entier pair. Or si l'on additionne uniquement les degrés impairs, leur somme doit elle aussi avoir une parité compatible avec le total pair : il faut donc un nombre pair de termes impairs. C'est le « lemme des poignées de main ».[/reponse]
[reponse statut="incorrect"]Non, cette affirmation est vraie.
C'est un résultat fondamental connu sous le nom de lemme des poignées de main. Il découle de l'égalité « somme des degrés = $2 \times$ nombre d'arêtes » : seul un nombre pair de termes impairs peut donner une somme paire.[/reponse]
[/qcm]

[solution]
Cette affirmation est vraie. C'est le lemme des poignées de main : la somme des degrés vaut $2 \times$ nombre d'arêtes, donc il y a un nombre pair de sommets de degré impair.
[/solution]
[/etape]

[etape]
Affirmation : Un graphe connexe ayant exactement deux sommets de degré impair admet un cycle eulérien.

[qcm]
[option]Vrai[/option]
[option correct="true"]Faux[/option]
[reponse statut="correct"]Bravo !
Avec deux sommets de degré impair, le théorème d'Euler garantit l'existence d'une chaîne eulérienne, mais celle-ci ne se referme pas : ses extrémités sont précisément les deux sommets impairs. Pour un cycle eulérien (chaîne fermée), il faudrait $0$ sommet de degré impair.[/reponse]
[reponse statut="incorrect"]Non, cette affirmation est fausse.
Les deux cas du théorème d'Euler sont à bien distinguer : $0$ sommet impair donne un cycle eulérien (chaîne fermée), $2$ sommets impairs donnent une chaîne eulérienne (extrémités distinctes), au-delà ni l'un ni l'autre.[/reponse]
[/qcm]

[solution]
Cette affirmation est fausse. Avec exactement $2$ sommets de degré impair, le graphe admet une chaîne eulérienne (entre ces deux sommets) mais pas un cycle eulérien : il faut $0$ sommet impair pour cela.
[/solution]
[/etape]

[etape]
Affirmation : Tout cycle est en particulier une chaîne.

[qcm]
[option correct="true"]Vrai[/option]
[option]Faux[/option]
[reponse statut="correct"]C'est bien ça !
Un cycle est, par définition, une chaîne fermée dont toutes les arêtes sont distinctes. Toute notion de cycle suppose donc déjà l'existence d'une chaîne sous-jacente. Un cycle est un cas particulier de chaîne, contraint à revenir à son point de départ.[/reponse]
[reponse statut="incorrect"]Non, cette affirmation est vraie.
Le vocabulaire suit une hiérarchie : la chaîne est la notion la plus générale (suite de sommets reliés deux à deux), le cycle ajoute deux contraintes (être fermé et avoir toutes les arêtes distinctes).[/reponse]
[/qcm]

[solution]
Cette affirmation est vraie. Par définition, un cycle est une chaîne fermée à arêtes distinctes : il s'agit d'un cas particulier de chaîne.
[/solution]
[/etape]

[etape]
Affirmation : Un graphe connexe à $6$ sommets dont les degrés sont $(2\,;\,4\,;\,2\,;\,4\,;\,2\,;\,4)$ admet un cycle eulérien.

[qcm]
[option correct="true"]Vrai[/option]
[option]Faux[/option]
[reponse statut="correct"]Parfait !
Tous les degrés ($2$ et $4$) sont pairs : le graphe possède $0$ sommet de degré impair. Le théorème d'Euler garantit alors l'existence d'un cycle eulérien dans ce graphe connexe.[/reponse]
[reponse statut="incorrect"]Non, cette affirmation est vraie.
Vérifier la parité de chaque degré : $2$ et $4$ sont tous deux pairs. Le critère du cycle eulérien (« $0$ sommet de degré impair, dans un graphe connexe ») est rempli.[/reponse]
[/qcm]

[solution]
Cette affirmation est vraie. Tous les degrés sont pairs et le graphe est connexe, donc le théorème d'Euler garantit l'existence d'un cycle eulérien.
[/solution]
[/etape]

QCM : Chaînes et cycles eulériens

[enonce]
Ce QCM porte sur les chaînes et cycles eulériens et le théorème d'Euler. Pour chaque question, choisissez la bonne réponse parmi les quatre propositions.
[/enonce]

[etape]
Qu'appelle-t-on une chaîne eulérienne dans un graphe ?
[qcm]
[option]Une chaîne qui passe par tous les sommets une fois et une seule.[/option]
[option correct="true"]Une chaîne qui utilise chaque arête une fois et une seule.[/option]
[option]Une chaîne fermée dont les sommets sont tous distincts.[/option]
[option]La chaîne la plus courte entre deux sommets donnés.[/option]
[reponse statut="correct"]Exactement !
Une chaîne eulérienne contient chaque arête du graphe une fois et une seule. Les sommets, eux, peuvent être visités plusieurs fois ; ce qui compte est de parcourir toutes les arêtes sans en répéter aucune.[/reponse]
[reponse motif="Une chaîne qui passe par tous les sommets une fois et une seule."]Non.
Cette définition est celle d'une chaîne hamiltonienne (parcours des sommets), pas eulérienne. Le théorème d'Euler porte sur les arêtes, pas sur les sommets.[/reponse]
[reponse motif="Une chaîne fermée dont les sommets sont tous distincts."]Non.
Cette description s'apparente à un cycle élémentaire. Une chaîne eulérienne n'est pas nécessairement fermée et peut repasser par certains sommets.[/reponse]
[reponse motif="La chaîne la plus courte entre deux sommets donnés."]Non.
La plus courte chaîne (au sens du nombre d'arêtes ou du poids) est traitée par d'autres outils, comme l'algorithme de Dijkstra, et n'a pas de lien direct avec la notion d'eulérien.[/reponse]
[reponse statut="incorrect"]Non.
Une chaîne eulérienne est une chaîne qui contient chaque arête du graphe une fois et une seule.[/reponse]
[/qcm]
[/etape]

[etape]
Que dit le théorème d'Euler concernant l'existence d'une chaîne eulérienne dans un graphe connexe ?
[qcm]
[option]Une chaîne eulérienne existe si tous les sommets sont de degré pair.[/option]
[option correct="true"]Une chaîne eulérienne existe si et seulement si le graphe possède $0$ ou $2$ sommets de degré impair.[/option]
[option]Une chaîne eulérienne existe si et seulement si le graphe est complet.[/option]
[option]Une chaîne eulérienne existe si et seulement si le nombre d'arêtes est pair.[/option]
[reponse statut="correct"]Bonne réponse !
Le théorème d'Euler affirme : un graphe connexe admet une chaîne eulérienne si et seulement si il a exactement $0$ ou $2$ sommets de degré impair (dans le cas $2$, ce sont les extrémités de la chaîne ; dans le cas $0$, on obtient même un cycle eulérien).[/reponse]
[reponse motif="Une chaîne eulérienne existe si tous les sommets sont de degré pair."]Non.
Cette propriété est une condition pour l'existence d'un cycle eulérien (cas particulier où la chaîne est fermée), mais elle ignore le cas avec exactement $2$ sommets de degré impair, qui donne aussi une chaîne eulérienne (non fermée).[/reponse]
[reponse motif="Une chaîne eulérienne existe si et seulement si le graphe est complet."]Non.
La complétude n'a aucun lien direct avec l'eulérianité. Par exemple, le graphe complet $K_{4}$ a des sommets de degré $3$ (impair) en nombre $4$, donc il n'admet pas de chaîne eulérienne.[/reponse]
[reponse motif="Une chaîne eulérienne existe si et seulement si le nombre d'arêtes est pair."]Non.
Le nombre total d'arêtes n'est pas le critère retenu. Ce qui compte, c'est la parité des degrés des sommets, pas la parité du nombre d'arêtes.[/reponse]
[reponse statut="incorrect"]Non.
Le théorème d'Euler pour les chaînes : un graphe connexe admet une chaîne eulérienne si et seulement s'il a exactement $0$ ou $2$ sommets de degré impair.[/reponse]
[/qcm]
[/etape]

[etape]
À quelle condition supplémentaire un graphe connexe admet-il un cycle eulérien (pas seulement une chaîne) ?
[qcm]
[option]Au moins un sommet doit être de degré impair.[/option]
[option correct="true"]Tous les sommets doivent être de degré pair.[/option]
[option]Le graphe doit être complet.[/option]
[option]Le nombre de sommets doit être pair.[/option]
[reponse statut="correct"]Tu as raison !
Pour qu'un graphe connexe admette un cycle eulérien, il faut $0$ sommet de degré impair, c'est-à-dire que tous les sommets soient de degré pair. La chaîne se referme alors naturellement sur son point de départ.[/reponse]
[reponse motif="Au moins un sommet doit être de degré impair."]Non.
C'est la situation contraire qui est visée. Dès qu'il existe un sommet de degré impair, ce sommet doit être une extrémité de la chaîne eulérienne, ce qui empêche la fermeture en cycle.[/reponse]
[reponse motif="Le graphe doit être complet."]Non.
Aucun lien direct entre complétude et cycle eulérien. Le graphe complet $K_{5}$ admet bien un cycle eulérien (tous les degrés valent $4$, qui est pair), mais la complétude n'est pas la cause de cette propriété.[/reponse]
[reponse motif="Le nombre de sommets doit être pair."]Non.
La parité du nombre de sommets ne joue aucun rôle. Ce qui compte est la parité des degrés de chaque sommet pris individuellement.[/reponse]
[reponse statut="incorrect"]Non.
Un graphe connexe admet un cycle eulérien si et seulement si tous ses sommets sont de degré pair.[/reponse]
[/qcm]
[/etape]

[etape]
Soit un graphe connexe à $5$ sommets dont la liste des degrés est $(2\,;\,3\,;\,4\,;\,3\,;\,2)$. Que peut-on conclure ?
[qcm]
[option]Le graphe admet un cycle eulérien.[/option]
[option correct="true"]Le graphe admet une chaîne eulérienne, mais pas de cycle eulérien.[/option]
[option]Le graphe n'admet ni chaîne, ni cycle eulérien.[/option]
[option]On ne peut pas conclure sans dessiner le graphe.[/option]
[reponse statut="correct"]Bravo !
On compte les sommets de degré impair : seuls les degrés $3$ apparaissent en deux exemplaires. Il y a donc exactement $2$ sommets de degré impair. Le graphe étant connexe, le théorème d'Euler garantit l'existence d'une chaîne eulérienne (non fermée) entre ces deux sommets.[/reponse]
[reponse motif="Le graphe admet un cycle eulérien."]Non.
Pour un cycle eulérien, tous les degrés doivent être pairs. Or ici, deux sommets ont le degré $3$ (impair) : la chaîne ne peut pas se refermer.[/reponse]
[reponse motif="Le graphe n'admet ni chaîne, ni cycle eulérien."]Non.
Le théorème d'Euler autorise jusqu'à $2$ sommets de degré impair pour avoir une chaîne eulérienne. Compter avec attention le nombre de degrés impairs avant de conclure.[/reponse]
[reponse motif="On ne peut pas conclure sans dessiner le graphe."]Non.
La connaissance des degrés et de la connexité suffit à appliquer le théorème d'Euler. Le dessin n'apporterait pas d'information supplémentaire pour ce critère.[/reponse]
[reponse statut="incorrect"]Non.
Avec exactement $2$ sommets de degré impair et un graphe connexe, le théorème d'Euler donne l'existence d'une chaîne eulérienne, mais pas d'un cycle eulérien.[/reponse]
[/qcm]
[/etape]

[etape]
Un graphe est dit traçable « sans lever le crayon et sans repasser sur une arête » lorsqu'il admet une chaîne eulérienne. Parmi les listes de degrés suivantes (pour des graphes connexes), laquelle correspond à un graphe non traçable ainsi ?
[qcm]
[option]$(2\,;\,2\,;\,2\,;\,2)$[/option]
[option correct="true"]$(3\,;\,3\,;\,3\,;\,3)$[/option]
[option]$(2\,;\,3\,;\,3\,;\,4)$[/option]
[option]$(4\,;\,4\,;\,4\,;\,4)$[/option]
[reponse statut="correct"]Parfait !
Avec $4$ sommets de degré $3$ (impair), le graphe possède $4$ sommets de degré impair. Or le théorème d'Euler exige $0$ ou $2$ sommets de degré impair. Le graphe ne peut donc pas être tracé sans lever le crayon.[/reponse]
[reponse motif="$(2\,;\,2\,;\,2\,;\,2)$"]Non.
Tous les degrés sont pairs : il y a $0$ sommet de degré impair. Le graphe admet même un cycle eulérien (cas plus fort), donc bien sûr une chaîne eulérienne.[/reponse]
[reponse motif="$(2\,;\,3\,;\,3\,;\,4)$"]Non.
Compter les degrés impairs : on en a exactement $2$ (deux sommets de degré $3$). Le théorème d'Euler donne l'existence d'une chaîne eulérienne entre ces deux sommets.[/reponse]
[reponse motif="$(4\,;\,4\,;\,4\,;\,4)$"]Non.
Tous les degrés sont pairs ($4$ est pair). Il y a $0$ sommet de degré impair, donc un cycle eulérien existe (et a fortiori une chaîne eulérienne).[/reponse]
[reponse statut="incorrect"]Non.
$(3\,;\,3\,;\,3\,;\,3)$ donne $4$ sommets de degré impair. Or le théorème d'Euler n'autorise que $0$ ou $2$ sommets de degré impair pour qu'une chaîne eulérienne existe.[/reponse]
[/qcm]
[/etape]

[etape]
Pour que le théorème d'Euler s'applique et donne une réponse fiable, quelle autre hypothèse doit être satisfaite (au-delà du compte des degrés impairs) ?
[qcm]
[option]Le graphe doit être orienté.[/option]
[option correct="true"]Le graphe doit être connexe.[/option]
[option]Le graphe doit être complet.[/option]
[option]Le nombre d'arêtes doit être supérieur au nombre de sommets.[/option]
[reponse statut="correct"]C'est bien ça !
Le théorème d'Euler n'a de sens que pour un graphe connexe. Si le graphe se compose de plusieurs morceaux disjoints, on ne pourra jamais visiter toutes les arêtes en un seul tracé, quel que soit le nombre de sommets de degré impair.[/reponse]
[reponse motif="Le graphe doit être orienté."]Non.
L'eulérianité s'étudie aussi bien sur des graphes orientés que non orientés ; ce n'est pas une restriction du théorème.[/reponse]
[reponse motif="Le graphe doit être complet."]Non.
La complétude est une propriété beaucoup plus forte qui n'est ni nécessaire ni suffisante : un graphe complet peut très bien avoir trop de degrés impairs (par exemple $K_{4}$).[/reponse]
[reponse motif="Le nombre d'arêtes doit être supérieur au nombre de sommets."]Non.
Aucune contrainte de ce type. Un graphe connexe avec moins d'arêtes que de sommets (un arbre par exemple) peut très bien admettre une chaîne eulérienne... ou non, selon les degrés.[/reponse]
[reponse statut="incorrect"]Non.
Le théorème d'Euler suppose que le graphe est connexe. Sinon, aucun parcours d'arêtes ne peut couvrir l'ensemble du graphe.[/reponse]
[/qcm]
[/etape]

Graphes – Bac blanc ES/L Sujet 3 – Maths-cours 2018 (spé)

Pour chacune des cinq affirmations suivantes, indiquer si elle est vraie ou fausse en justifiant la réponse.
Il est attribué un point par réponse exacte correctement justifiée.
Une réponse non justifiée n'est pas prise en compte.

On modélise le plan d'un village à l'aide du graphe (G) ci-dessous :

Les sommets du graphe (G) représentent les carrefours et les arêtes du graphe schématisent les routes reliant ces carrefours.

Affirmation 1 : Le graphe (G) est connexe.
Affirmation 2 : Le graphe (G) contient un sous-graphe complet d'ordre 4.
Affirmation 3 : Une personne peut parcourir toutes les routes du village sans emprunter plusieurs fois la même route.
Affirmation 4 : Il y a exactement 5 trajets de trois routes reliant les carrefours C et E.
On pourra utiliser la calculatrice pour justifier la réponse à l'aide d'un calcul matriciel.

On pondère le graphe (G) par les longueurs, en centaines de mètres, de chacune des routes :

Affirmation 5 : Le plus court chemin menant de A à D mesure 700 mètres .
On justifiera la réponse à l'aide d'un algorithme.

Corrigé

Affirmation 1 : Le graphe (G) est connexe : EXACT.

Un graphe est connexe si et seulement si on peut relier deux quelconques de ses sommets par une chaîne.

C'est bien le cas ici donc le graphe (G) est connexe.
Affirmation 2 : Le graphe (G) contient un sous-graphe complet d'ordre 4 : EXACT.

Considérons le sous-graphe d'ordre 4 composé des sommets B, D, E et F. Chacun de ces sommets est relié aux trois autres.
Ce sous-graphe est donc complet.
Affirmation 3 : Une personne peut parcourir toutes les routes du village sans emprunter plusieurs fois la même route : EXACT.

La question revient à déterminer s'il existe une chaîne qui contient une fois et une seule chacune des arêtes du graphe c'est à dire une chaîne eulérienne.

Or, d'après le théorème d'Euler, un graphe connexe contient une chaîne eulérienne si et seulement s'il possède 0 ou 2 sommets de degré impair.

Le tableau ci-après recense le degré de chacun des sommets :

Sommet A B C D E F

Degré 2 5 2 4 4 3

Le graphe (G) possède deux sommets de degré impair : B et F. Il existe donc au moins un trajet qui emprunte une fois et une seule chacune des routes du graphe.
Ces trajets ont nécessairement comme extrémités B et F ; par exemple : B-C-D-E-A-B-E-F-D-B-F.
Affirmation 4 : Il y a exactement 5 trajets de trois routes reliant les carrefours C et E: EXACT.

La matrice d'adjacence du graphe (G) obtenue en classant les sommets par ordre alphabétique est :

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

Pour obtenir le nombre de chemins de trois routes reliant deux sommets on calcule $ M^3 $.

À la calculatrice, on trouve :

$ M^3 = \begin{pmatrix} 2 &8 &3 &5 &7 &4 \\ 8 &10 &8 &11 &11 &11 \\ 3 &8 &2 &7 &5 &4 \\ 5 &11 &7 &8 &11 &9 \\ 7 &11 &5 &11 &8 &9\\ 4 &11 &4 &9 &9 &6 \end{pmatrix} $

Le nombre de chemins de trois routes, reliant C à E, est le coefficient de $ M^3 $ situé sur la troisième ligne (correspondant au sommet de départ C) et la cinquième colonne (correspondant au sommet d'arrivé E).

Il y a donc bien 5 trajets de trois routes reliant les carrefours C et E.

En pratique

Soit $ M $ la matrice d'adjacence d'un graphe G. Pour déterminer le nombre de chemins de longueur $n$ reliant deux sommets du graphe on calcule $ M^n $ .

Le coefficient de la matrice $ M^n $ situé à la $ i $-ème ligne et à la $ j $-ème colonne indique le nombre de chemins de longueur $ n $ menant du sommet numéro $ i $ au sommet numéro $ j $.
Affirmation 5 : Le plus court chemin menant de A à D mesure 700 mètres : FAUX.

On utilise l'algorithme de Dijkstra en partant de A :

Le trajet le plus court menant de A à D mesure 6 centaines de mètres soit 600 mètres.

Il s'agit du trajet A-B-F-D.

Pour plus de détails sur la méthode employée dans cette question se reporter à la fiche consacrée à l'algorithme de Dijkstra.

Graphes – Bac blanc ES Sujet 2 – Maths-cours 2018 (spé)

Une agence de tourisme propose la visite de certains monuments parisiens.

Chacun de ces monuments est désigné par une lettre comme suit :

E : Tour Eiffel
L : Musée du Louvre
M : Tour Montparnasse
N : Cathédrale Notre-Dame de Paris
S : Basilique du Sacré-Cœur de Montmartre
T : Arc de triomphe

Cette agence fait appel à une société de transport par autocar qui propose les liaisons suivantes (chacune de ces liaisons pouvant s'effectuer dans les deux sens de circulation) :

Graphe des liaisons entre monuments parisiens

Expliquer pourquoi il est possible de trouver un trajet empruntant une fois et une seule chacune des dix liaisons indiquées sur le graphe.
Donner un exemple d'un tel trajet.
1. Donner la matrice d'adjacence $ M $ associée à ce graphe en classant les sommets par ordre alphabétique.
2. On donne :
  
  $ M^2 = \begin{pmatrix} 4 &2 &1 &3 &2 &1 \\ 2 &4 &2 &2 &2 &2 \\ 1 &2 &3 &1 &3 &1 \\ 3 &2 &1 &3 &1 &1 \\ 2 &2 &3 &1 &4 &1\\ 1 &2 &1 &1 &1 &2 \end{pmatrix} $
  
  $ M^3 = \begin{pmatrix} 6 &10 &9 &5 &10 &6 \\ 10 &8 &8 &8 &10 &4 \\ 9 &8 &4 &8 &5 &4 \\ 5 &8 &8 &4 &9 &4 \\ 10 &10 &5 &9 &6 &6\\ 6 &4 &4 &4 &6 &2 \end{pmatrix} $
  
  Combien y a-t-il de trajets permettant de relier la cathédrale Notre-Dame de Paris et la tour Eiffel en utilisant au maximum trois liaisons.
  Justifier votre réponse.
On complète le graphe précédent en indiquant, sur chacune des branches, la durée du trajet, en minutes, entre deux monuments.

On souhaite aller de la tour Montparnasse à la Basilique du Sacré-Cœur de Montmartre.

En utilisant un algorithme, déterminer le trajet le plus rapide ainsi que la durée de ce trajet.

Corrigé

Trouver un trajet qui emprunte une fois et une seule chacune des liaisons indiquées sur le graphe revient à déterminer une chaîne eulérienne.

Le théorème d'Euler indique qu'un graphe connexe contient une chaîne eulérienne si et seulement s'il ne possède que 0 ou 2 sommets de degré impair.

Les degrés des sommets sont indiqués dans le tableau ci-après :

Sommet E L M N S T

Degré 4 4 3 3 4 2

Le graphe comporte deux sommets de degré impair : M et N. Il est donc possible de relier M (Tour Montparnasse) à N (Cathédrale Notre-Dame de Paris) en empruntant une fois et une seule chacune des liaisons; par exemple : M-E-T-S-E-L-S-N-L-M-N.
1. En classant les sommets par ordre alphabétique, on obtient la matrice d'adjacence suivante :
  
  $ M = \begin{pmatrix} 0 &1 &1 &0 &1 &1 \\ 1 &0 &1 &1 &1 &0 \\ 1 &1 &0 &1 &0 &0 \\ 0 &1 &1 &0 &1 &0 \\ 1 &1 &0 &1 &0 &1\\ 1 &0 &0 &0 &1 &0 \end{pmatrix} $
2. Le coefficient situé sur la $ 4^{\text{e}} $ ligne (correspondant à la cathédrale Notre-Dame de Paris) et la $ 1^{\text{ère}} $ colonne (correspondant à la tour Eiffel) de la matrice $ M $ est égal à 0.
  Il n'y a donc aucun trajet reliant la cathédrale Notre-Dame de Paris et la tour Eiffel en utilisant une et une seule liaison.
  
  Le coefficient situé sur la $ 4^{\text{e}} $ ligne et la $ 1^{\text{ère}} $ colonne de la matrice $ M^2 $ est égal à 3.
  Il y a donc 3 trajets reliant la cathédrale Notre-Dame de Paris et la tour Eiffel en utilisant exactement deux liaisons.
  
  Le coefficient situé sur la $ 4^{\text{e}} $ ligne et la $ 1^{\text{ère}} $ colonne de la matrice $ M^3 $ est égal à 5.
  Il y a donc 5 trajets reliant la cathédrale Notre-Dame de Paris et la tour Eiffel en utilisant exactement trois liaisons.
  
  Au total, on trouve qu'il existe exactement huit trajets permettant de relier la cathédrale Notre-Dame de Paris et la tour Eiffel en utilisant au maximum trois liaisons.

On utilise l'algorithme de Dijkstra :

Départ	$\infty$	$\infty$	$\mathbf{0_M}$	$\infty$	$\infty$	$\infty$
M (0)	$10_M$	$7_M$	—	$\mathbf{4_M}$	$\infty$	$\infty$
N (4)	$10_M$	$\mathbf{6_N}$	—	—	$12_N$	$\infty$
L (6)	$\mathbf{10_M}$	—	—	—	$11_L$	$\infty$
E (10)	—	—	—	—	$\mathbf{11_L}$	$14_E$

Reportez-vous à la page « méthode » : l'algorithme de Dijkstra étape par étape pour obtenir la méthode de construction détaillée de ce tableau.

Le trajet le plus rapide pour aller de la tour Montparnasse à la Basilique du Sacré-Cœur de Montmartre est le trajet M-N-L-S, c'est à dire Montparnasse - Notre-Dame de Paris - Louvre - Sacré-Cœur.

Sa durée est de 11 minutes.

Graphes – Bac blanc ES Sujet 1 – Maths-cours 2018 (spé)

Un appartement comporte 6 pièces notées A, B, C, D, E et F.

Le plan ci-après présente la disposition des pièces ainsi que les portes de communication entre ces pièces.

Par exemple, il y a une porte de communication entre les pièces A et B mais il n'y en a pas entre les pièces B et E.

La porte donnant accès à l'appartement est sans importance dans le cadre de l'exercice et n'a pas été représentée.

Toutes les réponses aux questions posées devront être justifiées.

1. Traduire la situation à l'aide d'un graphe (G) dont les sommets représentent les pièces et dont les arêtes représentent les portes de communication.
2. Le graphe (G) est-il connexe ? complet ?
1. Est-il possible de parcourir l'appartement en empruntant chaque porte une fois et une seule ?
  Si oui, donner un exemple d'un tel chemin.
2. Est-il possible de parcourir l'appartement en empruntant chaque porte une fois et une seule et en partant et en arrivant dans la même pièce ?
  Si oui, donner un exemple d'un tel chemin.
Déterminer la matrice d'adjacence $ M $ associée au graphe précédent en prenant les sommets par ordre alphabétique.
À l'aide d'une calculatrice on trouve :

$ M^3 = \begin{pmatrix} 2 &5 &2 &3 &7 &4 \\ 5 &0 &5 &2 &2 &2 \\ 2 &5 &2 &4 &7 &3 \\ 3 &2 &4 &2 &5 &2 \\ 7 &2 &7 &5 &4 &5\\ 4 &2 &3 &2 &5 &2 \end{pmatrix} $
1. Combien existe-t-il de chemins permettant d'aller de la pièce A à la pièce D en empruntant exactement trois portes ?
  Donner la liste de ces chemins.
2. Est-il toujours possible de relier deux pièces différentes en empruntant exactement trois portes ?
1. Montrer qu'il existe au moins un sous-graphe complet de (G) d'ordre 3.
2. Le propriétaire souhaite repeindre l'appartement en respectant les règles suivantes :
  - chaque pièce sera repeinte avec une couleur unique ;
  - deux pièces adjacentes, c'est à dire reliées par une porte, seront repeintes avec des couleurs différentes.
  Pourra-t-il réaliser ces objectifs en utilisant seulement trois couleurs ?

Corrigé

1. On place d'abord les sommets A, B, C, D, E et F qui représentent les pièces et on relie, par des arêtes, les pièces qui communiquent : A-B, A-E, A-F, B-C, C-D, C-E, D-E, E-F.
2. Le graphe est connexe. En effet, un graphe est connexe si deux sommets quelconques peuvent être reliés par une chaîne ce qui est le cas ici.
  
  Le graphe n'est pas complet. Un graphe non orienté est complet si et seulement si tous ses sommets sont reliés par une arête. Ce n'est pas le cas ici pour A et C par exemple.
  
  À retenir
  
  Un graphe est complet si et seulement si tous ses sommets sont deux à deux adjacents (c'est à dire reliés par une arête).
  
  Un graphe est connexe si et seulement si deux sommets quelconques peuvent être reliés par une chaîne (intuitivement cela signifie que le graphe est en « un seul morceau »).
1. On recherche s'il existe une chaîne eulérienne, c'est à dire une chaîne qui contient une fois et une seule chacune des arêtes du graphe.
  
  D'après le théorème d'Euler, un graphe connexe contient une chaîne eulérienne si et seulement s'il possède 0 ou 2 sommets de degré impair.
  
  Le degré de chacun des sommets est donné par le tableau ci-après :
  
  Sommet A B C D E F
  
  Degré 3 2 3 2 4 2
  
  Le graphe (G) possède deux sommets de degré impair : A et C.
  
  Il est donc possible de parcourir l'appartement en empruntant chacune des 8 portes une fois et une seule, par exemple en suivant le trajet : A-B-C-D-E-F-A-E-C.
  
  Théorème
  
  À retenir
  
  Une chaîne eulérienne est une chaîne qui contient une fois et une seule chacune des arêtes du graphe.
  
  Trouver un chemin qui emprunte chaque arête une fois et une seule revient à trouver une chaîne eulérienne.
  
  Un graphe connexe admet une chaîne eulérienne si et seulement s'il possède 0 ou 2 sommet(s) de degré impair.
2. Dans cette question, on recherche l'existence d'un cycle eulérien (un cycle est une chaîne fermée).
  
  Or, d'après le théorème d'Euler, un graphe connexe contient un cycle eulérien si et seulement s'il ne possède aucun sommet de degré impair.
  
  Ici, A et C sont de degré impair. Toute chaîne eulérienne aura pour extrémités A et C et ne sera donc pas un cycle.
  
  Par conséquent, il n'est pas possible de parcourir l'appartement en empruntant chaque porte une fois et une seule et en partant et en arrivant dans la même pièce.
  
  Théorème
  
  À retenir
  
  Un cycle eulérien est une chaîne fermée qui contient une fois et une seule chacune des arêtes du graphe.
  
  Trouver un chemin qui emprunte chaque arête une fois et une seule et dont les sommets de départ et d'arrivée sont identiques revient à trouver un cycle eulérien.
  
  Un graphe connexe admet un cycle eulérien si et seulement s'il ne possède aucun sommet de degré impair.
Numérotons les pièces A: 1, B: 2, C: 3, D: 4, E: 5, F: 6.
La matrice d'adjacence $ M $ associée au graphe précédent s'obtient en plaçant à la $ i $-ième ligne et à la $ j $-ième colonne :
- un « 1 » si les pièces numérotées $ i $ et $ j $ sont reliés par une arête ;
- un « 0 » sinon.
On obtient alors la matrice :

$ M = \begin{pmatrix} 0 &1 &0 &0 &1 &1 \\ 1 &0 &1 &0 &0 &0 \\ 0 &1 &0 &1 &1 &0 \\ 0 &0 &1 &0 &1 &0 \\ 1 &0 &1 &1 &0 &1\\ 1 &0 &0 &0 &1 &0 \end{pmatrix} $
1. Le coefficient de $ M^3 $ situé à la $ i $-ième ligne et à la $ j $-ième colonne indique le nombre de chemins de trois arêtes menant du sommet numéro $ i $ au sommet numéro $ j $.
  
  Ici, le coefficient situé à la première ligne et à la quatrième colonne est 3. Il y a donc 3 chemins permettant d'aller de la pièce A à la pièce D en empruntant exactement trois portes.
  
  À l'aide du graphe, on trouve les chemins : A-B-C-D, A-E-C-D et A-F-E-D.
  
  Théorème
  
  À retenir
  
  Le coefficient de la matrice $ M^n $ situé à la $ i $-ième ligne et à la $ j $-ième colonne correspond au nombre de chemins de longueur $ n $ menant du sommet numéro $ i $ au sommet numéro $ j $.
2. La matrice $ M^3 $ comporte un unique coefficient nul situé en ligne 2 et en colonne 2. Cela signifie qu'il n'est pas possible de partir de la pièce B pour revenir à la pièce B en empruntant exactement 3 portes mais que, mis à part ce cas, il est toujours possible de joindre deux pièces en empruntant exactement 3 portes.
  
  Comme l'énoncé précise deux pièces différentes, il est effectivement toujours possible de joindre deux pièces différentes en empruntant exactement trois portes.
1. Considérons le sous-graphe constitué des sommets A, E et F. Chacun de ces trois sommets est relié aux deux autres, donc ce sous-graphe est complet. Le sous-graphe constitué de C, E et D est lui-aussi complet.
2. Il est possible de repeindre les pièces en respectant les consignes de l'énoncé et avec seulement trois couleurs.
  
  Le sous-graphe A, E et F étant complet, il faudra nécessairement trois couleurs différentes pour peindre ces trois pièces.
  Il en est de même pour les pièces C, E et D.
  
  En respectant ces contraintes, il est facile de trouver une solution au problème posé ; par exemple (mais il y a d'autres solutions ...) :
  
  Couleur 1 : E, B
  Couleur 2 : A, C
  Couleur 3 : F, D.

Graphes : Algorithme de Dijkstra

Une agence de tourisme propose la visite de certains monuments parisiens.

Chacun de ces monuments est désigné par une lettre comme suit :

E : Tour Eiffel
L : Musée du Louvre
M : Tour Montparnasse
N : Cathédrale Notre-Dame de Paris
S : Basilique du Sacré-Cœur de Montmartre
T : Arc de triomphe

Cette agence fait appel à une société de transport par autocar qui propose les liaisons suivantes (chacune de ces liaisons pouvant s'effectuer dans les deux sens de circulation) :

Expliquer pourquoi il est possible de trouver un trajet empruntant une fois et une seule chacune des dix liaisons indiquées sur le graphe.
Donner un exemple d'un tel trajet.
1. Donner la matrice d'adjacence $ M $ associée à ce graphe en classant les sommets par ordre alphabétique.
2. On donne :
  
  $ M^2 = \begin{pmatrix} 4 &2 &1 &3 &2 &1 \\ 2 &4 &2 &2 &2 &2 \\ 1 &2 &3 &1 &3 &1 \\ 3 &2 &1 &3 &1 &1 \\ 2 &2 &3 &1 &4 &1\\ 1 &2 &1 &1 &1 &2 \end{pmatrix} $
  
  $ M^3 = \begin{pmatrix} 6 &10 &9 &5 &10 &6 \\ 10 &8 &8 &8 &10 &4 \\ 9 &8 &4 &8 &5 &4 \\ 5 &8 &8 &4 &9 &4 \\ 10 &10 &5 &9 &6 &6\\ 6 &4 &4 &4 &6 &2 \end{pmatrix} $
  
  Combien y a-t-il de trajets permettant de relier la cathédrale Notre-Dame de Paris et la tour Eiffel en utilisant au maximum trois liaisons.
  Justifier votre réponse.
On complète le graphe précédent en indiquant, sur chacune des branches, la durée du trajet, en minutes, entre deux monuments.

On souhaite aller de la tour Montparnasse à la Basilique du Sacré-Cœur de Montmartre.

En utilisant un algorithme, déterminer le trajet le plus rapide ainsi que la durée de ce trajet.

Corrigé

Un trajet empruntant une fois et une seule chacune des liaisons d'un graphe correspond à une chaîne eulérienne.
Un graphe admet une telle chaîne si et seulement s'il est connexe et possède exactement 0 ou 2 sommets de degré impair.

Le graphe est connexe car il existe toujours un chemin entre deux monuments quelconques.
D'après le graphe, les degrés des sommets sont :
- E (Tour Eiffel) : 4
- L (Musée du Louvre) : 4
- M (Tour Montparnasse) : 3
- N (Notre-Dame) : 3
- S (Sacré-Cœur) : 4
- T (Arc de triomphe) : 2
Seuls les sommets M (Tour Montparnasse) et N (Notre-Dame) ont un degré impair.
Le souhait d'emprunter chaque liaison une seule fois est donc réalisable.

Un exemple de trajet possible est : M - L - E - T - S - E - M - N - L - S - N.
1. La matrice d'adjacence $ M $ associée au graphe, avec les sommets classés par ordre alphabétique (E, L, M, N, S, T), est :
  
  $ M = \begin{pmatrix} 0 & 1 & 1 & 0 & 1 & 1 \\ 1 & 0 & 1 & 1 & 1 & 0 \\ 1 & 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 0 & 1 & 0 \end{pmatrix} $
2. Le nombre de trajets de longueur $ k $ reliant deux sommets est donné par le coefficient correspondant dans la matrice $ M^k $.
  Ici, on cherche le nombre de trajets entre la cathédrale Notre-Dame (N) et la tour Eiffel (E) en utilisant au maximum trois liaisons (donc des trajets de longueur 1, 2 ou 3).
  Le sommet N correspond à la 4ème ligne et le sommet E à la 1ère colonne.
  - Nombre de trajets de longueur 1 : $ M_{4,1} = 0 $
  - Nombre de trajets de longueur 2 : $ (M^2)_{4,1} = 3 $
  - Nombre de trajets de longueur 3 : $ (M^3)_{4,1} = 5 $
  Le nombre total de trajets est donc : $ 0 + 3 + 5 = 8 $.
  Il y a 8 trajets reliant ces deux monuments en trois liaisons maximum.

Pour déterminer le trajet le plus rapide entre la tour Montparnasse (M) et la Basilique du Sacré-Cœur (S), on utilise l'algorithme de Dijkstra.

Sommets	E	L	M	N	S	T	Choix
Initialisation	$ \infty $	$ \infty $	$ 0 $	$ \infty $	$ \infty $	$ \infty $	M (0)
Étape 1	$ 10_M $	$ 7_M $		$ 4_M $	$ \infty $	$ \infty $	N (4)
Étape 2	$ 10_M $	$ 6_N $			$ 12_N $	$ \infty $	L (6)
Étape 3	$ 10_M $				$ 11_L $	$ \infty $	E (10)
Étape 4					$ 11_L $	$ 14_E $	S (11)

En remontant l'algorithme à partir du sommet S :

S vient de L (distance 11)
L vient de N (distance 6)
N vient de M (distance 4)

Le trajet le plus rapide est M - N - L - S, c'est à dire Tour Montparnasse - Cathédrale Notre-Dame - Musée du Louvre - Basilique du Sacré-Cœur.

La durée de ce trajet est de 11 minutes.

Graphes Trajet minimal – Bac ES Pondichéry 2009

Une agence de voyages organise différentes excursions dans une région du monde et propose la visite de sites incontournables, nommés A, B, C, D, E et F.

Ces excursions sont résumées sur le graphe ci-dessous dont les sommets désignent les sites, les arêtes représentent les routes pouvant être empruntées pour relier deux sites et le poids des arêtes désigne le temps de transport (en heures) entre chaque site.

Graphe pondéré des excursions entre sites A, B, C, D, E, F

Justifier que ce graphe est connexe.
Un touriste désire aller du site A au site F en limitant au maximum les temps de transport.
1. En utilisant un algorithme, déterminer la plus courte chaîne reliant le sommet A au sommet F.
2. Déduire le temps de transport minimal pour aller du site A au site F.
Un touriste désirant apprécier un maximum de paysages souhaite suivre un parcours empruntant toutes les routes proposées une et une seule fois.

Si ce parcours existe, le décrire sans justifier; dans le cas contraire justifier qu'un tel parcours n'existe pas.

Corrigé

Deux sommets quelconques de ce graphe peuvent être reliés par une chaîne donc le graphe est connexe.

On utilise l'algorithme de Dijkstra :

A	B	C	D	E	F	Trajet
0	7(A)	$ \infty $	15(A)	$ \infty $	$ \infty $	AB
		19(B)	15(A)	11(B)	23(B)	ABE
		19(B)	13(E)		23(B)	ABED
		18(D)			23(B)	ABEDC
					21(C)	ABEDCF

La plus courte chaîne reliant le sommet A au sommet F est ABEDCF

Le temps de transport minimal pour aller du site A au site F est de 21 heures d'après le tableau précédent.

D'après le théorème d'Euler, il est possible d'emprunter toutes les routes une et une seule fois si le nombre de sommets de degré impair est égal à 0 ou à 2 . Ici, le graphe possède 4 sommets de degré impair : C, D, E, F. Un tel parcours n'existe donc pas.

Graphe – Trajet minimal – Bac ES Amérique du Nord 2009

Un groupe d'amis organise une randonnée dans les Alpes.

On a représenté par le graphe ci-dessous les sommets B, C, D, F, T, N par lesquels ils peuvent choisir de passer. Une arête entre deux sommets coïncide avec l'existence d'un chemin entre les deux sommets.

1. Recopier et compléter le tableau suivant :
  
  Sommets B C D F N T
  
  Degré des sommets du graphe
2. Justifier que le graphe est connexe.
Le groupe souhaite passer par les six sommets en passant une fois et une seule par chaque chemin.

Démontrer que leur souhait est réalisable. Donner un exemple de trajet possible.
Le groupe souhaite associer chaque sommet à une couleur de sorte que les sommets reliés par un chemin n'ont pas la même couleur. On note $ n $ le nombre chromatique du graphe.
1. Montrer que $ 4 \leqslant n \leqslant 6 $.
2. Proposer un coloriage du graphe permettant de déterminer son nombre chromatique.
Le groupe se trouve au sommet B et souhaite se rendre au sommet N. Les distances en kilomètres entre chaque sommet ont été ajoutées sur le graphe.

Indiquer une chaîne qui minimise la distance du trajet. Justifier la réponse.

Corrigé

1. Tableau des degrés des sommets :
  
  Sommets B C D F N T
  
  Degré 2 4 4 5 3 4
2. Le graphe est connexe car il existe toujours un chemin reliant deux sommets quelconques.
  Par exemple, la chaîne B-C-D-N-T-F contient tous les sommets du graphe.
Pour qu'un groupe puisse parcourir chaque chemin une fois et une seule (chaîne eulérienne), il faut que le nombre de sommets de degré impair soit égal à 0 ou 2.
Ici, seuls les sommets F (degré 5) et N (degré 3) ont des degrés impairs.
Le souhait est donc réalisable.
Un exemple de trajet possible est : F - B - C - F - D - C - T - F - N - T - D - N.
1. Le plus haut degré du graphe est $ \Delta = 5 $ (sommet F), donc le nombre chromatique $ n $ vérifie $ n \leqslant \Delta + 1 = 6 $.
  De plus, les sommets {C, D, F, T} forment un sous-graphe complet (chaque sommet est relié aux trois autres), donc $ n \geqslant 4 $.
  On en déduit :
  
  $ 4 \leqslant n \leqslant 6 $
2. On peut proposer le coloriage suivant avec 4 couleurs :
  - Couleur 1 : F
  - Couleur 2 : C et N
  - Couleur 3 : B et T
  - Couleur 4 : D
  Puisqu'on a réussi à colorier le graphe avec 4 couleurs et que $ n \geqslant 4 $, le nombre chromatique du graphe est $ n = 4 $.

Pour déterminer la chaîne qui minimise la distance entre B et N, on utilise l'algorithme de Dijkstra.

Sommets	B	C	D	F	N	T	Sommet choisi
Initialisation	$ 0 $	$ \infty $	$ \infty $	$ \infty $	$ \infty $	$ \infty $	B (0)
Étape 1		$ 12_B $	$ \infty $	$ 15_B $	$ \infty $	$ \infty $	C (12)
Étape 2			$ 14_C $	$ 15_B $	$ \infty $	$ 17_C $	D (14)
Étape 3				$ 15_B $	$ 26_D $	$ 17_C $	F (15)
Étape 4					$ 26_D $	$ 17_C $	T (17)
Étape 5					$ 24_T $		N (24)

En remontant l'algorithme à partir de N :

N vient de T (distance 24)
T vient de C (distance 17)
C vient de B (distance 12)

La chaîne qui minimise la distance entre B et N est : B - C - T - N.
La distance minimale est de 24 km.

Graphes – Trajet minimal – Bac ES Polynésie française 2008

Une grande ville a mis en place un système de location de bicyclettes en libre service.

Un abonné peut ainsi louer une bicyclette dans une station puis la déposer dans n'importe quelle station de son choix.

La ville compte sept stations de location nommées A, B, C, D, E, F et G.

Les stations sont reliées entre elles par une piste cyclable et les temps de parcours en minutes sont indiqués sur le graphe ci-dessous.

Philippe, cycliste très prudent, décide de visiter cette ville en n'empruntant que des pistes cyclables.
1. A-t-il la possibilité d'effectuer un parcours empruntant une fois et une seule toutes les pistes cyclables ? Justifier la réponse.
2. A la fin de ce parcours, pourra-t-il rendre sa bicyclette dans la station de départ ? Justifier la réponse.
On appelle M la matrice associée à ce graphe. On donne deux matrices N et T :

$ N=\begin{pmatrix}4 & 9 & 8 & 5 & 5 & 9 & 2 \\ 9 & 6 & 10 & 7 & 10 & 6 & 4 \\ 8 & 10 & 8 & 5 & 10 & 9 & 4 \\ 5 & 7 & 5 & 2 & 8 & 4 & 5 \\ 5 & 10 & 10 & 8 & 6 & 11 & 2 \\ 9 & 6 & 9 & 4 & 11 & 4 & 6 \\ 2 & 4 & 4 & 5 & 2 & 6 & 0 \end{pmatrix} $

$ T=\begin{pmatrix} 4 & 9 & 8 & 4 & 5 & 9 & 1 \\ 9 & 6 & 10 & 6 & 10 & 6 & 4 \\ 8 & 10 & 8 & 4 & 10 & 9 & 4 \\ 5 & 7 & 5 & 2 & 8 & 4 & 5 \\ 5 & 8 & 10 & 8 & 6 & 11 & 0 \\ 9 & 6 & 9 & 4 & 11 & 4 & 6 \\ 1 & 4 & 4 & 5 & 0 & 6 & 0 \end{pmatrix} $
1. Une des deux matrices N ou T est la matrice M³. Sans calculs, indiquer quelle est la matrice M³ en justifiant la réponse.
2. Philippe a loué une bicyclette à la station F et l'a rendue à la station E. Au cours de son déplacement, il est passé exactement deux fois devant une station. Combien de trajets différents a-t-il pu suivre ? Expliquer.
Le lendemain, il envisage de rejoindre le plus rapidement possible la station $ G $ en partant de la station A.
À l'aide d'un algorithme, déterminer un tel parcours et donner alors le temps nécessaire pour l'effectuer.

Corrigé

1. Pour déterminer s'il est possible d'effectuer un tel parcours (chaîne eulérienne), on calcule le degré de chaque sommet :
  - A : 3 (relié à B, C, F)
  - B : 4 (relié à A, C, D, E)
  - C : 4 (relié à A, B, E, F)
  - D : 3 (relié à B, E, G)
  - E : 4 (relié à B, C, D, F)
  - F : 4 (relié à A, C, E, G)
  - G : 2 (relié à D, F)
  Le graphe possède exactement 2 sommets de degré impair (A et D).
  Or, d'après le théorème d'Euler, un graphe admet une chaîne eulérienne si et seulement si le nombre de sommets de degré impair est égal à 0 ou 2.
  Philippe a donc la possibilité d'effectuer un tel parcours (en commençant par A et en finissant par D, ou inversement).
2. Un parcours revenant à la station de départ en empruntant chaque piste une seule fois correspond à un cycle eulérien.
  L'existence d'un cycle eulérien nécessite que tous les sommets soient de degré pair.
  Comme A et D sont de degré impair, il ne pourra pas revenir à son point de départ par un tel parcours.

La matrice $ M^3 $ donne le nombre de chemins de longueur 3 entre deux sommets.
Considérons le nombre de chemins de longueur 3 reliant le sommet G (7ème ligne/colonne) à lui-même.
Un chemin de longueur 3 de G à G est un cycle de longueur 3 passant par G. Or G n'est relié qu'à D et F, et il n'y a pas d'arête directe entre D et F. Il n'existe donc aucun triangle (cycle de longueur 3) passant par G.
On doit donc avoir $ (M^3)_{7,7} = 0 $.
C'est le cas pour les deux matrices N et T.

Regardons alors le nombre de chemins de longueur 3 entre A (sommet 1) et G (sommet 7).
Les chemins de longueur 3 sont de la forme A-X-Y-G.
Comme G est relié à D et F, Y doit être D ou F.
- Si Y = D : les voisins de D sont B, E, G. Donc X peut être B ou E. Or A est relié à B ($ A-B-D-G $) mais A n'est pas relié à E.
- Si Y = F : les voisins de F sont A, C, E, G. Donc X peut être A, C ou E. Or A est relié à C ($ A-C-F-G $) mais A n'est pas relié à E.
Il y a donc 2 chemins de longueur 3 entre A et G. La matrice $ M^3 $ doit avoir le coefficient 2 à la ligne 1, colonne 7.
Il s'agit donc de la matrice N.
Philippe est passé exactement deux fois devant une station entre F et E. Son trajet est donc composé de 3 liaisons (longueur 3).
Le nombre de tels trajets est donné par le coefficient de la 6ème ligne (F) et 5ème colonne (E) de la matrice $ M^3 $, soit $ N_{6,5} $.
D'après la matrice N, il y a 11 trajets différents.

3. Pour trouver le trajet le plus rapide de A vers G, on utilise l'algorithme de Dijkstra.

Sommets	A	B	C	D	E	F	G	Choix
Initialisation	0	$ \infty $	$ \infty $	$ \infty $	$ \infty $	$ \infty $	$ \infty $	A (0)
Étape 1		$ 7_A $	$ 11_A $	$ \infty $	$ \infty $	$ 13_A $	$ \infty $	B (7)
Étape 2			$ 11_A $	$ 23_B $	$ 21_B $	$ 13_A $	$ \infty $	C (11)
Étape 3				$ 23_B $	$ 20_C $	$ 13_A $	$ \infty $	F (13)
Étape 4				$ 23_B $	$ 20_C $		$ 31_F $	E (20)
Étape 5				$ 23_B $			$ 31_F $	D (23)
Étape 6							$ 28_D $	G (28)

Le trajet le plus court est donc A - B - D - G.
Le temps nécessaire pour l'effectuer est de 28 minutes.
[/list]

Graphes Algorithme de Dijkstra – Bac ES Métropole 2009

Le graphe ci-dessous représente le plan d'une ville.

Le sommet A désigne l'emplacement des services techniques.

Les sommets B, C, D, E, F et G désignent les emplacements de jardins publics. Une arête représente l'avenue reliant deux emplacements et est pondérée par le nombre de feux tricolores situés sur le trajet.

Graphe pondéré d'un plan de ville — algorithme de Dijkstra

Les parties I et II sont indépendantes.

Partie I

On s'intéresse au graphe non pondéré.

Répondre sans justification aux quatre questions suivantes :
1. Ce graphe est-il connexe ?
2. Ce graphe est-il complet ?
3. Ce graphe admet-il une chaîne eulérienne ?
4. Ce graphe admet-il un cycle eulérien ?
Déterminer, en justifiant, le nombre chromatique de ce graphe.

Partie II

On s'intéresse au graphe pondéré.

Proposer un trajet comportant un minimum de feux tricolores reliant A à G.

La réponse sera justifiée par un algorithme.

Corrigé

Partie 1

1. Le graphe est connexe car pour toute paire de sommets, il existe une chaîne reliant ces sommets.
2. Le graphe n'est pas complet car les points A et D (par exemple) ne sont pas relié par une arête.
3. D'après le théorème d'Euler, le graphe admet une chaîne eulérienne. En effet, il n'existe que deux sommets de degré impair(C et D)
4. D'après le théorème d'Euler, le graphe n'admet pas de cycle eulérien. Il faudrait pour cela qu'il n'existe aucun sommet de degré impair
BCDE forme un sous-graphe complet. Le nombre chromatique du graphe est donc supérieur ou égal à 4.

On peut colorier le graphe avec 4 couleurs de la façon suivante (par exemple) :

rouge: A, D
bleu: B, F
vert: C, G
jaune: E

Le nombre chromatique du graphe est donc 4.

Partie 2

On utilise l'algorithme de Dijkstra :

A	B	C	D	E	F	G
0	2 (A)	1 (A)	$ \infty $	$ \infty $	$ \infty $	$ \infty $
	2 (A)		5 (C)	4 (C)	6 (C)	$ \infty $
			3 (B)	4 (C)	6 (C)	$ \infty $
				4 (C)	6 (C)	8 (D)
					5 (E)	8 (D)
						7 (F)

Le trajet ACEFG comporte le nombre minimum de 7 feux.

Sommet	A	B	C	D	E	F
Degré	2	5	2	4	4	3

Sommet	E	L	M	N	S	T
Degré	4	4	3	3	4	2

Sommet	A	B	C	D	E	F
Degré	3	2	3	2	4	2

Sommets	B	C	D	F	N	T
Degré	2	4	4	5	3	4

Vrai/Faux : Chaînes et cycles dans un graphe

QCM : Chaînes et cycles eulériens

Graphes – Bac blanc ES/L Sujet 3 – Maths-cours 2018 (spé)

Graphes – Bac blanc ES Sujet 2 – Maths-cours 2018 (spé)

Graphes – Bac blanc ES Sujet 1 – Maths-cours 2018 (spé)

Théorème

Théorème

Théorème

Graphes : Algorithme de Dijkstra

Graphes Trajet minimal – Bac ES Pondichéry 2009

Graphe – Trajet minimal – Bac ES Amérique du Nord 2009

Graphes – Trajet minimal – Bac ES Polynésie française 2008

Graphes Algorithme de Dijkstra – Bac ES Métropole 2009

Partie 1

Partie 2