On considère le graphe suivant :
Le graphe est-il connexe ?
La chaîne A-B-C-D-E-F-G-H contient tous les sommets du graphe par conséquent, il existe au moins une chaîne reliant deux sommets quelconques.
Le graphe est connexe
Le graphe admet-il des chaînes eulériennes ? Si oui, en préciser une.
Déterminons le degré de chacun des sommets.
Sommets | A | B | C | D | E | F | G | H |
Degré | 4 | 3 | 4 | 4 | 4 | 3 | 4 | 4 |
Le graphe est connexe et il existe deux sommets de degré impair, il admet donc une chaîne eulérienne commençant par un des deux sommets de degré impair (B ou F) et finissant par le deuxième sommet de degré impair. Par exemple :
F - C - H - E - A - D - G - B - C - D - E - F - G - H - A - B est une chaîne eulérienne.
Justifier la non-existence d'un cycle eulérien pour le graphe . Quelle arête peut-on alors ajouter à ce graphe pour obtenir un graphe contenant un cycle eulérien ?
Il y a un cycle eulérien si tous les sommets du graphe sont pairs. Il suffit donc d'ajouter une arête entre les sommets G et F pour obtenir un graphe connexe dont tous les sommets sont de degré pair
Soit M la matrice associée à ce graphe (les sommets sont pris dans l'ordre alphabétique).On donne la matrice Déterminer le nombre de chaînes de longueur 3 partant du sommet G et aboutissant au sommet E. Citer alors toutes ces chaînes
Les sommets de la matrice M sont pris dans l'ordre alphabétique, par conséquent, le terme situé à l'intersection de la septième ligne et de la cinquième colonne de la matrice , donne le nombre de chaînes de longueur 3 partant du sommet G et aboutissant au sommet E
Il y a 3 chaînes de longueur 3 partant du sommet G et aboutissant au sommet E : G-B-A-E, G-D-A-E et G-H-A-E.
Donner un encadrement du nombre chromatique X du graphe. Déterminer ce nombre chromatique, en explicitant clairement la démarche.
Le plus haut degré des sommets est 4 donc . D'autre part, A-D-E est un sous graphe complet d'ordre 3 donc . Ainsi,
Utilisons l'algorithme de coloration de Welsh et Powell :
Les sommets étant classés par ordre de degré décroissant, on attribue la couleur 1 aux sommets A, C et G; la couleur 2 aux sommets D, H, B et F ; la couleur 3 au sommet E.
Une coloration du graphe avec 3 couleurs est possible et donc le nombre chromatique de ce graphe est égal à 3.
Les documents présentés ne sont pas libres de droits. Vous pouvez les télécharger et diffuser (en indiquant la provenance) à condition de ne pas en faire un usage commercial.