Un opérateur installe huit antennes sur un site industriel étendu. Deux antennes trop proches se brouillent si elles émettent sur la même fréquence. Chaque fréquence supplémentaire se loue, d'où la question : combien de fréquences au minimum, et comment les attribuer ?
La situation
Une étude de propagation a relevé les paires d'antennes qui se brouillent :
| Antenne | Se brouille avec |
|---|---|
| A | B, G |
| B | A, C, D, F, G |
| C | B, D, H |
| D | B, C, E, G |
| E | D, H |
| F | B |
| G | A, B, D, H |
| H | C, E, G |
A -- B
A -- G
B -- C
B -- D
B -- F
B -- G
C -- D
C -- H
D -- E
D -- G
E -- H
G -- H
titre: Le graphe des brouillages : un sommet par antenne, une arête par paire qui se brouille.
Les fréquences sont numérotées 0, 1, 2, et ainsi de suite. En cas d'égalité de degré, Welsh-Powell traite les antennes dans l'ordre alphabétique.
Objectif
Appliquer Welsh-Powell et compter les fréquences utilisées ; appliquer le même glouton dans l'ordre alphabétique pour comparer ; puis déterminer le nombre chromatique, en justifiant qu'on ne peut pas descendre en dessous.