Math CST, secondaire 5 à Montréal • Graphes

Fiche de révision : La théorie des graphes

Cette fiche ne refait pas le cours sur les graphes : elle traite ce qui coûte réellement des points en évaluation de mathématique CST de cinquième secondaire. Le chapitre ne demande presque aucun calcul, et c'est précisément ce qui le rend traître : deux problèmes qui se ressemblent sur la figure se traitent par des méthodes opposées, et le mot qui les distingue est dans l'énoncé, pas dans le dessin.

Lisez-la avant de faire la série d'exercices du même chapitre, puis relisez le mémo la veille de l'évaluation.

Le fil du chapitre

Le graphe ne dit jamais ce qu'il faut faire : c'est l'énoncé qui le dit, en nommant ce qu'il faut parcourir, les ARÊTES ou les SOMMETS, et ce qu'il faut rendre minimal, la somme du réseau ou la longueur d'un seul trajet.

Ce chapitre fait partie de Mathématique CST, secondaire 5

L'essentiel

Les deux parcours, à ne jamais confondre

• EULÉRIEN, ce sont les ARÊTES : on passe une fois et une seule par chaque arête. Un sommet peut être revisité autant de fois qu'on veut.
• HAMILTONIEN, ce sont les SOMMETS : on passe une fois et une seule par chaque sommet. Des arêtes peuvent rester inutilisées.
• Une CHAÎNE est ouverte, elle finit ailleurs qu'elle n'a commencé ; un CYCLE revient au point de départ. Les quatre combinaisons existent.
• L'eulérien possède un critère automatique, celui des degrés. L'hamiltonien n'en a AUCUN : on cherche un parcours, ou on démontre qu'il est impossible en exhibant un sommet de coupure ou une impasse.

À gauche, tous les degrés sont pairs donc le cycle eulérien existe, mais

C

est un sommet de coupure : pas d'hamiltonien. À droite, les quatre degrés valent

3

: pas d'eulérien, et pourtant le cycle

PQRS

existe.

Écrire en début de réponse « il s'agit d'un problème eulérien, car l'énoncé demande de parcourir chaque rue » rapporte le point de justification, même quand la suite est fausse.

Le critère des degrés, la seule règle automatique du chapitre

• La somme des degrés vaut TOUJOURS le double du nombre d'arêtes, donc elle est toujours paire, et le nombre de sommets de degré impair est lui aussi toujours pair.
• Dans un graphe CONNEXE : aucun sommet impair donne un cycle eulérien ; exactement deux sommets impairs donnent une chaîne eulérienne, qui part de l'un et arrive à l'autre ; quatre sommets impairs ou plus ne donnent ni chaîne ni cycle.
• Le critère exige la connexité : un graphe en deux morceaux n'a aucun parcours eulérien, quels que soient ses degrés.
• Quand il y a quatre sommets impairs ou plus, on ne répond pas « impossible » et on s'arrête : on répète des arêtes, et la question devient « combien de kilomètres en plus au minimum ».

Les quatre optimisations, et ce que chacune rend minimal

• ARBRE DE VALEURS MINIMALES : rend minimale la SOMME de tout le réseau construit. Exactement $n-1$ arêtes, obtenues en prenant les arêtes par valeurs croissantes et en écartant celles qui fermeraient un cycle.
• CHAÎNE DE POIDS MINIMAL : rend minimal UN trajet entre deux sommets donnés, sur un réseau qui existe déjà. On avance de proche en proche en notant la meilleure valeur connue de chaque sommet.
• CHEMIN CRITIQUE : le plus LONG chemin d'un réseau orienté, et sa durée est la durée MINIMALE du projet. La marge d'une tâche est l'écart entre la durée du projet et celle du plus long chemin qui la contient.
• NOMBRE CHROMATIQUE : le plus petit nombre de couleurs tel que deux sommets reliés n'aient jamais la même. Un groupe de $k$ sommets tous reliés deux à deux en impose au moins $k$ , et un cycle de longueur impaire en impose $3$ .

Ces quatre problèmes se posent sur la MÊME figure : c'est la phrase de l'énoncé qui décide, jamais le dessin.

Les pièges qui coûtent des points

Les erreurs ci-dessous sont celles que je corrige le plus souvent en séance. Chacune coûte des points sur une copie, même quand le raisonnement est juste.

1. Traiter un problème de tournée comme un problème hamiltonien

toute la question, 4 points

Ce qu'il ne faut pas écrire

« Le camion doit passer dans toutes les rues, donc il doit visiter tous les sommets : c'est un problème hamiltonien. »

Ce qu'il faut écrire

« Le camion doit parcourir chaque RUE, donc chaque arête : c'est un problème eulérien, et j'applique le critère des degrés. »

Pourquoi : Les deux problèmes se posent sur la même figure et se résolvent par des méthodes sans rapport ; la seule chose qui les distingue est le mot de l'énoncé. Rues, câbles, ponts, canalisations : ce sont des arêtes. Villes, clients, machines, salles : ce sont des sommets.

2. Déduire l'hamiltonien de l'eulérien

2 points, et la démonstration entière

Ce qu'il ne faut pas écrire

« Tous les degrés sont pairs, donc il existe un cycle eulérien, donc il existe aussi un cycle hamiltonien. »

Ce qu'il faut écrire

« Tous les degrés sont pairs, donc il existe un cycle eulérien. Cela ne dit rien de l'hamiltonien : ici $C$ est un sommet de coupure, il faudrait y passer deux fois, donc aucun cycle hamiltonien n'existe. »

Pourquoi : Le critère des degrés ne parle que des arêtes. Aucun théorème du programme ne relie les deux notions, et la figure de l'essentiel donne un contre-exemple dans chaque sens.

3. Prendre la somme des degrés pour le nombre d'arêtes

1 point, et tous les totaux de longueur qui suivent

Ce qu'il ne faut pas écrire

« La somme des degrés vaut $14$ , le graphe a donc $14$ arêtes. »

Ce qu'il faut écrire

« La somme des degrés vaut $14$ , donc le graphe a $\dfrac{14}{2}=7$ arêtes, puisque chaque arête est comptée à ses deux extrémités. »

Pourquoi : L'erreur double toutes les distances calculées ensuite. La contre-vérification est immédiate : une somme de degrés IMPAIRE est impossible, elle signale toujours une erreur de comptage.

4. Chercher un cycle eulérien alors qu'il y a deux sommets impairs

2 points, et la question du retour au garage

Ce qu'il ne faut pas écrire

« Il y a deux sommets de degré impair, donc le camion peut partir du garage, tout parcourir et y revenir sans répétition. »

Ce qu'il faut écrire

« Il y a exactement deux sommets impairs, $S$ et $T$ : il existe une CHAÎNE eulérienne, qui part obligatoirement de $S$ pour arriver en $T$ . Un cycle est impossible, donc revenir au départ exige de répéter des arêtes. »

Pourquoi : La distinction chaîne ou cycle est la moitié de la réponse attendue, et c'est elle qui décide du point de départ imposé. Deux sommets impairs ne laissent aucun choix : on part de l'un des deux.

5. Répondre à un plus court trajet avec l'arbre de valeurs minimales

toute la question, 4 points

Ce qu'il ne faut pas écrire

« L'arbre de valeurs minimales relie tous les points au meilleur coût, donc le trajet le moins long de $A$ à $B$ se lit dessus : $4+5+7=16$ . »

Ce qu'il faut écrire

« L'arbre minimise la somme du réseau, pas un trajet. Le plus court chemin de $A$ à $B$ se cherche sur le graphe ENTIER : l'arête directe $AB$ vaut $12$ , donc le trajet minimal vaut $12$ , et non les $16$ lus sur l'arbre. »

Les traits pleins forment l'arbre de valeurs minimales, de coût

16

. L'arête

AB

, en pointillé, en est exclue et donne pourtant le trajet le plus court de

A

B

12

contre

16

Pourquoi : Ce sont deux problèmes différents et l'un ne résout jamais l'autre : l'arbre écarte volontiers une arête chère qui est pourtant le meilleur raccourci entre deux sommets précis.

6. Prendre le chemin critique pour le chemin le plus court

toute la question, et toutes les marges

Ce qu'il ne faut pas écrire

« On cherche la durée minimale du projet, donc le chemin critique est le chemin le plus court du réseau. »

Ce qu'il faut écrire

« Le chemin critique est le chemin le plus LONG du réseau orienté, car le projet n'est terminé que lorsque sa plus longue suite de tâches enchaînées l'est. Sa durée EST la durée minimale du projet. »

Pourquoi : Le mot « minimale » de l'énoncé pousse à chercher un minimum, alors que la durée minimale réalisable est imposée par le maximum. Une fois le chemin critique faux, toutes les marges le sont aussi.

7. Donner une coloration sans prouver qu'elle est minimale

2 points sur 4

Ce qu'il ne faut pas écrire

« J'ai colorié le graphe avec quatre couleurs, donc le nombre chromatique vaut $4$ . »

Ce qu'il faut écrire

« Cette coloration à $4$ couleurs montre que $4$ suffisent. De plus les sommets $M$ , $S_1$ et $S_2$ sont deux à deux reliés et le cycle extérieur est de longueur impaire, donc $3$ ne peuvent pas suffire : le nombre chromatique vaut exactement $4$ . »

Pourquoi : Un nombre chromatique se démontre en deux moitiés, « ce nombre suffit » et « un de moins ne suffirait pas ». La première moitié seule ne prouve qu'une majoration.

8. Retenir une arête bon marché qui ferme un cycle

2 points, et un arbre à $n$ arêtes au lieu de $n-1$

Ce qu'il ne faut pas écrire

« L'arête $AE$ ne coûte que $5$ , je la prends : c'est l'une des moins chères du réseau. »

Ce qu'il faut écrire

« $A$ et $E$ sont déjà reliés par $A$ , $F$ , $E$ : prendre $AE$ créerait un cycle, et un arbre n'en a pas. Je l'écarte malgré son coût, et je passe à l'arête suivante. »

Pourquoi : Le critère de rejet n'est jamais le coût, c'est la création d'un cycle. Le compte final le trahit aussitôt : six sommets doivent donner exactement cinq arêtes.

9. Prendre un croisement de traits pour un sommet

1 point, et le critère des degrés faussé

Ce qu'il ne faut pas écrire

« Les arêtes $BE$ et $AD$ se croisent au milieu, cela fait donc un septième sommet de degré $4$ . »

Ce qu'il faut écrire

« Un sommet est un point tracé sur la figure. Le croisement de $BE$ et $AD$ n'en porte pas : le graphe garde ses six sommets, et la somme des degrés vaut $16$ pour $8$ arêtes. »

Pourquoi : Un graphe n'a pas de forme : seules comptent les liaisons, et la même famille de liaisons peut se dessiner avec ou sans croisement. Un croisement est un accident de dessin, jamais une information.

Quelle méthode choisir

Quel problème l'énoncé pose-t-il ?

Le verbe de l'énoncé et l'objet qu'il faut parcourir ou rendre minimal

Si passer par chaque rue, chaque câble, chaque pont, chaque canalisation → problème EULÉRIEN : appliquer le critère des degrés

Exemple : une tournée de déneigement, une inspection de conduites

ce sont des arêtes, donc les sommets peuvent être revisités
Si passer par chaque ville, chaque client, chaque salle, chaque machine → problème HAMILTONIEN : chercher un parcours, ou prouver l'impossibilité par un sommet de coupure

Exemple : une tournée de livraison, un circuit touristique

aucun critère automatique : on exhibe un parcours ou un obstacle
Si relier tous les points au coût total le plus faible → ARBRE DE VALEURS MINIMALES par arêtes croissantes

Exemple : câbler six quartiers en fibre optique

le résultat compte toujours exactement $n-1$ arêtes
Si aller d'un point précis à un autre le plus vite ou le moins cher → CHAÎNE DE POIDS MINIMAL sur le graphe entier

Exemple : un technicien qui va du quartier $A$ au quartier $C$

surtout pas sur l'arbre minimal, qui répond à une autre question
Si durée minimale d'un projet, retard admissible d'une tâche → CHEMIN CRITIQUE : le plus long chemin du réseau orienté

Exemple : sept tâches de chantier, durée totale et marges

la marge d'une tâche vaut la durée du projet moins celle du plus long chemin qui la contient
Si nombre minimal de plages horaires, de fréquences, de couleurs, de salles → NOMBRE CHROMATIQUE du graphe des conflits

Exemple : placer six examens sans qu'un élève en ait deux en même temps

une arête signifie une INTERDICTION de partager, jamais une compatibilité

Si l'énoncé ne parle ni de parcours ni d'optimisation, il demande du vocabulaire : ordre, degrés, connexité, chaîne, cycle. Répondre avec les définitions et le contrôle de la somme des degrés.

Le graphe admet-il un parcours eulérien ?

Le nombre de sommets de degré IMPAIR, dans un graphe connexe

Les trois cas du critère, à la même échelle : le triangle n'a que des degrés pairs, le carré à diagonale a deux sommets de degré

3

, et le carré à deux impasses en a quatre de degré impair.

Si aucun sommet de degré impair → il existe un CYCLE eulérien : on part d'où on veut et on revient au départ

Exemple : les deux triangles du papillon, degrés $2$ , $2$ , $4$ , $2$ , $2$

c'est le seul cas où un retour au garage est possible sans répétition
Si exactement deux sommets de degré impair → il existe une CHAÎNE eulérienne, de l'un des deux vers l'autre

Exemple : un réseau de sept rues où $S$ et $T$ sont de degré $3$

le point de départ n'est pas au choix : il est imposé par la parité
Si quatre sommets de degré impair ou plus → ni chaîne ni cycle : il faudra RÉPÉTER des arêtes

Exemple : un carré dont deux sommets portent une impasse

on apparie alors les sommets impairs par les plus courts trajets, et on ajoute leur longueur au total
Si le graphe n'est pas connexe → aucun parcours eulérien, quels que soient les degrés

Exemple : deux triangles sans aucune arête entre eux

vérifier la connexité AVANT de compter les degrés

La rédaction attendue

Le correcteur coche des étapes. Les voici dans l'ordre, avec la phrase de conclusion qu'il attend mot pour mot.

Justifier l'existence d'un parcours eulérien

Quand l'utiliser : L'énoncé demande de passer une fois et une seule par chaque arête, ou de dire si c'est possible

1 Nommer le problème : « il s'agit d'un parcours eulérien, car l'énoncé demande de passer par chaque rue, donc par chaque arête ».
2 Vérifier la connexité en exhibant un parcours qui touche tous les sommets.
3 Dresser la liste des degrés, sommet par sommet, sans en oublier un.
4 Contrôler la somme : elle doit être paire et valoir le double du nombre d'arêtes.
5 Compter les sommets de degré impair et énoncer le critère qui s'applique à ce nombre.
6 Conclure, puis EXHIBER un parcours complet en listant les sommets dans l'ordre, ce qui vaut preuve.

Phrase de conclusion

« Le graphe est connexe et possède exactement deux sommets de degré impair, $S$ et $T$ : il admet donc une chaîne eulérienne, qui part obligatoirement de $S$ et arrive en $T$ . Le parcours $S$ , $R$ , $Q$ , $P$ , $T$ , $Q$ , $S$ , $T$ emprunte les sept arêtes, chacune une seule fois. »

Le piège : Conclure sans exhiber le parcours. Le critère prouve l'EXISTENCE ; l'énoncé demande presque toujours un parcours explicite, et il vaut la moitié des points.

Barème : 1 point pour la nature du problème, 1 point pour les degrés et leur somme, 1 point pour le critère, 2 points pour le parcours exhibé.

Construire l'arbre de valeurs minimales

Quand l'utiliser : L'énoncé demande de relier tous les sommets au coût total le plus faible

1 Annoncer le nombre d'arêtes attendu : « le graphe a $n$ sommets, l'arbre en comptera exactement $n-1$ ».
2 Trier toutes les arêtes par valeurs croissantes, en les écrivant en ligne.
3 Prendre les arêtes une à une dans cet ordre, et pour chacune dire si elle est retenue ou écartée.
4 Justifier chaque rejet par le cycle qu'elle fermerait, en nommant le chemin déjà existant.
5 S'arrêter dès que le compte de $n-1$ arêtes est atteint, et vérifier que chaque sommet apparaît au moins une fois.
6 Additionner les valeurs retenues et conclure.

Phrase de conclusion

« L'arbre de valeurs minimales est formé des arêtes $EF$ , $FA$ , $CD$ , $BC$ et $DE$ , soit cinq arêtes pour six sommets, et son coût total vaut $3+4+6+7+9=29$ milliers de dollars. »

Le piège : Écarter une arête sans dire pourquoi. Le rejet motivé par le cycle est une étape notée, pas un détail de brouillon.

Barème : 1 point pour le tri, 2 points pour les choix successifs et leurs justifications, 1 point pour le total.

Vérifier avant de rendre

Cinq minutes de vérification récupèrent plus de points qu'un exercice de plus commencé à la hâte.

La somme des degrés est paire

Additionnez les degrés que vous avez relevés et divisez par deux : vous devez retomber exactement sur le nombre d'arêtes que vous avez comptées à part.

Une somme de $15$ est impossible : une arête a été oubliée ou un degré mal lu. Une somme de $14$ pour $6$ arêtes annoncées signale la même erreur, dans l'autre sens.
L'arbre a exactement $n-1$ arêtes

Comptez les arêtes retenues et comparez à votre nombre de sommets moins un, puis vérifiez que chaque sommet apparaît au moins une fois dans la liste.

Six sommets et six arêtes retenues : il y a un cycle, une arête aurait dû être écartée. Six sommets et quatre arêtes : un sommet est resté isolé.
La chaîne écrite a le bon nombre de sommets

Une chaîne eulérienne qui emprunte $a$ arêtes s'écrit avec exactement $a+1$ sommets. Comptez-les sur votre copie.

Sept arêtes et une chaîne de sept sommets écrits : une arête a été sautée quelque part dans le parcours.
Le chemin critique est bien le plus long

Recalculez la durée d'au moins deux autres chemins complets du départ à l'arrivée et vérifiez qu'aucun ne dépasse celui que vous avez retenu.

Un autre chemin qui dure $13$ jours alors que vous avez annoncé $11$ : c'est lui le chemin critique, et toutes vos marges sont fausses.
La coloration se relit sur les ARÊTES

Parcourez la liste des arêtes une par une et vérifiez que les deux extrémités portent des couleurs différentes. Ne relisez pas sommet par sommet, c'est ainsi qu'on rate une arête.

Huit arêtes dans l'énoncé et seulement sept vérifiées : la huitième est presque toujours celle qui casse la coloration.

L'exercice type décortiqué

La tournée de déneigement, du vocabulaire au kilométrage

Le plan ci-dessous représente un secteur de sept rues. Les sommets sont des intersections et les valeurs sont des longueurs en kilomètres.

Un camion doit déneiger chaque rue. Le garage se trouve à l'intersection $P$ , où le camion doit revenir en fin de tournée.

Sept rues et cinq intersections. Les intersections

S

T

portent trois rues chacune, toutes les autres en portent deux ou quatre : ce sont elles qui décident de la réponse.

Étape 1

L'énoncé demande de déneiger chaque RUE, donc de parcourir chaque arête : c'est un problème eulérien.

Pourquoi

Nommer le problème avant de calculer vaut un point, et surtout évite de partir sur l'hamiltonien, qui ne mène nulle part ici. Le mot déclencheur est « chaque rue ».

Étape 2

Degrés : $\deg(P)=2$ , $\deg(Q)=4$ , $\deg(R)=2$ , $\deg(S)=3$ , $\deg(T)=3$ . Somme : $2+4+2+3+3=14$ .

Pourquoi

On relève les degrés dans l'ordre des sommets pour n'en oublier aucun. La somme est le premier contrôle : elle doit être paire.

Étape 3

$\dfrac{14}{2}=7$ arêtes, ce qui correspond bien aux sept rues de l'énoncé.

Pourquoi

Le second contrôle, gratuit : si le compte des arêtes tiré des degrés ne correspond pas à celui de la figure, un degré est faux et tout le reste s'écroule.

Étape 4

Deux sommets sont de degré impair, $S$ et $T$ . Le graphe est connexe. Il existe donc une chaîne eulérienne, et elle part de $S$ ou de $T$ .

Pourquoi

C'est l'application du critère, et elle répond déjà à la moitié de la question : le camion ne peut pas choisir son point de départ.

Étape 5

Un parcours qui convient : $S$ , $R$ , $Q$ , $P$ , $T$ , $Q$ , $S$ , $T$ . Il emprunte $SR$ , $RQ$ , $QP$ , $PT$ , $TQ$ , $QS$ et $ST$ , soit les sept rues, chacune une fois.

Pourquoi

Le critère prouve l'existence, pas davantage : le parcours exhibé est ce qui rapporte les points. On le vérifie en comptant huit sommets écrits pour sept arêtes.

Étape 6

Longueur parcourue : $5+4+6+3+4+5+3=30$ km, c'est-à-dire exactement la longueur totale du réseau.

Pourquoi

Un parcours sans répétition parcourt forcément la somme des longueurs. Retrouver ce total est la signature d'une chaîne correcte.

Étape 7

Le garage est en $P$ : revenir au départ exigerait un cycle eulérien, donc aucun sommet impair. Il y en a deux, $S$ et $T$ : c'est impossible sans répétition.

Pourquoi

La question du retour au garage est presque toujours posée en seconde partie, et elle change la réponse du tout au tout. On repart du critère, pas du parcours déjà écrit.

Étape 8

Le moins coûteux est de répéter le plus court trajet entre les deux sommets impairs, ici la rue $ST$ de $3$ km. La tournée fermée mesure $30+3=33$ km.

Pourquoi

Répéter une arête revient à la dédoubler, ce qui rend $S$ et $T$ pairs et rend le cycle possible. On choisit la moins chère des liaisons entre les deux sommets impairs.

Étape 9

Vérification : $33 > 30$ , et l'écart de $3$ km correspond bien à une rue parcourue deux fois.

Pourquoi

Un total fermé inférieur ou égal au total ouvert serait absurde. L'écart doit toujours être la longueur d'un vrai trajet du réseau.

Conclusion rédigée

Le camion peut déneiger les sept rues sans répétition en $30$ km, à condition de partir de $S$ et de terminer en $T$ . S'il doit partir du garage $P$ et y revenir, il devra répéter la rue $ST$ et parcourir au minimum $33$ km.

L'erreur classique sur cet exercice : Répondre « impossible » à la question du retour au garage et s'arrêter là. L'impossibilité porte sur le parcours SANS répétition ; la question attend le kilométrage minimal AVEC répétition, et c'est là que sont les points.

À savoir par cœur

• Somme des degrés $=2\times$ nombre d'arêtes. Elle est TOUJOURS paire, et le nombre de sommets impairs est toujours PAIR.
• Zéro sommet impair : cycle eulérien. DEUX sommets impairs : chaîne eulérienne, qui part de l'un et arrive à l'autre. Quatre ou plus : ni l'un ni l'autre.
• Eulérien, ce sont les ARÊTES. Hamiltonien, ce sont les SOMMETS. Aucun des deux n'entraîne l'autre.
• Un arbre de valeurs minimales a exactement $n-1$ arêtes, et une arête peu chère se refuse dès qu'elle ferme un cycle.
• L'arbre de valeurs minimales rend minimale la SOMME du réseau ; la chaîne de poids minimal rend minimal UN trajet. Ce ne sont jamais les mêmes arêtes.
• Le chemin critique est le chemin le PLUS LONG, et sa durée est la durée minimale du projet. Marge d'une tâche $=$ durée du projet $-$ durée du plus long chemin qui la contient.
• Un nombre chromatique se prouve en deux moitiés : une coloration qui montre que $k$ suffisent, et un argument qui montre que $k-1$ ne suffiraient pas.

Questions fréquentes

Quelle est la différence entre eulérien et hamiltonien ?

Un parcours eulérien passe une fois et une seule par chaque ARÊTE, un parcours hamiltonien par chaque SOMMET. Le premier a un critère automatique, celui des degrés ; le second n'en a aucun, on cherche un parcours ou on prouve qu'il est impossible. Un graphe peut avoir l'un sans l'autre, dans les deux sens.

Comment savoir si un graphe a une chaîne eulérienne ?

Vérifiez d'abord que le graphe est connexe, puis comptez les sommets de degré impair. Zéro sommet impair donne un cycle eulérien, deux sommets impairs donnent une chaîne qui part de l'un et arrive à l'autre, quatre ou plus ne donnent rien. Il n'y a jamais un seul sommet impair, ni trois : ce nombre est toujours pair.

Pourquoi le chemin critique est-il le plus long chemin ?

Parce qu'un projet n'est terminé que lorsque sa dernière tâche l'est. Tant que la plus longue suite de tâches enchaînées n'est pas achevée, le projet ne l'est pas, même si tout le reste est fini depuis des jours. La durée du plus long chemin est donc la durée minimale réalisable du projet.

Comment trouver l'arbre de valeurs minimales ?

Triez les arêtes par valeurs croissantes, puis prenez-les une à une en écartant celles qui fermeraient un cycle avec les arêtes déjà retenues. Arrêtez-vous quand vous avez le nombre de sommets moins une arête. Une arête bon marché se refuse sans hésiter si elle crée un cycle : le critère est le cycle, jamais le coût.

Comment calculer le nombre chromatique d'un graphe ?

Trouvez d'abord une coloration valide, ce qui montre qu'un certain nombre de couleurs suffit. Montrez ensuite qu'une couleur de moins est impossible, en exhibant un groupe de sommets tous reliés deux à deux, ou un cycle de longueur impaire. Les deux moitiés sont exigées, une coloration seule ne prouve pas le minimum.

Passer à la pratique

Exercices corrigés : La théorie des graphes

Une méthode se prouve sur une copie, pas sur une fiche. La série du même chapitre reprend chacun de ces pièges dans un exercice, avec le corrigé rédigé étape par étape.

10 exercices corrigés
100 points
150 minutes

Faire les exercices

Fiche précédente Les mathématiques financières Fiche suivante Probabilités, chances et espérance

Voir aussi

Toutes les fiches Tous les exercices Les mathématiques financières (CST 5)Probabilités et espérance (CST 5)Programmation linéaire et optimisation Tuteur au secondaire à Montréal

Vous cherchez un tuteur en math CST à Montréal ?

Contactez-moi pour une première séance. On travaille sur des exercices du niveau réel des évaluations de cinquième secondaire, séquence Culture, société et technique.

Me contacter WhatsApp

Site par Studio Squalli