Dessiner le graphe (non orienté) à huit sommets dont les arêtes sont :
(1 ; 2), (1 ; 3), (2 ; 3), (2 ; 4), (2 ; 7), (3 ; 5), (3 ; 6), (3 ; 7), (4 ; 5), (4 ; 7), (5 ; 6), (5 ; 7), (6 ; 7), (6 ; 8), (7 ; 8).
Donner la matrice M associée à ce graphe.
Combien y a-t-il de chemins de longueur 3 permettant de se rendre du sommet 1 au sommet 8 ?
Les donner tous.
Est-il possible de parcourir toutes les arêtes de ce graphe sans passer plus d'une fois par la même arête ?
Existe-il un cycle passant une fois et une seule par toutes les arêtes du graphe ?
On considère le graphe ci-dessous. On note Γ son nombre chromatique.
Donner un encadrement du nombre chromatique.
Donner une coloration de ce graphe.
En déduire la valeur du nombre chromatique de .
Le graphe ci-dessous indique les différentes liaisons entre plusieurs lieux. Le long de chaque arête figure la distance en kilomètres séparant les différents lieux.
En précisant la méthode utilisée, déterminer le plus court chemin possible pour aller de A à L.
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.