Ok

En poursuivant votre navigation sur ce site, vous acceptez l'utilisation de cookies. Ces derniers assurent le bon fonctionnement de nos services. En savoir plus.

Recherchez sur le site (cours, livres, Agregation, etc.)

Liens mathématiques divers

Avril 2024

D L M M J V S
1 2 3 4 5 6
7 8 9 10 11 12 13
14 15 16 17 18 19 20
21 22 23 24 25 26 27
28 29 30
Syndicate this site (rss)
Syndicate this site (XML)

Catégories

« L'indicatrice de Carmichael | Page d'accueil | An overview of Babylonian mathematics »

11/12/2010

Graphes

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)=vertGamma^+(x)vert$ le degré sortant ou degré externe de $ x$. 
On note $ d^-(x)=vertGamma^-(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$ où $ 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(nvert Uvert+vert U_fvert)$. 

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+nvert U_rvert+vert U_fvert)$. 

Problèmes ouverts: peut on réaliser la fermeture transitive de $ G$ en $ O(n+vert U_fvert)$ ? La réduction transitive en $ O(n+vert Uvert)$ ? 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

Source : http://www.les-mathematiques.net/a/a/w/node1.php3#556

11:58 Publié dans Graphes | Lien permanent | Commentaires (0) | |  del.icio.us | | Digg! Digg |  Facebook

Les commentaires sont fermés.