Bonjour pouvez-vous m’aidez svp ?

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