Les-Mathematiques.net - Cours de mathématiques universitaires - Forum - Cours à télécharger

A lire
Deug/Prépa
Licence
Agrégation
A télécharger
Télécharger
144 personne(s) sur le site en ce moment
E. Cartan

Les maths pour l'agreg

A lire
Articles
Math/Infos
Récréation
A télécharger
Télécharger
Théorème de Cantor-Bernstein
Théo. Sylow
Théo. Ascoli
Théo. Baire
Loi forte grd nbre
Nains magiques
 
 
 
 
 
Graphes next up previous index
suivant: Index monter: aaw précédent: aaw   Index

Graphes

On s'intéresse ici au cas le plus général d'un ensemble $ X$ muni d'une relation binaire $ U$. $ (X,U)$ est un graphe orienté.

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)=\vert\Gamma^+(x)\vert$ le degré sortant ou degré externe de $ x$.
On note $ d^-(x)=\vert\Gamma^-(x)\vert$ 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.

Théorème 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.

Théorème 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$ $ G_i=G[\{x_i,...,x_n\}]$.

Ci-dessous un algorithme déterminant si oui ou non un graphe est sans circuit ou non.
Le codage machine employé consiste en une liste de successeurs pour chaque sommet.

Procédure sans-circuit($ G$)
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 privé de $ \{ 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.

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:

Procédure Tri-topologique($ G$)
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:

Tri-topo( $ G,S,\sigma$)
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) * \vert L(G) \vert)$.
Il existe des algorithmes de complexité $ O(n*\vert L(G)\vert)$ (beaucoup plus compliqués).
$ L(G)$ est le nombre de tri topologiques, $ n$ le nombre de sommets, $ m$ le nombre d'arcs.

On considère maintenant un graphe $ G=(X,U)$ orienté et sans circuits. On pose $ h(x)=0$ si $ d^-(x)=0$ et $ h(x)=max \{ h(y) \vert (y,x) \in U \} +1$ sinon; $ h(x)$ est appelé hauteur de $ x$.

Algorithme de construction des niveaux du graphe; un niveau est de la forme $ X_i=\{ x \in X \vert h(x)=i \}$:
$ \bullet\ $Calculer les degrés internes.
$ \bullet\ $nb-sommets=0
$ \bullet\ $Pour tout $ x \in X$ faire
$ \bullet\ $$ \bullet\ $Si $ d^-(x)=0$ faire
$ \bullet\ $$ \bullet\ $$ \bullet\ $ajouter($ x$) au niveau 0.
$ \bullet\ $$ \bullet\ $$ \bullet\ $nb-sommets++
$ \bullet\ $ $ i \leftarrow 0$
$ \bullet\ $Tant que niveau($ i$) est non vide faire
$ \bullet\ $$ \bullet\ $Pour tout $ x$ dans niveau($ i$) faire
$ \bullet\ $$ \bullet\ $$ \bullet\ $pour tout $ y$ successeur de $ x$ faire $ \bullet\ $$ \bullet\ $$ \bullet\ $$ \bullet\ $ $ d^-(y) \leftarrow d^-(y) - 1$
$ \bullet\ $$ \bullet\ $$ \bullet\ $$ \bullet\ $Si $ d^-(y)=0$ alors
$ \bullet\ $$ \bullet\ $$ \bullet\ $$ \bullet\ $$ \bullet\ $niveau($ i+1$) $ \leftarrow$ niveau($ i+1$) $ \cup \{ y \}$
$ \bullet\ $$ \bullet\ $$ \bullet\ $$ \bullet\ $$ \bullet\ $nb-sommets $ \leftarrow$ nb-sommets $ +1$
$ \bullet\ $$ \bullet\ $ $ i \leftarrow i + 1$

Il y a des circuits si et seulement si à la fin de l'algorithme nb-sommets est différent de $ n$.
La complexité est en $ O(n+m)$.

Un chemin sur un graphe $ G=(X,U)$ est un n-uplet $ (x_1,...,x_k)$ tel que $ \forall i (x_i,x_{i+1}) \in U$.
Soit $ G=(X,U)$ un graphe orienté, la fermeture transitive $ G_f=(X,U_f)$ de $ G$ est définie par $ (x,y) \in U_f$ si et seulement si il existe un chemin $ (x_1,...,x_k)$ de $ G$ avec $ x=x_1$ et $ y=x_k$.
Soit $ G=(X,U)$ un graphe orienté avec $ X=\{1,...,k\}$ et $ X_0=\emptyset$.
Soit $ \mu=(x_1,...,x_l)$ un chemin de $ G$, l'intérieur de $ \mu$, noté $ I(\mu)$, est $ \{x_2,...,x_{l-1} \}$. $ I(\mu)=\emptyset$ si et seulement si $ l \leq 2$.
On définit une suite de graphes $ G_k=(X,U_k)$ de la manière suivante: $ (x,y) \in U_k$ si et seulement si il existe un chemin $ c$ entre $ x$ et $ y$ avec $ I(c) \subset X_k$. En particulier $ G_0=G \cup \{ (x,x) \vert x \in X \}$, et $ G_n=G_f$.

Lemme: $ (i,j) \in U_k \iff ( (i,j) \in U_{k-1} \lor ( (i,k) \in U_{k-1} \land (k,j) \in U_{k-1} ) )$

On déduit de ce lemme un algorithme destiné à déterminer la fermeture transitive d'un graphe, l'algorithme de Roy-Warshall:
$ \bullet\ $ $ a \leftarrow g$
( on initialise la matrice avec le graphe)
$ \bullet\ $Pour $ i$ variant de $ 1$ à $ n$ faire $ a_{i,i} \leftarrow 1$
$ \bullet\ $Pour $ k$ variant de $ 1$ à $ n$ faire
$ \bullet\ $$ \bullet\ $Pour $ i$ variant de $ 1$ à $ n$ faire
$ \bullet\ $$ \bullet\ $$ \bullet\ $Pour $ j$ variant de $ 1$ à $ n$ faire
$ \bullet\ $$ \bullet\ $$ \bullet\ $$ \bullet\ $ $ a_{i,j} \leftarrow a_{i,j} \lor ( a_{i,k} \land a_{k,j} )$

On peut constater que l'on n'applique pas exactement le lemme, car les $ a_{i,j}$ ne sont pas les bons, mais l'on peut aussi montrer que l'algorithme fonctionne tout de même.

La complexité de l'algorithme de Roy-Warshall est $ O(n^3)$.

Soit $ G=(X,U)$ un graphe orienté, $ G_r=(X,U_r)$ est une réduction transitive de $ G$ si $ U_r \subset U$, $ G_r$ n'a pas de transitivité et $ (G_r)_f=G_f$.
La réduction transitive n'est pas toujours unique.
Si $ G=(X,U)$ est un graphe orienté sans circuit, il a une unique réduction transitive appelé graphe de Hasse.

Algorithme général de calcul d'une fermeture transitive (pas seulement dans le cas d'un graphe sans circuit).
$ \bullet\ $Pour $ x \in X$ faire
$ \bullet\ $$ \bullet\ $marque($ x$) $ \leftarrow$ faux
$ \bullet\ $$ \bullet\ $ $ \Gamma^+_f(x) \leftarrow \emptyset$
$ \bullet\ $Pour tout $ x \in X$ faire
$ \bullet\ $$ \bullet\ $file $ \leftarrow \{ x \}$
$ \bullet\ $$ \bullet\ $tant que file $ \neq \emptyset$ faire
$ \bullet\ $$ \bullet\ $$ \bullet\ $ $ y \leftarrow $ premier(file)
$ \bullet\ $$ \bullet\ $$ \bullet\ $supprimer ($ y$,file)
$ \bullet\ $$ \bullet\ $$ \bullet\ $Pour tout $ z \in \Gamma^+(y)$ faire
$ \bullet\ $$ \bullet\ $$ \bullet\ $$ \bullet\ $Si marque($ y$)$ =$faux alors
$ \bullet\ $$ \bullet\ $$ \bullet\ $$ \bullet\ $$ \bullet\ $marque($ z$) $ \leftarrow$ vrai
$ \bullet\ $$ \bullet\ $$ \bullet\ $$ \bullet\ $$ \bullet\ $marque( $ \Gamma^+_f(x) \leftarrow \Gamma^+_f(x) \cup \{ z \}$)
$ \bullet\ $$ \bullet\ $$ \bullet\ $$ \bullet\ $$ \bullet\ $file $ \leftarrow$ file $ \cup$ { z }
$ \bullet\ $$ \bullet\ $Pour tout $ z \in Gamma^+_f(x)$ faire
$ \bullet\ $$ \bullet\ $$ \bullet\ $marque($ x$) $ \leftarrow faux$

Le coût de cet algorithme est $ O(n\vert U\vert+\vert U_f\vert)$.

On cherche maintenant à déterminer à la fois la fermeture et la réduction transitive dans un graphe sans circuit.
L'algorithme employé est l'algorithme de Goralcicova-Koubek.

$ \bullet\ $Pour tout $ x \in X$ faire
$ \bullet\ $$ \bullet\ $ $ \Gamma^+_f(x) \leftarrow \emptyset$
$ \bullet\ $$ \bullet\ $ $ \Gamma^+_r(x) \leftarrow \emptyset$
$ \bullet\ $$ \bullet\ $marque($ x$) $ \leftarrow$ faux
$ \bullet\ $On classe les points dans l'ordre d'un tri topologique $ \tau=(x_1,x_2,...,x_n)$
$ \bullet\ $Pour $ i$ variant de $ n$ à $ 1$ faire
$ \bullet\ $$ \bullet\ $ $ S \leftarrow \Gamma^+(x_i)$
$ \bullet\ $$ \bullet\ $Tant que $ S \neq \emptyset$
$ \bullet\ $$ \bullet\ $$ \bullet\ $ $ x \leftarrow min_{\tau}(S)$
$ \bullet\ $$ \bullet\ $$ \bullet\ $Si non(marque(X)) alors
(cas où $ (x_i,x)$ n'est pas un arc de transitivité)
$ \bullet\ $$ \bullet\ $$ \bullet\ $$ \bullet\ $ $ \Gamma^+_r(x_i) \leftarrow \Gamma^+_r(x_i) \cup \{ x \}$
$ \bullet\ $$ \bullet\ $$ \bullet\ $$ \bullet\ $ $ \Gamma^+_f(x_i) \leftarrow \Gamma^+_f(x_i) \cup \{ x \}$
$ \bullet\ $$ \bullet\ $$ \bullet\ $$ \bullet\ $marque($ x$) $ \leftarrow$ vrai
$ \bullet\ $$ \bullet\ $$ \bullet\ $$ \bullet\ $Pour tout $ y \in \Gamma^+_f(x)$ faire
$ \bullet\ $$ \bullet\ $$ \bullet\ $$ \bullet\ $$ \bullet\ $si non(marque($ y$)) alors
$ \bullet\ $$ \bullet\ $$ \bullet\ $$ \bullet\ $$ \bullet\ $$ \bullet\ $marque($ y$) $ \leftarrow$ vrai
$ \bullet\ $$ \bullet\ $$ \bullet\ $$ \bullet\ $$ \bullet\ $$ \bullet\ $ $ \Gamma^+_f(x_i) \leftarrow \Gamma^+_f(x_i) \cup \{ y \}$
$ \bullet\ $$ \bullet\ $$ \bullet\ $$ \bullet\ $ $ S \leftarrow S \setminus \{ x \}$
$ \bullet\ $$ \bullet\ $Pour tout $ y \in \Gamma^+_f(x_i)$ faire
$ \bullet\ $$ \bullet\ $$ \bullet\ $marque($ y$) $ \leftarrow$ faux

La complexité est en $ O(n+n\vert U_r\vert+\vert U_f\vert)$.

Problèmes ouverts: peut on réaliser la fermeture transitive de $ G$ en $ O(n+\vert U_f\vert)$ ? La réduction transitive en $ O(n+\vert U\vert)$ ? Comment détecter qu'un graphe est fermé transitivement ? Réduit transitivement ? (probablement faisable en temps linéaire)


next up previous index
suivant: Index monter: aaw précédent: aaw   Index
C_antonini,J-F_Quint,P_Borgnat,J_Bérard,E_Lebeau,E_Souche,A_Chateau,O_Teytaud
 

 
©Emmanuel Vieillard Baron 01-01-2001
Adresse Mail:

Inscription
Désinscription

Actuellement 16057 abonnés
Qu'est-ce que c'est ?
Taper le mot à rechercher

Mode d'emploi
En vrac

Faites connaître Les-Mathematiques.net à un ami
Curiosités
Participer
Latex et autres....
Collaborateurs
Forum

Nous contacter

Le vote Linux

WWW IMS
Cut the knot
Mac Tutor History...
Number, constant,...
Plouffe's inverter
The Prime page