Une introduction aux graphes

Dans ce cours, Frédéric, professeur de numérique et sciences informatiques, propose de définir la notion de graphe, puis de l'illustrer par des situations de la vie courante et les problèmes algorithmiques que posent ces situations qui peuvent être traiter à l’aide des graphes. Puis d'étudier les différentes manières de représenter un graphe en informatique ; quelques exercices courts sont proposés sur ce thème. L’exposé se termine, à titre d’exemple, par la programmation d’un algorithme simple de recherche de l’existence d’un chemin entre deux sommets d’un graphe.

Téléchargez le support de cours en PDF.

Définition : graphes, sommets, arêtes, voisins, chemins

Qu’est-ce qu’un graphe ?

Un graphe, c'est :

• des points, appelés sommets ou nœuds,
• des liaisons entre ces points, appelées arêtes ou arcs.

On ne tient pas compte de la position des points, ni de la forme des arêtes, ni des croisements d’arêtes.

Quelques variantes : 

• Certaines arêtes relient un sommet à lui-même.
• Il y a plusieurs arêtes entre deux sommets donnés.
• Les arêtes sont ≪ orientées ≫.
• Les arêtes sont ≪ pondérées (ou valuées) ≫ par un nombre.
• Les sommets sont ≪ colorés ≫.

Vocabulaire

• Sommets voisins (ou adjacents) : deux sommets sont voisins s’il existe une arête qui les relie.
• Chemin dans un graphe : c’est une suite de sommets telle que deux sommets cons´ecutifs sont toujours voisins.

Applications des graphes

Pourquoi s’intéresser aux graphes ?

Ils permettent de schématiser de nombreuses situations et d’étudier les problèmes qu’elles posent ; par exemple (sommets/arêtes) :

• réseau informatique (ordinateurs/connexions), réseau internet (serveurs/connexions), réseau social (membres/liens sociaux) ;
• voies de transports entre lieux géographiques (villes/routes; aéroports/lignes aériennes; stations/métro, etc. ).

Quelques problèmes classiques sur les graphes

• Peut-on relier deux sommets quelconques par un chemin (connexité du graphe) ?
• Pour deux sommets reliables par un chemin, quel chemin passe par le minimum de sommets intermédiaires (plus court chemin dans le métro ou trajet SNCF) ?
• Chemin dans un graphe pondéré qui minimise la somme des poids (itinéraire GoogleMap — poids = distances en km).

Représentation informatique d’un graphe

Comment représenter un graphe en informatique ?

Il y a plusieurs possibilités. Il faut choisir celle qui est la mieux adaptée au problème posé.

• Donner la liste S des sommets et la liste A des arrêtes :
  S=[0,1,2,3,4,5,6]
  A=[[1,3],[3,5],[1,5],[6,5],[5,0],[2,0]]
  → cette représentation s’adapte aussi aux graphes orientés.
• Par une matrice d’adjacence :
  Le coefficient de la ligne i et de la colonne j vaut 1 si les sommets i et j sont voisins, et vaut 0 sinon.
  → cette représentation s’adapte aussi aux graphes orientés.

Comment représenter une matrice en Python ?

Il n’existe pas de type matrice par défaut.

Utiliser une liste de listes :

In [1]: M=[[0, 1, 2], [3, 4, 5], [6, 7, 8]]

In [2]: M[1][0]

Out[2]: 3

Comment représenter un graphe en informatique ?

Par un dictionnaire d’adjacence qui a pour clefs chaque sommet, avec comme valeur associée la liste des voisins de ce sommet.

ADJ={0:[2,5],1:[3,5],2:[0],3:[1,5],4:[], 5:[0,1,3,6],6:[5]}

ADJ[1]→[3,5]

→ cette représentation s’adapte aussi aux graphes orientés.