On considère le graphe G suivant :
Le graphe G est-il connexe ? Expliquer la réponse.
La chaîne A-B-C-D-E-F-G contient tous les sommets du graphe.
Par conséquent, pour toute paire de sommets distincts, il existe une chaîne les reliant donc le graphe est connexe.
Le graphe G admet-il des chaînes eulériennes ? Si oui, en préciser une.
Dans un graphe non orienté, le degré d'un sommet du graphe est le nombre d'arêtes issues de ce sommet. Nous avons donc :
| Sommets | A | B | C | D | E | F |
| Degré des sommets du graphe | 3 | 4 | 4 | 4 | 4 | 3 |
Le graphe est connexe et contient seulement deux sommets de degré impair par conséquent, il existe une chaîne eulérienne commençant par un des deux sommets de degré impair (A ou F) et finissant par le deuxième sommet de degré impair. Par exemple la chaîne A-B-C-D-E-F-D-A-C-E-B-F.
Justifier la non-existence d'un cycle eulérien pour le graphe G. Quelle arête peut-on alors ajouter à ce graphe pour obtenir un graphe contenant un cycle eulérien ?
Le graphe contenant deux sommets de degré impair, il n'existe pas de cycle eulérien. Il suffit d'ajouter une arête reliant les sommets A et F pour obtenir un graphe connexe dont tous les sommets sont de degré pair donc contenant un cycle eulérien.
Déterminer un encadrement du nombre chromatique du graphe G. Justifier la réponse.
Soit n le nombre chromatique de ce graphe.
Le plus haut degré des sommets est 4 donc . D'autre part, le sous graphe est un sous graphe complet d'ordre 3 donc .
Ainsi,
Déterminer alors ce nombre chromatique, en explicitant clairement la démarche.
Utilisons l'algorithme de coloration de Welsh et Powell (algorithme "glouton").
Les sommets étant classés par ordre de degré décroissant, on attribue la couleur 1 aux sommets B et D; la couleur 2 aux sommets C et F et la couleur 3 aux sommets E et A
Une coloration du graphe avec 3 couleurs est possible et donc le nombre chromatique de ce graphe est égal à 3.
Déterminer la matrice M associée à ce graphe (les sommets sont pris dans l'ordre alphabétique).
La matrice M associée à ce graphe est
On donne
Déterminer le nombre de chaînes de longueur 3 partant du sommet A et aboutissant au sommet F. 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 première ligne et de la sixième colonne de la matrice , donne le nombre de chaînes de longueur 3 partant du sommet A et aboutissant au sommet F :
Il y a 5 chaînes de longueur 3 partant du sommet A et aboutissant au sommet F : A-B-E-F, A-C-B-F, A-C-E-F, A-C-D-F et A-D-E-F.
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.