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.