A lire

Deug/Prépa

Licence

Agrégation
A télécharger

Télécharger

personnes(s) sur le site en ce moment.

B. Malgrange

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

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 muni d'une relation binaire . est un graphe orienté.

On note $\Gamma^+(x)$ l'ensemble des tels que $(x,y) \in U$ ; on l'appelle ensemble des successeurs de .
On note $\Gamma^-(x)$ l'ensemble des tels que $(y,x) \in U$ ; on l'appelle ensemble des prédécesseurs de .
On note $d^+(x)=\vert\Gamma^+(x)\vert$ le degré sortant ou degré externe de .
On note $d^-(x)=\vert\Gamma^-(x)\vert$ le degré entrant ou degré interne de .
Si est appelé une source.
Si est appelé un puits.

Théorème Soit un graphe orienté fini. 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 un graphe orienté fini. est sans circuit si et seulement si il existe une permutation 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()
Début: Pour tout $x \in X$ faire

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 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
Pour chaque successeur de faire
$d^-(y) \leftarrow d^-(y) - 1$
Si alors
Source $\leftarrow$ Source $\cup \{ y \}$ .
Si (Nbsommets) alors est sans circuit sinon a au moins un circuit.

La complexité de cet algorithme est avec le nombre de sommets et 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 est une permutation de 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()
Pour tout $x \in X$ calculer (comme dans l'algorithme précédent)
$S \leftarrow \emptyset$
Pour tout $x \in X$ faire:
si 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 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

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).
est le nombre de tri topologiques, le nombre de sommets, le nombre d'arcs.

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

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 faire
$\bullet\$ $\bullet\$ $\bullet\$ ajouter() au niveau 0.
$\bullet\$ $\bullet\$ $\bullet\$ nb-sommets++
$\bullet\$ $i \leftarrow 0$
$\bullet\$ Tant que niveau() est non vide faire
$\bullet\$ $\bullet\$ Pour tout dans niveau() faire
$\bullet\$ $\bullet\$ $\bullet\$ pour tout successeur de faire $\bullet\$ $\bullet\$ $\bullet\$ $\bullet\$ $d^-(y) \leftarrow d^-(y) - 1$
$\bullet\$ $\bullet\$ $\bullet\$ $\bullet\$ Si alors
$\bullet\$ $\bullet\$ $\bullet\$ $\bullet\$ $\bullet\$ niveau() $\leftarrow$ niveau() $\cup \{ y \}$
$\bullet\$ $\bullet\$ $\bullet\$ $\bullet\$ $\bullet\$ nb-sommets $\leftarrow$ nb-sommets
$\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 .
La complexité est en .

Un chemin sur un graphe est un n-uplet tel que $\forall i (x_i,x_{i+1}) \in U$ .
Soit un graphe orienté, la fermeture transitive de est définie par $(x,y) \in U_f$ si et seulement si il existe un chemin de avec et .
Soit un graphe orienté avec $X=\{1,...,k\}$ et $X_0=\emptyset$ .
Soit $\mu=(x_1,...,x_l)$ un chemin de , 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 de la manière suivante: $(x,y) \in U_k$ si et seulement si il existe un chemin entre et avec $I(c) \subset X_k$ . En particulier $G_0=G \cup \{ (x,x) \vert x \in X \}$ , et .

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 variant de à faire $a_{i,i} \leftarrow 1$
$\bullet\$ Pour variant de à faire
$\bullet\$ $\bullet\$ Pour variant de à faire
$\bullet\$ $\bullet\$ $\bullet\$ Pour variant de à 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 .

Soit un graphe orienté, est une réduction transitive de si $U_r \subset U$ , n'a pas de transitivité et .
La réduction transitive n'est pas toujours unique.
Si 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() $\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 (,file)
$\bullet\$ $\bullet\$ $\bullet\$ Pour tout $z \in \Gamma^+(y)$ faire
$\bullet\$ $\bullet\$ $\bullet\$ $\bullet\$ Si marque()faux alors
$\bullet\$ $\bullet\$ $\bullet\$ $\bullet\$ $\bullet\$ marque() $\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() $\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() $\leftarrow$ faux
$\bullet\$ On classe les points dans l'ordre d'un tri topologique $\tau=(x_1,x_2,...,x_n)$
$\bullet\$ Pour variant de à 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ù 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() $\leftarrow$ vrai
$\bullet\$ $\bullet\$ $\bullet\$ $\bullet\$ Pour tout $y \in \Gamma^+_f(x)$ faire
$\bullet\$ $\bullet\$ $\bullet\$ $\bullet\$ $\bullet\$ si non(marque()) alors
$\bullet\$ $\bullet\$ $\bullet\$ $\bullet\$ $\bullet\$ $\bullet\$ marque() $\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() $\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 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)