Correction : les graphes
A l'origine des graphes : les ponts de Königsberg
- sommets = les îles
- arêtes = les ponts qui relient les îles
Les ponts peuvent être franchis dans les deux sens : le graphe n'est donc pas orienté
Réseau d'amis
Certaines relations sont en "sens unique" : le graphe est donc orienté.
La visite au musée
- sommets = les salles
- arêtes = les portes qui relient les salles
Le tournoi de foot
Un seul match entre deux équipes : il y a donc une relation non orientée d'un sommet à chacun des autres sommets :
- 4 sommets, 1 relation entre chaque paire de sommets donc 6 relations soit 6 matches.
- Ce graphe est d'un seul tenant, il est donc bien connexe.
- Chaque sommet est en relation avec tous les autres, donc voisins de chacun des autres sommets : le graphe est donc bien complet.
Le club de tennis
- A : +1 +1 +1 = 3
B : -1 +1 +1 = 1
C : -1 -1 -1 = - 3
D : -1 -1 +1 = - 1
- Ce sont donc A et B qui sont sélectionnés.
Loup, chèvre, chou
Le graphe associé à l'énigme :
Un des chemins à suivre ( il y en a un deuxième ) est donc : 000 -> 010 -> 110 -> 100 -> 101 -> 111, soit :
- emmener la chèvre
- revenir à vide
- emmener le loup
- revenir avec la chèvre
- emmener le chou
- revenir à vide
- emmener la chèvre
Une journées en enfer...
Voila le graphe complet modélisant le problème :
Heureusement qu'il n'est pas nécessaire de le construire à la main pour résoudre l'énigme 😱...
La disposition des nœuds fait cependant bien apparaître le chemin à suivre : (0, 0) -> (5, 0) -> (2, 3) -> (2, 0) -> (0, 2) -> (5, 2) -> (4, 3) -> (4, 0), soit :
- remplir le seau de 5L
- transvaser une partie du seau de 5L pour remplir celui de 3L ( le seau de 5L contient donc maintenant 2L d'eau )
- vider le seau de 3L
- transvaser le seau de 5L dans celui de 3L ( le seau de 3L contient 2L d'eau )
- remplir le seau de 5L
- transvaser une partie du seau de 5L pour remplir celui de 3L ( le seau de 5L contient donc 1L de moins, soit 4L )
