Liaison satellite - Lycée Raynouard (Brignoles)

Un satellite de télécommunications géostationnaire est censé recevoir un nombre n de signaux émis depuis une source sur terre et les renvoyer vers leur destination également sur terre.
Pour cela, il dispose d'antennes de réception qui captent les signaux émis et d'antennes d'émission qui les renvoient. Malheureusement, les antennes peuvent tomber en panne (principalement si elles sont heurtées par un débris) et les pannes ne peuvent pas être réparées, le satellite étant à 36 000 km du sol.
Les constructeurs prévoient donc de mettre k antennes de réception et k antennes d'émission supplémentaires, afin de pouvoir tolérer k pannes reliées par un réseau d’interconnexion.
Ce réseau est constituée de commutateurs à quatre pattes (p1, p2, p3, p4) qui en changeant de position permettent de connecter p1 à p2 et p3 à p4 ou p1 à p3 et p2 à p4, ou p1 à p4 et p2 à p3. (Deux signaux différents peuvent passer par un commutateur mais emprunter des pattes différentes.)
Il doit permettre de fonctionner quelles que soient les k pannes sur les antennes de réception et les k pannes sur les antennes d'émission. Autrement dit, quelles que soient les n antennes de réception valides et les n antennes d'émissions valides, on doit trouver n chemins arête-disjoints chacun allant d'une antenne de réception valide à une antenne d'émission valide.

Le but est de construire de tels réseaux avec le moins de commutateurs possibles.
On pourra commencer par les cas où n ou k est petit.
Exemple avec n=1 et k=1, c’est à dire 2 antennes de réception et 2 antennes d'émission en tout. Donc il y a 1 signal qui part de la Terre et 2 pannes ( une sur les antennes émission et une sur celles de réception). Il faut se débrouiller pour qu’un signal arrive peu importe où se trouvent les pannes.



Sans commutateur, il peut y avoir une panne sur l’antenne 1 et sur l’antenne B, le signal n’arrivera jamais.
Avec un commutateur noté com1, en cas de panne sur l’antenne 1 et B, on peut relier l’antenne 2 à la A.