Cette page contient divers exercices corrigés sur la modélisation de la théorie des graphes et les problèmes de coloration de graphe. Veuillez consulter la page sur la théorie des graphes pour en savoir plus sur les bases de la théorie des graphes et divers problèmes de théorie des graphes.
Exercice 1
Considérant un jeu de dominos utilisant les nombres 0, 1, 2, 3, 4, comme sur chaque domino comprend deux chiffres distincts, comme 1 et 3, le problème suivant est proposé : est-il possible d’aligner tous les dominos de sorte que lorsque deux pions « toucher » les numéros « au contact » sont identiques ?
Montrer le problème sous la forme d’un graphe complet K5. Le problème est de trouver un cycle eulérien dans le graphe.
Exercice 2
Considérez la séquence 01110100 comme étant disposée selon un motif circulaire. Notez que chacun des huit triplets binaires possibles : 000, 001, 011, . . . , 111 apparaissent exactement une fois dans la liste circulaire. Pouvez-vous construire une liste similaire de longueur 16 où les quatre modèles de chiffres binaires apparaissent exactement une fois chacun ?
C’est un graphe à quatre sommets, chacun étiqueté avec l’une des paires possibles de chiffres binaires. Imaginez que chaque nœud soit les deux derniers chiffres du modèle jusqu’à présent. Les flèches s’éloignant d’un sommet sont étiquetées 0 ou 1 : les deux valeurs possibles pour le chiffre suivant pouvant être ajouté au motif, et les extrémités des flèches indiquent les nouveaux deux derniers chiffres. Par exemple, le nœud 00 va à 01 avec un arc nommé 1, et va à 00 avec un arc nommé 0.
Pour obtenir toutes les combinaisons possibles à trois chiffres, nous devons parcourir le graphe avec un cycle eulérien. En raison du résultat du problème précédent, il y a toujours deux flèches vers l’extérieur et deux flèches vers chaque sommet, et en raison du résultat du problème précédent, il doit y avoir un circuit eulérien.
La situation est la même pour n’importe quel nombre de chiffres sauf que le graphique deviendra de plus en plus complexe. Pour la version à 4 chiffres, il y aura 8 sommets et 16 arêtes, et ainsi de suite. Mais dans tous les cas, il y aura deux arêtes entrant et deux sortant de chaque sommet, donc un circuit eulérien est possible.
Exercice 3
Un serveur peut acheminer un maximum de packages en même temps. Sept sous-stations sont reliées à un serveur, une sous-station ne peut pas envoyer de colis si certaines sous-stations utilisent déjà le lien. Le tableau suivant présente chaque sous-station de la capacité à envoyer un colis en fonction des autres. Par exemple, un colis de A ne peut pas être envoyé s’il existe déjà un colis de D mais peut être envoyé lorsque B a envoyé un colis.
Sous-station | A | B | C | D | E | F | G |
N’est pas avec | D,E | D,E,F,G | E,G | A,B,E | A,B,C,D,F,G | B,E,G | B,C,E,F |
Représenter les liens dans un graphique. Combien de paquets le serveur doit-il gérer en même temps (valeur maximale) ?
Le graphe est 4-chromatique.
Exercice 4
Une école doit faire passer des épreuves écrites à quatre élèves : Pierre, Jean, Guillermo et Ibrahim. Sept disciplines sont concernées : mathématiques, physique, biologie, français, anglais, espagnol et histoire.
Pierre doit passer les mathématiques, la physique et l’anglais, Jean les mathématiques, la biologie et le français, Guillermo les mathématiques, l’anglais et l’espagnol et Ibrahim la physique, le français et l’histoire.
Quel est le nombre minimum de créneaux horaires à prévoir pour qu’aucun étudiant ne doive passer deux épreuves simultanément ? Quel est le nombre chromatique d’un graphe complet ? Comment borner les nombres chromatiques dans un graphe ?
Un sommet représente une discipline, une arête relie deux disciplines si elles ne peuvent avoir lieu en même temps. Le problème peut être résolu en recherchant un nombre minimum de couleurs. Le plus grand sous-graphe complet est K3, il y a donc au moins 3 couleurs. Le degré maximum est de cinq, il y a donc au plus 5 couleurs. Par expérimentation, le graphe est 3-chromatique.
FR 
EN 
ES