Un groupe de neuf scouts partent camper dans la montagne. Ils communiquent en morse, avec leurs lampes de poche, mais les configurations du terrain font que :
Afin d’être certains que tout le monde soit bien informé, ils ont convenu que tout scout recevant un message pour la première fois le retransmet instantanément à son tour. Arthur veut envoyer le message “Toujours prêt” à ses camarades. En supposant que l’envoi du message en morse prend une minute à chaque fois, Arthur souhaite savoir combien de temps il faudra pour que tout lemonde ait reçu son message, et qui seront les derniers informés.
On définit le graphe simple non orienté $G = (S, A)$, tel que :
$$S = \{ s \mid s \text{ est un scout} \}$$ $$A = \{ \{i, j\} \subseteq S \mid i \text{ peut communiquer directement avec } j \}$$
On cherche à définir la distance maximum entre Arthur et les autres membres ainsi que les derniers membres atteint.
La distance entre Arthur et les autres membres est définie par $\delta(A, s_k) = k \times \text{ nombre d’arêtes entre } A \text{ et } s_k$, car $G$ ne contient que des poids uniformes.
Nous cherchons donc : $$T = \underset{s_k \in S}{max~}{\delta(A, s_k)}$$ $$D = \{s_k \in S \mid \delta(A, s_k) = T \}$$
Pour résoudre ce problème nous utilisons le parcours en largeur (en. Breadth First Search).
Précondition : Poids uniformes
Complexité : $\mathcal{O}(\mid S \mid + \mid A \mid)$
// Loading
Nous noterons $\pi[s_k]$ le parent de $s_k$. $F$ est la file de traitement des noeuds.
Sélection du noeud A.
// Loading
$$ F = \{ A \} $$
| $A$ | $B$ | $C$ | $D$ | $E$ | $F$ | $G$ | $H$ | $I$ | |
|---|---|---|---|---|---|---|---|---|---|
| $\pi[s_k]$ | $A$ | None | None | None | None | None | None | None | None |
| $\delta(A, s_k)$ | $0$ | $+\infty$ | $+\infty$ | $+\infty$ | $+\infty$ | $+\infty$ | $+\infty$ | $+\infty$ | $+\infty$ |
Découverte du noeud B, mise à jour des tableaux et ajout dans la file.
// Loading
$$ F = \{ A, B \} $$
| $A$ | $B$ | $C$ | $D$ | $E$ | $F$ | $G$ | $H$ | $I$ | |
|---|---|---|---|---|---|---|---|---|---|
| $\pi[s_k]$ | $A$ | $A$ | None | None | None | None | None | None | None |
| $\delta(A, s_k)$ | $0$ | $1$ | $+\infty$ | $+\infty$ | $+\infty$ | $+\infty$ | $+\infty$ | $+\infty$ | $+\infty$ |
Découverte du noeud D, mise à jour des tableaux et ajout dans la file.
// Loading
$$ F = \{ A, B, D \} $$
| $A$ | $B$ | $C$ | $D$ | $E$ | $F$ | $G$ | $H$ | $I$ | |
|---|---|---|---|---|---|---|---|---|---|
| $\pi[s_k]$ | $A$ | $A$ | None | $A$ | None | None | None | None | None |
| $\delta(A, s_k)$ | $0$ | $1$ | $+\infty$ | $1$ | $+\infty$ | $+\infty$ | $+\infty$ | $+\infty$ | $+\infty$ |
Le noeud A n’a plus de voisin, on le supprime de la file.
// Loading
$$ F = \{ B, D \} $$
| $A$ | $B$ | $C$ | $D$ | $E$ | $F$ | $G$ | $H$ | $I$ | |
|---|---|---|---|---|---|---|---|---|---|
| $\pi[s_k]$ | $A$ | $A$ | None | $A$ | None | None | None | None | None |
| $\delta(A, s_k)$ | $0$ | $1$ | $+\infty$ | $1$ | $+\infty$ | $+\infty$ | $+\infty$ | $+\infty$ | $+\infty$ |
Sélection du noeud B.
// Loading
$$ F = \{ B, D \} $$
| $A$ | $B$ | $C$ | $D$ | $E$ | $F$ | $G$ | $H$ | $I$ | |
|---|---|---|---|---|---|---|---|---|---|
| $\pi[s_k]$ | $A$ | $A$ | None | $A$ | None | None | None | None | None |
| $\delta(A, s_k)$ | $0$ | $1$ | $+\infty$ | $1$ | $+\infty$ | $+\infty$ | $+\infty$ | $+\infty$ | $+\infty$ |
Découverte du noeud F, mise à jour des tableaux et ajout dans la file.
// Loading
$$ F = \{ B, D, F \} $$
| $A$ | $B$ | $C$ | $D$ | $E$ | $F$ | $G$ | $H$ | $I$ | |
|---|---|---|---|---|---|---|---|---|---|
| $\pi[s_k]$ | $A$ | $A$ | None | $A$ | None | $B$ | None | None | None |
| $\delta(A, s_k)$ | $0$ | $1$ | $+\infty$ | $1$ | $+\infty$ | $2$ | $+\infty$ | $+\infty$ | $+\infty$ |
Le noeud B n’a plus de voisin, on le supprime de la file.
// Loading
$$ F = \{ D, F \} $$
| $A$ | $B$ | $C$ | $D$ | $E$ | $F$ | $G$ | $H$ | $I$ | |
|---|---|---|---|---|---|---|---|---|---|
| $\pi[s_k]$ | $A$ | $A$ | None | $A$ | None | $B$ | None | None | None |
| $\delta(A, s_k)$ | $0$ | $1$ | $+\infty$ | $1$ | $+\infty$ | $2$ | $+\infty$ | $+\infty$ | $+\infty$ |
Sélection du noeud D.
// Loading
$$ F = \{ D, F \} $$
| $A$ | $B$ | $C$ | $D$ | $E$ | $F$ | $G$ | $H$ | $I$ | |
|---|---|---|---|---|---|---|---|---|---|
| $\pi[s_k]$ | $A$ | $A$ | None | $A$ | None | $B$ | None | None | None |
| $\delta(A, s_k)$ | $0$ | $1$ | $+\infty$ | $1$ | $+\infty$ | $2$ | $+\infty$ | $+\infty$ | $+\infty$ |
Découverte du noeud G, mise à jour des tableaux et ajout dans la file.
// Loading
$$ F = \{ D, F, G \} $$
| $A$ | $B$ | $C$ | $D$ | $E$ | $F$ | $G$ | $H$ | $I$ | |
|---|---|---|---|---|---|---|---|---|---|
| $\pi[s_k]$ | $A$ | $A$ | None | $A$ | None | $B$ | $D$ | None | None |
| $\delta(A, s_k)$ | $0$ | $1$ | $+\infty$ | $1$ | $+\infty$ | $2$ | $2$ | $+\infty$ | $+\infty$ |
Le noeud D n’a plus de voisin, on le supprime de la file.
// Loading
$$ F = \{ F, G \} $$
| $A$ | $B$ | $C$ | $D$ | $E$ | $F$ | $G$ | $H$ | $I$ | |
|---|---|---|---|---|---|---|---|---|---|
| $\pi[s_k]$ | $A$ | $A$ | None | $A$ | None | $B$ | $D$ | None | None |
| $\delta(A, s_k)$ | $0$ | $1$ | $+\infty$ | $1$ | $+\infty$ | $2$ | $2$ | $+\infty$ | $+\infty$ |
Sélection du noeud F.
// Loading
$$ F = \{ F, G \} $$
| $A$ | $B$ | $C$ | $D$ | $E$ | $F$ | $G$ | $H$ | $I$ | |
|---|---|---|---|---|---|---|---|---|---|
| $\pi[s_k]$ | $A$ | $A$ | None | $A$ | None | $B$ | $D$ | None | None |
| $\delta(A, s_k)$ | $0$ | $1$ | $+\infty$ | $1$ | $+\infty$ | $2$ | $2$ | $+\infty$ | $+\infty$ |
Découverte du noeud C, mise à jour des tableaux et ajout dans la file.
// Loading
$$ F = \{ F, G, C \} $$
| $A$ | $B$ | $C$ | $D$ | $E$ | $F$ | $G$ | $H$ | $I$ | |
|---|---|---|---|---|---|---|---|---|---|
| $\pi[s_k]$ | $A$ | $A$ | $F$ | $A$ | None | $B$ | $D$ | None | None |
| $\delta(A, s_k)$ | $0$ | $1$ | $3$ | $1$ | $+\infty$ | $2$ | $2$ | $+\infty$ | $+\infty$ |
Découverte du noeud E, mise à jour des tableaux et ajout dans la file.
// Loading
$$ F = \{ F, G, C, E \} $$
| $A$ | $B$ | $C$ | $D$ | $E$ | $F$ | $G$ | $H$ | $I$ | |
|---|---|---|---|---|---|---|---|---|---|
| $\pi[s_k]$ | $A$ | $A$ | $F$ | $A$ | $F$ | $B$ | $D$ | None | None |
| $\delta(A, s_k)$ | $0$ | $1$ | $3$ | $1$ | $3$ | $2$ | $2$ | $+\infty$ | $+\infty$ |
Découverte du noeud I, mise à jour des tableaux et ajout dans la file.
// Loading
$$ F = \{ F, G, C, E, I \} $$
| $A$ | $B$ | $C$ | $D$ | $E$ | $F$ | $G$ | $H$ | $I$ | |
|---|---|---|---|---|---|---|---|---|---|
| $\pi[s_k]$ | $A$ | $A$ | $F$ | $A$ | $F$ | $B$ | $D$ | None | $F$ |
| $\delta(A, s_k)$ | $0$ | $1$ | $3$ | $1$ | $3$ | $2$ | $2$ | $+\infty$ | $3$ |
Le noeud F n’a plus de voisin, on le supprime de la file.
// Loading
$$ F = \{ G, C, E, I \} $$
| $A$ | $B$ | $C$ | $D$ | $E$ | $F$ | $G$ | $H$ | $I$ | |
|---|---|---|---|---|---|---|---|---|---|
| $\pi[s_k]$ | $A$ | $A$ | $F$ | $A$ | $F$ | $B$ | $D$ | None | $F$ |
| $\delta(A, s_k)$ | $0$ | $1$ | $3$ | $1$ | $3$ | $2$ | $2$ | $+\infty$ | $3$ |
Sélection du noeud G.
// Loading
$$ F = \{ G, C, E, I \} $$
| $A$ | $B$ | $C$ | $D$ | $E$ | $F$ | $G$ | $H$ | $I$ | |
|---|---|---|---|---|---|---|---|---|---|
| $\pi[s_k]$ | $A$ | $A$ | $F$ | $A$ | $F$ | $B$ | $D$ | None | $F$ |
| $\delta(A, s_k)$ | $0$ | $1$ | $3$ | $1$ | $3$ | $2$ | $2$ | $+\infty$ | $3$ |
Découverte du noeud H, mise à jour des tableaux et ajout dans la file.
// Loading
$$ F = \{ G, C, E, I, H \} $$
| $A$ | $B$ | $C$ | $D$ | $E$ | $F$ | $G$ | $H$ | $I$ | |
|---|---|---|---|---|---|---|---|---|---|
| $\pi[s_k]$ | $A$ | $A$ | $F$ | $A$ | $F$ | $B$ | $D$ | $G$ | $F$ |
| $\delta(A, s_k)$ | $0$ | $1$ | $3$ | $1$ | $3$ | $2$ | $2$ | $3$ | $3$ |
Le noeud G n’a plus de voisin, on le supprime de la file.
// Loading
$$ F = \{ C, E, I, H \} $$
| $A$ | $B$ | $C$ | $D$ | $E$ | $F$ | $G$ | $H$ | $I$ | |
|---|---|---|---|---|---|---|---|---|---|
| $\pi[s_k]$ | $A$ | $A$ | $F$ | $A$ | $F$ | $B$ | $D$ | $G$ | $F$ |
| $\delta(A, s_k)$ | $0$ | $1$ | $3$ | $1$ | $3$ | $2$ | $2$ | $3$ | $3$ |
Sélection du noeud C.
// Loading
$$ F = \{ C, E, I, H \} $$
| $A$ | $B$ | $C$ | $D$ | $E$ | $F$ | $G$ | $H$ | $I$ | |
|---|---|---|---|---|---|---|---|---|---|
| $\pi[s_k]$ | $A$ | $A$ | $F$ | $A$ | $F$ | $B$ | $D$ | $G$ | $F$ |
| $\delta(A, s_k)$ | $0$ | $1$ | $3$ | $1$ | $3$ | $2$ | $2$ | $3$ | $3$ |
Le noeud C n’a plus de voisin, on le supprime de la file.
// Loading
$$ F = \{ E, I, H \} $$
| $A$ | $B$ | $C$ | $D$ | $E$ | $F$ | $G$ | $H$ | $I$ | |
|---|---|---|---|---|---|---|---|---|---|
| $\pi[s_k]$ | $A$ | $A$ | $F$ | $A$ | $F$ | $B$ | $D$ | $G$ | $F$ |
| $\delta(A, s_k)$ | $0$ | $1$ | $3$ | $1$ | $3$ | $2$ | $2$ | $3$ | $3$ |
Sélection du noeud E.
// Loading
$$ F = \{ E, I, H \} $$
| $A$ | $B$ | $C$ | $D$ | $E$ | $F$ | $G$ | $H$ | $I$ | |
|---|---|---|---|---|---|---|---|---|---|
| $\pi[s_k]$ | $A$ | $A$ | $F$ | $A$ | $F$ | $B$ | $D$ | $G$ | $F$ |
| $\delta(A, s_k)$ | $0$ | $1$ | $3$ | $1$ | $3$ | $2$ | $2$ | $3$ | $3$ |
Le noeud E n’a plus de voisin, on le supprime de la file.
// Loading
$$ F = \{ I, H \} $$
| $A$ | $B$ | $C$ | $D$ | $E$ | $F$ | $G$ | $H$ | $I$ | |
|---|---|---|---|---|---|---|---|---|---|
| $\pi[s_k]$ | $A$ | $A$ | $F$ | $A$ | $F$ | $B$ | $D$ | $G$ | $F$ |
| $\delta(A, s_k)$ | $0$ | $1$ | $3$ | $1$ | $3$ | $2$ | $2$ | $3$ | $3$ |
Sélection du noeud I.
// Loading
$$ F = \{ I, H \} $$
| $A$ | $B$ | $C$ | $D$ | $E$ | $F$ | $G$ | $H$ | $I$ | |
|---|---|---|---|---|---|---|---|---|---|
| $\pi[s_k]$ | $A$ | $A$ | $F$ | $A$ | $F$ | $B$ | $D$ | $G$ | $F$ |
| $\delta(A, s_k)$ | $0$ | $1$ | $3$ | $1$ | $3$ | $2$ | $2$ | $3$ | $3$ |
Le noeud I n’a plus de voisin, on le supprime de la file.
// Loading
$$ F = \{ H \} $$
| $A$ | $B$ | $C$ | $D$ | $E$ | $F$ | $G$ | $H$ | $I$ | |
|---|---|---|---|---|---|---|---|---|---|
| $\pi[s_k]$ | $A$ | $A$ | $F$ | $A$ | $F$ | $B$ | $D$ | $G$ | $F$ |
| $\delta(A, s_k)$ | $0$ | $1$ | $3$ | $1$ | $3$ | $2$ | $2$ | $3$ | $3$ |
Sélection du noeud H.
// Loading
$$ F = \{ H \} $$
| $A$ | $B$ | $C$ | $D$ | $E$ | $F$ | $G$ | $H$ | $I$ | |
|---|---|---|---|---|---|---|---|---|---|
| $\pi[s_k]$ | $A$ | $A$ | $F$ | $A$ | $F$ | $B$ | $D$ | $G$ | $F$ |
| $\delta(A, s_k)$ | $0$ | $1$ | $3$ | $1$ | $3$ | $2$ | $2$ | $3$ | $3$ |
Le noeud H n’a plus de voisin, on le supprime de la file.
// Loading
$$ F = \{ \} $$
| $A$ | $B$ | $C$ | $D$ | $E$ | $F$ | $G$ | $H$ | $I$ | |
|---|---|---|---|---|---|---|---|---|---|
| $\pi[s_k]$ | $A$ | $A$ | $F$ | $A$ | $F$ | $B$ | $D$ | $G$ | $F$ |
| $\delta(A, s_k)$ | $0$ | $1$ | $3$ | $1$ | $3$ | $2$ | $2$ | $3$ | $3$ |
Nous avons : $$T = \underset{s_k \in S}{max~}{\delta(A, s_k)} = 3$$ $$D = \{s_k \in S \mid \delta(A, s_k) = T \} = \{ C, E, H, I \}$$
Les derniers informés sont Céleste, Ernestine, Hugo et Isidore.