On considère le graphe ci-dessus.
Ce graphe est-il connexe ?
Définition :
Un graphe est connexe s'il existe une chaîne reliant deux sommets quelconques de ce graphe.
Déterminer le degré de chacun des sommets.
On pourra donner le résultat sous forme de tableau.
Justifier l'existence d'une chaîne eulérienne.
Théorème d'Euler :
Un graphe connexe admet une chaîne eulérienne si et seulement si le nombre de ses sommets de degré impair est 0 ou 2.
Déterminer un encadrement du nombre chromatique de ce graphe.
Propriété 1:
Soit n le plus haut des degré des sommets d'un graphe G; le nombre chromatique de G est inférieur ou égal à n + 1.
Propriété 2:
Le nombre chromatique d'un graphe complet d'ordre n est égal à n.
Montrer que ce nombre chromatique est égal à 3.
Voici le plan d'un musée : les parties grisées matérialisent les portes et les visiteurs partent de l'accueil, visitent le musée et doivent terminer leur visite à la boutique.
Représenter la situation à l'aide d'un graphe en précisant ce que représentent arêtes et sommets.
Pourquoi est-il possible de trouver un circuit où les visiteurs passent une fois et une seule par toutes les portes ?
Donner un exemple d'un tel circuit.
Si le nombre de sommets de degré impair d'un graphe est 2, les sommets de degré impair sont les extrémités de la chaîne eulérienne.
Comment colorier les salles y compris l'accueil et la boutique, en utilisant un minimum de couleurs, pour que 2 salles qui communiquent par une porte aient des couleurs différentes ?
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.