Sciences naturelles
Questions sur les graphes
Peut-on modéliser Internet par un graphe ?

Questions sur les graphes. LR200612403

Article mis en ligne le 25 juin 2007
dernière modification le 28 août 2011

par Bernard Vuilleumier

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.