Adloun

Graphes : modélisation et représentations

Cours · OCaml (option informatique), chapitre 14 · prépas MPSI et MP, option informatique · le début du chapitre, la suite sur Adloun

Un graphe : des sommets reliés par des arêtes.

14.1 Introduction et motivation

Réseaux routiers, liens entre pages web, amis d'un réseau social, dépendances entre tâches : une foule de problèmes se modélisent par un graphe — des sommets reliés par des arêtes. Avant d'explorer un graphe (parcours, plus courts chemins, aux chapitres suivants), il faut savoir le représenter en machine. Ce chapitre installe le vocabulaire et les deux représentations fondamentales en OCaml : la matrice d'adjacence et les listes d'adjacence, leurs forces respectives, et comment passer de l'une à l'autre.

On y mobilise tout l'arsenal des chapitres précédents : tableaux (chapitre 5) pour la matrice, listes (chapitre 2) pour les voisinages, et le raisonnement de complexité pour choisir la bonne structure selon la densité du graphe.

14.2 Vocabulaire

Définition 14.1Graphe

Un graphe est la donnée d'un ensemble de sommets et d'un ensemble d'arêtes reliant des paires de sommets. On numérote les sommets de 0 à n-1. Le graphe est :

  • non orienté si les arêtes n'ont pas de sens ({i, j}) ;
  • orienté si les arcs ont un sens (i -> j j -> i).

Les voisins d'un sommet sont ceux qui lui sont reliés ; le degré d'un sommet est son nombre de voisins. Un graphe peut être pondéré (chaque arête porte un poids : distance, coût).

Exercices du chapitre

La suite du cours · Tous les exercices du chapitre