Bonjour,
1)a)
. ABCDEFG contient tous les sommets donc pour toute paire de sommets, il existe une chaine qui les relie : Le graphe est connexe.
. Tous les sommets sont de degré pair.
Donc il existe un cycle Eulérien.
b) par exp : A - C - E - F - G - E - D - F - B - D - C - B - A
2) A et G ne sont pas de degré impair, donc pas de chaine Eulérienne, donc impossible.
3) algorithme de Dijkstra pour rechercher la chaine de poids minimal entre A et G
ci-dessous
chaine de poids minimal : A-C-D-F-G
Parcours croisant le minimum de monstres : G-F-D-C-A avec 25 monstres
