Les capteurs d'un bâtiment remontent leurs mesures par un réseau maillé de relais radio. Deux relais en liaison directe doivent émettre sur des canaux différents, sinon ils se brouillent. Le superviseur n'affiche pas la carte des liaisons, seulement, pour chaque relais, le nombre de liaisons actives.
La situation
| Relais | R1 | R2 | R3 | R4 | R5 | R6 | R7 | R8 | R9 |
|---|---|---|---|---|---|---|---|---|---|
| Liaisons actives | 4 | 3 | 3 | 2 | 5 | 3 | 4 | 2 | 2 |
Le réseau se modélise par un graphe non orienté : un sommet par relais, une arête par liaison. Le logiciel de planification stocke ce graphe sous la forme d'une matrice d'adjacence, un tableau carré avec une ligne et une colonne par relais. Il attribue ensuite les canaux par l'algorithme glouton : les relais sont traités l'un après l'autre, et chacun reçoit le plus petit canal qu'aucun de ses voisins déjà servis n'utilise.
Objectif
Sans connaître la carte des liaisons, calculer le nombre de liaisons du réseau, le nombre de cases à 1 et à 0 de la matrice d'adjacence, et le nombre de canaux que le glouton ne dépassera jamais, quel que soit l'ordre dans lequel il traite les relais.