Ce petit problème permet de montrer que dans un réseau c’est à dire un ensemble d’entités (ici les agences) liées par des relations (ici les liaisons) des contraintes locales ( le nombre de liaisons par agences) peuvent conditionner l’architecture de l’ensemble. Nous allons voir que la connaissance du simple nombre de liaisons sur les N-1 premières agences non seulement conditionne les relations de la dernière, mais fixe l’architecture totale du réseau. On retrouve cette même idée dans les « Sudoku » jeux actuellement à la mode dans nos journaux qui ont pour but la construction d’un tableau unique de 81 chiffres (1 à 9) à partir de la seule connaissance du positionnement d’un dizaine de ceux-ci et des contraintes locales de non répétition du même chiffre par rangées (ligne ou colonne) et sous-tableau.
Voyons comment définir l’architecture du réseau d’agences qui respecte les contraintes proposées. Avant de généraliser prenons un exemple de N = 8 agences que l’on positionne sur un cercle (cf. fig. 1) pour une raison de commodité visuelle (la position géographique des agences ne joue évidemment aucun rôle) .
fig. 1 : Construction du réseau à N = 8 agences
Construisons le réseau pas à pas :
Pas 1 : L’agence N-1 = 7 doit avoir 7 relations, elle est donc reliée à toutes les autres (traits rouges), en particulier à 1 et 8. Ses liaisons sont donc définies et en conséquence la liaison unique de l’agence 1 est également définie. Reste à définir les liaisons des agences 2, 3, 4, 5, 6, 8.
Pas 2 : L’agence 6 ne peut être reliée ni à 1 ni à elle-même elle doit donc relier les 6 autres agences, en particulier 8 et 2, cette dernière à donc ses 2 liaisons d’établies. Reste à définir les liaisons des agences 3, 4, 5, 8.
Pas 3 : C’est au tour de l’agence 5 qui ne peut être reliée ni à 1, ni à 2 ni à elle-même et par suite est reliée aux 5 restantes : 3, 4, 6, 7, 8. L’agence 3 a donc ses 3 liaisons d’établies. Reste à définir les liaisons de 4 et 8
Pas 4 et fin : 4 ne peut être relié qu’à 5, 6, 7, 8 .
Toutes les liaisons ont été construites, en quatre pas nous avons établit 4 liaisons sur l’agence 8 et le réseau ainsi constitué est unique.
Cette méthode de construction est généralisable quel que soit le nombre d’agences : lorsque N est pair, il y a N/2 pas donc N/2 liaisons sur l’agence N ; lorsque N est impair il y a (N-1)/2 pas donc (N-1)/2 liaisons pour l’agence N. Et, répétons le, il n’y a qu’un seul réseau qui satisfait les contraintes imposées.
Evidemment puisque l’agence N-1 est reliée à toutes les autres elle sert de « Hub » et on relie n’importe quel couple en un maximum de 2 tractions.
Quant au nombre de liaisons il est égal à 1 + 2 + 3 + ... N-1 + N/2 = N²/2 si N est pair
et (N² -1)/2 dans le cas impair le nombre de camions nécessaires sera donc N² ou N²-1 selon les cas.
