Constructeur d'autoroutes, Comptes Rendus MATh.en.JEANS 00-04

Graphes complets (relier chaque ville à toutes les autres) :

Cela est possible si le nombre de villes est inférieur ou égal à 4.

Graphes à degré fixe (relier chaque ville à un nombre fixé de villes) :

On peut relier chaque ville à :

2 villes pour tout nombre de villes au moins égal à 3;

3 villes pour tout nombre de villes pair et supérieur ou égal à 4;

4 villes pour 6 villes et pour tout nombre de villes supérieur ou égal à 8;

5 villes si le nombre de villes est 12.

Comptes Rendus MATh.en.JEANS 00-04          © MATh.en.JEANS 2001. Tous droits réservés.

 0. Introduction

1. Influence de la configuration des villes sur la réalisation du contrat

2. Relier toutes les villes entre elles

3. Relier chaque ville à un nombre fixé de villes

4. Conclusion

Retour aux Comptes Rendus MATh.en.JEANS