image
Introduction aux graphes.

Graphes

Les graphes sont des outils indispensables en informatique; par exemple, les graphes acycliques (le terme anglais direct acyclic graphs sera plus facile à trouver sur www) sont très utiles en compilation et en optimisation de code. Les graphes sont aussi le support de ce que l’on appelle les réseaux bayésiens, utilisés pour la modélisation statistique. Ils servent aussi à l’étude des réseaux, dont Internet; en particulier, on s’intéresse souvent dans ce cas aux graphes aléatoires. La recherche d’un tri topologique est importante aussi en mathématiques appliquées, pour l’optimisation multi-objectifs par exemples. Enfin, la recherche de plus court chemin sur un graphe, sous des formes très variées, a un vaste réseau d’applications. On pourra trouver une introduction aux graphes et aux algorithmes qui les concernent dans [GM].

(Graphe orienté).
Un graphe orienté est la donnée d’un couple \((X,U)\)\(X\) est un ensemble muni d’une relation binaire \(U\). Les éléments de \(X\) sont appelés les sommets du graphe et les éléments de \(U\) sont appelés les arcs du graphe.
On note \(\Gamma^+(x)\) l’ensemble des \(y\) tels que \((x,y) \in U\); on l’appelle ensemble des successeurs de \(x\).
On note \(\Gamma^-(x)\) l’ensemble des \(y\) tels que \((y,x) \in U\); on l’appelle ensemble des prédécesseurs de \(x\).
On note \(d^+(x)=|\Gamma^+(x)|\) le degré sortant ou degré externe de \(x\).
On note \(d^-(x)=|\Gamma^-(x)|\) le degré entrant ou degré interne de \(x\).
Si \(d^-(x)=0\) \(x\) est appelé une source.
Si \(d^+(x)=0\) \(x\) est appelé un puits.
(Graphe orienté sans circuit).
Un graphe orienté \((X,U)\) est dit sans circuit s’il n’existe pas de cycle formé par des arcs \((x_1,x_2), \ldots , (x_{n-1},x_n), (x_n, x_1)\). En anglais on parle de DAG (directed acyclic graph).
Soit \(G=(X,U)\) un graphe orienté fini. \(G\) est sans circuit si et seulement si les deux énoncés suivants sont vérifiés:
\(\bullet\)\(\exists x \in X \ d^-(x)=0\).
\(\bullet\)\(\forall x \in X \ d^-(x)=0 \Longrightarrow G \setminus \{x\}\) est sans circuit.
Soit \(G=(X,U)\) un graphe orienté fini. \(G\) est sans circuit si et seulement si il existe une permutation \((x_1,x_2,...,x_n)\) des sommets tels que \(d_{G_i}^-(x_i)=0\), avec \(G_i=G[\{x_i,...,x_n\}]\).

Voici un algorithme déterminant si oui ou non un graphe est sans circuit ou non. La structure de données employée consiste en une liste de successeurs pour chaque sommet.


Début :
Pour tout \(x \in X\) faire
\(d^-(x)=0\)
Pour tout \(x \in X\) faire
Pour tout \(y \in \Gamma^+(x)\) faire
\(d^-(y) \leftarrow d^-(y) + 1\)
\(Source \leftarrow \emptyset\)
\(Nbsommets \leftarrow 0\)
Pour tout \(x \in X\) faire
Si \(d^-(x)=0\) alors \(Source \leftarrow Source \cup \{x\}\).
Tant que \(Source \neq \emptyset\) faire
\(x \leftarrow choix(Source)\)
\(Source \leftarrow Source\backslash \{ x \}\)
\(Nbsommets \leftarrow Nbsommets +1\)
Pour chaque successeur \(y\) de \(x\) faire
\(d^-(y) \leftarrow d^-(y) - 1\)
Si \(d^-(y)=0\) alors
\(Source \leftarrow Source \cup \{ y \}\).
Si (\(Nbsommets=n\)) alors \(G\) est sans circuit sinon \(G\) a au moins un circuit.


La complexité de cet algorithme est \(O(n+m)\) avec \(n\) le nombre de sommets et \(m\) le nombre d’arcs. \(Source\) peut être implémentée sous forme de liste, avec pour fonction de choix la fonction simplissime qui choisit le premier élément.

(Tri topologique).
Un tri topologique d’un graphe orienté sans circuit \(G=(X,U)\) est une permutation \((x_1,x_2,...,x_n)\) de \(X\) telle que \((x_i,x_j) \in U \Longrightarrow i < j\).

Notons que la permutation calculée par l’algorithme précédent (ie. l’ordre de sortie de \(Source\)) est un tri topologique.

L’algorithme suivant sert à engendrer tous les tris topologiques:

Pour tout \(x \in X\)
Calculer \(d^-(x)\) (comme dans l’algorithme précédent)
\(S \leftarrow \emptyset\)
Pour tout \(x \in X\) faire
Si \(d^-(x)=0\) alors \(S \leftarrow S \cup \{ x \}\)
\(\sigma \leftarrow \emptyset\)
Tri-topo(\(G,S,\sigma\))


avec la procédure récursive Tri-topo suivante :


Si \(S=\emptyset\) alors écrire \(\sigma\) sinon
Pour tout \(x \in S\) faire
\(S' \leftarrow S - \{ x \}\)
\(\sigma \leftarrow \sigma . x\) (concaténation)
Pour tout \(y \in \Gamma^+(x)\) faire
\(d^-(y) \leftarrow d^-(y) - 1\)
Si \(d^-(y)=0\) alors
\(S' \leftarrow S' \cup \{ y \}\)
Tri-topo(\(G,S',\sigma\))
Pour tout \(y \in \Gamma^+(x)\) faire
\(d^-(y) \leftarrow d^-(y) - 1\)
\(\sigma \leftarrow \sigma\) privé de \(x\)


La complexité est en \(O((n+m) * | L(G) |)\), où \(L(G)\) est le nombre de tri topologiques, \(n\) est le nombre de sommets, \(m\) est le nombre d’arcs.

Il existe des algorithmes de complexité \(O(n*|L(G)|)\) (beaucoup plus compliqués).

Pour aller plus loin, le lecteur est encouragé à consulter [BOU].

Bibliographie


Barre utilisateur

[ID: 43] [Date de publication: 25 avril 2021 20:21] [Catégorie(s): Le cours d'agrégation ] [ Nombre commentaires: 0] [nombre d'éditeurs: 1 ] [Editeur(s): Emmanuel Vieillard-Baron ] [nombre d'auteurs: 5 ] [Auteur(s): Christophe Antonini Olivier Teytaud Pierre Borgnat Annie Chateau Edouard Lebeau ]




Commentaires sur le cours

Documents à télécharger