Un virus se balade sur le réseau local de mon établissement. Seule thérapie : couper les connexions entre ordinateurs sains et ordinateurs infectés. Combien y a t-il de connexions à couper, dans le pire des cas ? Le calcul exact de ce nombre pour de grands réseaux est difficile. On sait le faire à 87.85672057848516% près, mais pas à 87.85672057848517% près. On dirait une curiosité mathématique. En fait, les problèmes de découpage de graphes sont typiques en informatique, à la fois pour les applications pratiques et sous l’angle théorique.
Cet article est une introduction « élémentaire » à un exposé que le même auteur a donne le 19 novembre 2011 dans le cadre du Séminaire Bourbaki à l’Institut Henri Poincaré.
ÉCRIT PAR
Pierre Pansu
Professeur - Université Paris-Saclay
