GR-EThéorie des graphes

Graphe orienté : tableau $d^+/d^-$ , chaîne orientée eulérienne, arc à ajouter, matrice non symétrique et chaînes orientées de longueur $k$

Idée directrice

Dans un graphe orienté, chaque arc a un sens : on ne parle plus du degré d'un sommet mais de son degré sortant $d^+$ et de son degré entrant $d^-$ . Le critère d'Euler se lit sur la différence $d^+-d^-$ : nulle en chaque sommet, le graphe (connexe) admet un cycle orienté eulérien ; nulle partout sauf en un sommet où elle vaut $1$ (le départ) et en un sommet où elle vaut $-1$ (l'arrivée), il admet une chaîne orientée eulérienne, et l'arc à ajouter pour la refermer va de l'arrivée vers le départ. La matrice associée n'est plus symétrique, et ses puissances comptent les chaînes orientées dans le bon sens : de la ligne vers la colonne.

Ce qui aide à reconnaître la démarche

« Recopier et compléter le tableau suivant où $d^+$ et $d^-$ représentent le nombre d'arcs sortants et entrants » ; « justifier que le graphe $(G)$ n'admet pas de cycle orienté eulérien » ; « montrer que $(G)$ admet une chaîne orientée eulérienne puis donner un exemple » ; « quel arc doit-on ajouter au graphe $(G)$ pour en avoir un graphe orienté eulérien de même ordre ? » ; « combien y a-t-il de chaînes orientées de longueur $7$ allant de $E$ à $C$ ? Citer ces chaînes »

Besoin d’un point de départ ? Voir la méthode

Tableau $d^+/d^-$ : $d^+$ est la somme de la ligne du sommet dans $M$ , $d^-$ la somme de sa colonne ; contrôle : $\sum d^+=\sum d^-=$ nombre d'arcs.
Cycle orienté eulérien : graphe connexe et $d^+=d^-$ en chaque sommet. Chaîne orientée eulérienne : graphe connexe, $d^+=d^-$ sauf au départ ( $d^+-d^-=1$ ) et à l'arrivée ( $d^+-d^-=-1$ ).
Arc à ajouter pour obtenir un graphe orienté eulérien : de l'arrivée de la chaîne eulérienne vers son départ, à condition qu'il n'existe pas déjà.
$M$ : ligne = sommet de départ, colonne = sommet d'arrivée ; elle n'est pas symétrique dès qu'un arc n'a pas d'arc retour.
$(M^k)_{ij}$ compte les chaînes orientées de longueur $k$ de $i$ vers $j$ ; « arrivant en $j$ » : somme de la colonne $j$ ; « issues de $i$ » : somme de la ligne $i$ . Si seules $M^p$ et $M^q$ sont données, $(M^{p+q})_{ij}$ est le produit de la ligne $i$ de $M^p$ par la colonne $j$ de $M^q$ . Quand on cite les chaînes, leur nombre doit égaler le coefficient.

Les pièges à vérifier dans ta démarche

Inverser $d^+$ et $d^-$ , c'est-à-dire lire la colonne au lieu de la ligne ; appliquer à un graphe orienté le critère des graphes non orientés (nombre de sommets de degré impair) ; faire partir la chaîne eulérienne du mauvais sommet — elle part du sommet où $d^+-d^-=1$ ; proposer l'arc à ajouter dans le mauvais sens, ou un arc qui existe déjà ; multiplier la colonne $E$ de $M^3$ par la ligne $C$ de $M^4$ , c'est-à-dire chercher $(M^7)_{35}$ au lieu de $(M^7)_{53}$ : dans un graphe orienté, le nombre de chaînes de $C$ vers $E$ n'est pas celui de $E$ vers $C$ .

Sujet principal

Exercice 2 — graphe orienté (5 points), dans l'esprit des sessions Économie et Gestion 2017–2026

3 questionsFigure fournieCorrigé masqué

On considère le graphe orienté $(G)$ ci-dessous, de sommets $A$ , $B$ , $C$ , $D$ et $E$ .

Tableau à recopier et compléter (question 1.a), où $d^+$ et $d^-$ désignent respectivement le nombre d'arcs sortants et le nombre d'arcs entrants :

\begin{array}{c|ccccc}\text{Sommet}&A&B&C&D&E\\ \hline d^+&\ldots&\ldots&\ldots&\ldots&\ldots\\d^-&\ldots&\ldots&\ldots&\ldots&\ldots\end{array}

Pour la question 3, on donne les matrices suivantes, où $M$ est la matrice associée à $(G)$ (sommets rangés dans l'ordre alphabétique) :

M^3=\begin{pmatrix}2&1&0&1&1\\2&1&0&0&0\\0&2&3&0&0\\0&0&1&1&1\\0&0&1&2&2\end{pmatrix}

M^4=\begin{pmatrix}2&3&3&0&0\\0&2&3&0&0\\0&0&2&3&3\\2&1&0&1&1\\4&2&0&1&1\end{pmatrix}

1. Recopier et compléter le tableau ci-dessus.
2. Justifier que le graphe $(G)$ n'admet pas de cycle orienté eulérien.
3. Montrer que $(G)$ admet une chaîne orientée eulérienne, puis en donner un exemple.
4. Quel arc doit-on ajouter au graphe $(G)$ pour obtenir un graphe orienté eulérien de même ordre ? Donner alors un cycle orienté eulérien.
1. Donner la matrice $M$ associée au graphe $(G)$ , les sommets étant rangés dans l'ordre alphabétique.
2. Justifier, sans calcul, que la matrice $M$ n'est pas symétrique.
1. Combien y a-t-il de chaînes orientées de longueur $3$ arrivant au sommet $B$ ? Les citer.
2. Combien y a-t-il de chaînes orientées de longueur $7$ allant de $E$ à $C$ ? Citer ces chaînes.

Voir la correction commentéeAprès avoir posé votre démarche

1.a Idée : $d^+$ compte les arcs qui partent du sommet, $d^-$ ceux qui y arrivent. On lit sur la figure les huit arcs $A\to B$ , $A\to C$ , $B\to C$ , $C\to D$ , $C\to E$ , $D\to A$ , $E\to A$ et $E\to B$ :

\begin{array}{c|ccccc}\text{Sommet}&A&B&C&D&E\\ \hline d^+&2&1&2&1&2\\d^-&2&2&2&1&1\end{array}

Contrôle : $\sum d^+=\sum d^-=8$ , le nombre d'arcs (chaque arc part d'un sommet et arrive à un autre).

1.b Un cycle orienté eulérien impose $d^+=d^-$ en chaque sommet : on entre dans un sommet autant de fois qu'on en sort. Or $d^+(B)=1$ et $d^-(B)=2$ : $(G)$ n'admet pas de cycle orienté eulérien.

1.c Idée : un graphe orienté connexe admet une chaîne orientée eulérienne lorsque $d^+=d^-$ en tout sommet sauf en deux : le départ, où $d^+-d^-=1$ , et l'arrivée, où $d^+-d^-=-1$ . La chaîne $E\to A\to B\to C\to D$ passe par les cinq sommets : $(G)$ est connexe. La différence $d^+-d^-$ vaut $0$ en $A$ , $C$ et $D$ , $1$ en $E$ et $-1$ en $B$ : $(G)$ admet une chaîne orientée eulérienne de $E$ à $B$ .

Exemple : $E\to A\to C\to D\to A\to B\to C\to E\to B$ emprunte chacun des huit arcs une fois et une seule.

1.d Idée : l'arc ajouté doit donner un arc sortant de plus à $B$ et un arc entrant de plus à $E$ : il va de l'arrivée $B$ vers le départ $E$ . L'arc $B\to E$ n'existe pas dans $(G)$ . Après l'avoir ajouté, $d^+(B)=d^-(B)=2$ et $d^+(E)=d^-(E)=2$ , les autres sommets sont inchangés et le graphe reste connexe : on obtient un graphe orienté eulérien d'ordre $5$ . Il suffit de prolonger la chaîne précédente par le nouvel arc : $E\to A\to C\to D\to A\to B\to C\to E\to B\to E$ est un cycle orienté eulérien.

2.a Idée : $m_{ij}=1$ s'il existe un arc du $i$ -ème sommet vers le $j$ -ème, $0$ sinon ; la ligne est le sommet de départ.

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

On retrouve $d^+$ en sommant chaque ligne et $d^-$ en sommant chaque colonne.

2.b $m_{12}=1$ car l'arc $A\to B$ existe, mais $m_{21}=0$ car il n'y a pas d'arc $B\to A$ : $m_{12}\neq m_{21}$ , donc $M$ n'est pas symétrique. C'est le cas dès qu'un arc n'a pas d'arc retour.

3.a Idée : $(M^3)_{ij}$ compte les chaînes orientées de longueur $3$ de $i$ vers $j$ ; « arriver en $B$ » en partant de n'importe quel sommet, c'est sommer la colonne de $B$ . La deuxième colonne de $M^3$ est $(1,1,2,0,0)$ : il y a $1+1+2+0+0=\boxed{4}$ chaînes orientées de longueur $3$ arrivant en $B$ .

Ce sont $A\to C\to E\to B$ , $B\to C\to E\to B$ , $C\to D\to A\to B$ , $C\to E\to A\to B$ : une issue de $A$ , une de $B$ , deux de $C$ , comme l'indique la colonne.

3.b Idée : $M^7=M^3\times M^4$ , donc le coefficient ligne $E$ (cinquième), colonne $C$ (troisième) de $M^7$ est le produit de la ligne $E$ de $M^3$ par la colonne $C$ de $M^4$ .

(M^7)_{53}=0\times3+0\times3+1\times2

\qquad+2\times0+2\times0=\boxed{2}

Idée : pour les citer, partir d'une chaîne sans répétition de $E$ à $C$ et y insérer des circuits. Ces chaînes sont $E\to A\to C$ et $E\to B\to C$ , de longueur $2$ , et $E\to A\to B\to C$ , de longueur $3$ . Les circuits de $(G)$ ont pour longueur $3$ (par exemple $A\to C\to D\to A$ ) ou $4$ ( $A\to B\to C\to D\to A$ et $A\to B\to C\to E\to A$ ) : on ne peut pas allonger une chaîne de longueur $2$ de $5$ arcs, mais on allonge $E\to A\to B\to C$ d'un circuit de longueur $4$ . On trouve bien deux chaînes :

$E\to A\to B\to C\to D\to A\to B\to C$ et $E\to A\to B\to C\to E\to A\to B\to C$ .

Changer d’énoncé, garder le raisonnement

Choisis un seul transfert après le sujet principal. Qu’est-ce qui change ? Quel résultat ou quelle méthode peux-tu réutiliser ? Les autres exercices restent disponibles pour une prochaine séance.

Variantes rencontrées : graphe donné seulement par sa matrice, à représenter, avec le tableau $d^+/d^-$ à compléter (contrôle 2017) ; figure à choisir parmi trois représentations, chaînes de longueur 4 et arc à ajouter pour obtenir un graphe orienté eulérien (principale 2023) ; tableau $d^+/d^-$ , chaîne orientée eulérienne, chaînes de longueur 3 arrivant en un sommet et de longueur 7 à citer (principale 2024) ; graphe orienté donné avec ses matrices, ordre, matrice et chaînes de longueur 3 en QCM (principale 2025) ; graphe orienté à quatre sommets, $M^2$ donnée et chaînes de longueur 4 lues sur $M^4=(M^2)^2$ (contrôle 2026) ; graphe orienté $(G')$ obtenu d'un graphe non orienté par un plan de circulation (principales 2021 et 2022).

Exercices d'entraînement — une nuance à la fois

1 Drill GR-E.1 — graphe orienté donné par sa matrice : tableau

d^+/d^-

, chaîne orientée eulérienne, représentation

Entraînement 01 / 04

Drill GR-E.1 — graphe orienté donné par sa matrice : tableau $d^+/d^-$ , chaîne orientée eulérienne, représentation

2 questionsCorrigé masqué

La matrice $M$ ci-dessous est associée à un graphe orienté $G$ de sommets $A$ , $B$ , $C$ , $D$ et $E$ pris dans cet ordre. On donne aussi $M^2$ .

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

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

1. Dresser le tableau des degrés sortants $d^+$ et des degrés entrants $d^-$ des cinq sommets.
2. Le graphe $G$ admet-il un cycle orienté eulérien ? Expliquer.
3. Vérifier que $G$ admet une chaîne orientée eulérienne.
4. Représenter le graphe $G$ et donner un exemple de chaîne orientée eulérienne.
Combien y a-t-il de chaînes orientées de longueur $2$ reliant le sommet $B$ au sommet $E$ ? Les citer.

Voir la correction commentéeAprès avoir posé votre démarche

1.a Idée : sans figure, $d^+$ est la somme de la ligne du sommet et $d^-$ la somme de sa colonne.

\begin{array}{c|ccccc}\text{Sommet}&A&B&C&D&E\\ \hline d^+&2&2&2&1&2\\d^-&2&2&1&2&2\end{array}

Les deux lignes totalisent $9$ , le nombre de coefficients égaux à $1$ , c'est-à-dire le nombre d'arcs.

1.b Non : un cycle orienté eulérien exigerait $d^+=d^-$ en chaque sommet, or $d^+(C)=2\neq d^-(C)=1$ .

1.c La chaîne $C\to D\to B\to A\to E$ passe par tous les sommets : $G$ est connexe. $d^+-d^-$ est nul en $A$ , $B$ et $E$ , vaut $1$ en $C$ et $-1$ en $D$ : $G$ admet une chaîne orientée eulérienne, qui part de $C$ et arrive en $D$ .

1.d Idée : chaque coefficient $m_{ij}=1$ est un arc du $i$ -ème vers le $j$ -ème sommet. Les arcs sont $A\to D$ , $A\to E$ , $B\to A$ , $B\to C$ , $C\to D$ , $C\to E$ , $D\to B$ , $E\to A$ et $E\to B$ ; comme $m_{15}=m_{51}=1$ , les arcs $A\to E$ et $E\to A$ sont dessinés tous les deux.

Exemple de chaîne orientée eulérienne : $C\to D\to B\to A\to E\to B\to C\to E\to A\to D$ (neuf arcs, chacun une fois).

2. Idée : lire la ligne $B$ , colonne $E$ de $M^2$ . $(M^2)_{25}=\boxed{2}$ : ce sont $B\to A\to E$ et $B\to C\to E$ , car les arcs sortant de $B$ vont vers $A$ et $C$ , qui ont tous deux un arc vers $E$ .

2 Drill GR-E.2 — reconnaître la représentation d'un graphe orienté à partir de sa matrice

Entraînement 02 / 04

Drill GR-E.2 — reconnaître la représentation d'un graphe orienté à partir de sa matrice

2 questionsFigure fournieCorrigé masqué

La matrice $M$ ci-dessous est la matrice associée à un graphe connexe $(G)$ de sommets $A$ , $B$ , $C$ , $D$ et $E$ pris dans cet ordre.

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

On donne aussi :

M^4=\begin{pmatrix}3&0&2&1&2\\2&3&0&2&1\\1&2&2&0&3\\2&1&0&2&0\\0&2&1&0&2\end{pmatrix}

1. Justifier que le graphe $(G)$ est orienté.
2. Déterminer le nombre d'arcs du graphe $(G)$ .
3. Déterminer, en justifiant la réponse, laquelle des trois figures est une représentation du graphe $(G)$ .
1. Déterminer le nombre de chaînes orientées de longueur $4$ reliant $D$ à $A$ .
2. Citer ces chaînes.

Voir la correction commentéeAprès avoir posé votre démarche

1.a Idée : un graphe non orienté a une matrice symétrique. Ici $m_{24}=1$ mais $m_{42}=0$ : il y a un arc de $B$ vers $D$ et aucun de $D$ vers $B$ . $M$ n'est pas symétrique, donc $(G)$ est orienté.

1.b Chaque arc correspond à un coefficient égal à $1$ : la somme des coefficients de $M$ vaut $2+2+2+1+1=8$ , donc $(G)$ a $\boxed{8}$ arcs.

1.c Idée : éliminer les figures par un argument simple, puis vérifier la dernière arc par arc. La figure 1 n'a que $7$ arcs : il lui manque l'arc $C\to E$ ( $m_{35}=1$ ), elle est exclue. La figure 3 porte l'arc $D\to B$ , alors que $m_{42}=0$ : elle est exclue. Les huit arcs de la figure 2, $A\to C$ , $A\to E$ , $B\to A$ , $B\to D$ , $C\to B$ , $C\to E$ , $D\to A$ et $E\to B$ , sont exactement ceux que donnent les coefficients égaux à $1$ : la figure 2 représente $(G)$ .

2.a Le nombre cherché est le coefficient ligne $D$ (quatrième), colonne $A$ (première) de $M^4$ : $(M^4)_{41}=\boxed{2}$ .

2.b Idée : le seul arc qui sort de $D$ est $D\to A$ ; il reste un circuit de longueur $3$ de $A$ à $A$ . Depuis $A$ on va en $C$ ou en $E$ , puis en $B$ : c'est le seul sommet atteint en un arc depuis $C$ ou $E$ qui ramène en $A$ : les chaînes sont $D\to A\to C\to B\to A$ et $D\to A\to E\to B\to A$ .

3 Drill GR-E.3 — du graphe des rues au graphe orienté

(G')

d'un plan de circulation

Entraînement 03 / 04

Drill GR-E.3 — du graphe des rues au graphe orienté $(G')$ d'un plan de circulation

2 questionsFigure fournieCorrigé masqué

Un quartier compte cinq places $A$ , $B$ , $C$ , $D$ et $E$ reliées par des rues. Le graphe $(G)$ ci-dessous, à gauche, modélise la situation : les sommets sont les places et les arêtes sont les rues.

1. Dresser le tableau des degrés des sommets de $(G)$ .
2. Un piéton peut-il parcourir toutes les rues du quartier en passant par chaque rue une fois et une seule ? Si oui, proposer un tel parcours.
La municipalité instaure un plan de circulation : certaines rues deviennent à sens unique, les autres restent à double sens. Le graphe orienté $(G')$ , à droite, modélise la nouvelle situation.
1. Quelles rues sont devenues à sens unique ? Donner la matrice $M$ associée au graphe $(G')$ , les sommets étant rangés dans l'ordre alphabétique.
2. On donne $M^3$ ci-dessous. Combien y a-t-il de chaînes orientées de longueur $3$ allant de $B$ à $D$ ? Les citer.

M^3=\begin{pmatrix}0&0&0&1&1\\1&0&2&2&2\\1&0&1&3&3\\1&1&2&1&0\\2&2&4&4&1\end{pmatrix}

Voir la correction commentéeAprès avoir posé votre démarche

1.a Idée : le degré d'un sommet est le nombre d'arêtes qui y aboutissent.

\begin{array}{c|ccccc}\text{Sommet}&A&B&C&D&E\\ \hline \text{Degré}&3&2&2&3&4\end{array}

La somme des degrés vaut $14=2\times7$ : chacune des sept rues est comptée deux fois.

1.b Idée : parcourir chaque rue une seule fois, c'est trouver une chaîne eulérienne. La chaîne $A-B-E-C-D$ passe par toutes les places : $(G)$ est connexe. Exactement deux sommets, $A$ et $D$ , sont de degré impair : $(G)$ admet une chaîne eulérienne d'extrémités $A$ et $D$ . Le piéton peut donc le faire, en partant de $A$ et en finissant en $D$ (ou l'inverse), par exemple $A-B-E-A-D-C-E-D$ .

2.a Sur $(G')$ , une rue à sens unique porte un seul arc et une rue à double sens en porte deux. Les rues devenues à sens unique sont $A\to D$ , $B\to A$ , $E\to A$ et $E\to D$ ; les rues $B-E$ , $C-E$ et $C-D$ restent à double sens.

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

Une rue à double sens donne deux coefficients symétriques égaux à $1$ , par exemple $m_{25}=m_{52}=1$ pour $B-E$ ; une rue à sens unique n'en donne qu'un, par exemple $m_{14}=1$ et $m_{41}=0$ .

2.b $(M^3)_{24}=\boxed{2}$ (ligne $B$ , colonne $D$ ). Idée : pour les citer, suivre les arcs sortants. De $B$ on va en $A$ ou en $E$ . Par $A$ , le seul arc est $A\to D$ puis $D\to C$ : on n'arrive pas en $D$ en trois arcs. Par $E$ : $B\to E\to A\to D$ et $B\to E\to C\to D$ ; ce sont les deux chaînes annoncées.

4 Drill GR-E.4 — QCM sur un graphe orienté donné par sa matrice : ordre, degré entrant, chaîne orientée eulérienne, chaînes de longueur

3

Entraînement 04 / 04

Drill GR-E.4 — QCM sur un graphe orienté donné par sa matrice : ordre, degré entrant, chaîne orientée eulérienne, chaînes de longueur $3$

5 questionsCorrigé masqué

Pour chaque question, une seule des trois réponses proposées est exacte. Recopier sur la copie le numéro de la question et la lettre correspondant à la réponse exacte. Aucune justification n'est demandée.

On considère un graphe orienté $(G)$ de sommets $A$ , $B$ , $C$ et $D$ (pris dans cet ordre). Sa matrice associée $M$ et la matrice $M^3$ sont :

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

M^3=\begin{pmatrix}3&1&1&1\\1&2&0&2\\1&0&2&1\\1&1&2&2\end{pmatrix}

L'ordre du graphe $(G)$ est égal à : a) $4$ ; b) $7$ ; c) $16$ .
Le degré entrant $d^-(C)$ du sommet $C$ est égal à : a) $1$ ; b) $2$ ; c) $3$ .
Le graphe $(G)$ : a) admet un cycle orienté eulérien ; b) admet une chaîne orientée eulérienne de $B$ à $C$ ; c) admet une chaîne orientée eulérienne de $C$ à $B$ .
Le nombre de chaînes orientées de longueur $3$ allant du sommet $A$ au sommet $C$ est égal à : a) $0$ ; b) $1$ ; c) $3$ .
Le nombre de chaînes orientées de longueur $3$ issues du sommet $D$ est égal à : a) $2$ ; b) $5$ ; c) $6$ .

Voir la correction commentéeAprès avoir posé votre démarche

1. a) L'ordre est le nombre de sommets, c'est-à-dire le nombre de lignes de $M$ : $4$ ( $7$ est le nombre d'arcs, $16$ le nombre de coefficients).

2. b) $d^-(C)$ est la somme de la troisième colonne de $M$ : $m_{23}+m_{43}=2$ (arcs $B\to C$ et $D\to C$ ).

3. b) Sommes des lignes : $d^+=(2,2,1,2)$ ; sommes des colonnes : $d^-=(2,1,2,2)$ . $d^+-d^-$ vaut $1$ en $B$ , $-1$ en $C$ et $0$ ailleurs, et le graphe est connexe : il y a une chaîne orientée eulérienne de $B$ à $C$ , par exemple $B\to C\to A\to B\to D\to A\to D\to C$ , et pas de cycle orienté eulérien.

4. b) $(M^3)_{13}=1$ : la seule chaîne est $A\to B\to D\to C$ .

5. c) « Issues de $D$ » : somme de la quatrième ligne de $M^3$ , $1+1+2+2=6$ .

Relier ce raisonnement au bac

Choisis une filière pour voir les sujets qui étayent ce scénario.

Tu écris. Tu continues.

Où veux-tu aller ?

Graphe orienté : tableau $d^+/d^-$ , chaîne orientée eulérienne, arc à ajouter, matrice non symétrique et chaînes orientées de longueur $k$

Exercice 2 — graphe orienté (5 points), dans l'esprit des sessions Économie et Gestion 2017–2026

Changer d’énoncé, garder le raisonnement

Exercices d'entraînement — une nuance à la fois

Drill GR-E.1 — graphe orienté donné par sa matrice : tableau $d^+/d^-$ , chaîne orientée eulérienne, représentation

Drill GR-E.2 — reconnaître la représentation d'un graphe orienté à partir de sa matrice

Drill GR-E.3 — du graphe des rues au graphe orienté $(G')$ d'un plan de circulation

Drill GR-E.4 — QCM sur un graphe orienté donné par sa matrice : ordre, degré entrant, chaîne orientée eulérienne, chaînes de longueur $3$

Relier ce raisonnement au bac

Graphe orienté : tableau d+/d−d^+/d^-d+/d−, chaîne orientée eulérienne, arc à ajouter, matrice non symétrique et chaînes orientées de longueur kkk

Changer d’énoncé, garder le raisonnement

Exercices d'entraînement — une nuance à la fois

Relier ce raisonnement au bac

Graphe orienté : tableau $d^+/d^-$ , chaîne orientée eulérienne, arc à ajouter, matrice non symétrique et chaînes orientées de longueur $k$