Algorithmique numérique Approximation creuse de graphes

L’état décide de changer sa stratégie d’investissement pour l’amélioration du réseau routier. Un projet de recherche a éte ́ lance ́ et l’équipe chargée d’optimiser la politique d’investissement a développe ́ un outil performant répondant a ̀ la question. Cependant, cet outil n’est pas capable de travailler sur le réseau routier complet du ̂ a ̀ la complexite ́ du problème d’optimisation sous-jacent. Votre tache consiste a ̀ pallier ce problème en fournissant a ̀ l’équipe d’optimisation un réseau de taille réduite sur base du réseau complet. Dans ce graphe, un sommet représente un carrefour et une arête une route du réseau. A ̀ chaque arête est associe ́ un poids entre 0 et 1 représentant la densite ́ de la circulation sur la route. Un exemple de réseau routier a ̀ 30 routes est donne ́ a ̀ la Figure 1a. Son homologue creux est donne ́ a ̀ la Figure 1b. (a) Graphe initial (b) Graphe creu