Questions sur les graphes

Peut-on modéliser Internet par un graphe ?
lundi 25 juin 2007
par  Bernard Vuilleumier
popularité : 4%

Un graphe n’est composé que de points et de lignes. Mais cette apparente simplicité cache un potentiel insoupçonné : ces objets mathématiques sont source de problèmes qui comptent parmi les plus ardus des mathématiques.


Questions
- Qu’est-ce qu’un graphe ?
- Quand sont-ils apparus pour la première fois ?
- Quelles ont été les premières utilisations des graphes ?
- À quoi servent les graphes aujourd’hui ?
- Peut-on trouver son chemin grâce aux graphes ?
- Peut-on modéliser Internet par un graphe ?
- Quelles questions se posent encore sur les graphes ?
- Y a-t-il un rapport entre les problèmes de coloriage et les graphes ?


Activités [1]
- Construisez un graphe complet à n points pour 2 ≤ n ≤ 7.
- Combien de lignes chacun de ces graphes comporte-t-il ?
- Démêlez les graphes suivants :

- Générez un graphe orienté à partir des coordonnées de ses nœuds en connectant chacun d’eux à ses k plus proches voisins pour 1 ≤ k ≤ 4.
- Établissez les graphes du déclin des isotopes radioactifs du carbone.



[1Ces activités peuvent être réalisées à l’aide de petits programmes disponibles sur le site Wolfram Demonstrations Project. Ces mini-applications sont exécutables avec MathematicaPlayer qui est gratuit. Comment puis-je lire et exécuter un notebook Mathematica si je ne possède pas le logiciel ?