Structures de données : graphes

Structures de données : graphes

Benjamin Monmege

Exemples d’utilisation des graphes

Réseau routier


Réseau routier : avec sens interdits


Internet


Réseaux sociaux


Jeux : graphe des configurations


Graphe de dépendances


Graphe de prérequis


Définition d’un graphe

Graphe orienté

Un graphe orienté est la donnée :

  • d’un ensemble S de sommets

  • et d’un ensemble A d’arcs, chaque arc étant un couple (u, v) de deux sommets (possiblement les deux mêmes), parfois noté u → v : u est la source de l’arc et v sa destination

Un chemin est une suite de sommets u0, u1, …, uk (avec k ≥ 0) reliés par des arcs, c’est-à-dire telle que ui → ui + 1 pour tout i ∈ {0, …, k − 1}.

Relation

Un graphe orienté permet de représenter une relation entre des éléments d’un ensemble fini :

  • relation de parenté
  • relation d’amitié (pas forcément réciproque)
  • relation d’ordre sur l’âge…

Graphe non orienté

Si les flèches ne sont pas importantes pour modéliser le problème, on utilise plutôt un graphe non orienté :

  • il est composé d’un ensemble A d’arêtes, chaque arête étant une paire {u, v} de deux sommets distincts.

On parle alors de chaîne plutôt que de chemin.

Représentation d’un graphe

Matrice d’adjacence


Liste de successeurs : dictionnaire Python


Il existe aussi une représentation par liste de prédécesseurs: il faut choisir la meilleure des représentations selon le problème à résoudre sur les graphes…

Arbre comme sous-graphe

Connexité

  • Une composante connexe d’un graphe non orienté est un ensemble maximal de sommets tous reliés les uns aux autres par un chemin.
  • Un graphe peut se décomposer de manière unique en un ensemble de composantes connexes.
  • Un graphe est dit connexe s’il ne possède qu’une unique composante connexe.


Une notion similaire existe pour les graphes orientés : la forte connexité

Acyclicité

  • Un circuit dans un graphe non orienté est une chaîne partant et arrivant dans le même sommet. On parle de cycle dans un graphe orienté.
  • Un graphe est dit acyclique s’il ne possède aucun circuit/cycle.

Caractérisation des arbres

Tout graphe connexe et acyclique est un arbre…

… au sens où on peut choisir n’importe quel sommet comme racine et obtenir un arbre d’arité non borné en considérant ses voisins, puis les voisins de ses voisins, etc.