Liste des algorithmes de la théorie des graphes

Un article de Wikipédia, l'encyclopédie libre.

Vous avez de nouveaux messages (diff^?).

Sommaire

1 Algorithmes importants de la théorie des graphes
2 Une présentation unifiée de quelques algorithmes

[modifier] Algorithmes importants de la théorie des graphes

[modifier] Algorithmes de parcours d'un graphe

Algorithme de parcours en largeur (ou BFS: Breadth first search)
Algorithme de parcours en profondeur (ou DFS: Depth First Search)
Algorithme de parcours en largeur lexicographique (ou Lex-BFS)

[modifier] Algorithmes de Plus Courts Chemins (PCC)

[modifier] Algorithmes d'arbres couvrants de poids minimum

[modifier] Algorithmes de construction d'une forêt maximale

Algorithme de construction d'une forêt maximale

[modifier] Lemme de Minty

Lemme de Minty

[modifier] Algorithmes pour les flots maximums

Algorithme de Ford-Fulkerson
Algorithme de Roy

[modifier] Algorithmes pour les flots à coût minimum

Algorithme de Busacker-Gowen
Algorithme de Klein

[modifier] Algorithmes pour les flots compatibles

Algorithme de recherche de flots compatibles

[modifier] Algorithmes de coloration

(voir coloration de graphe)

[modifier] Algorithmes divers

Algorithme du plus proche voisin
Algorithmes de connexité
Algorithme de détermination des composantes Biconnexes
Algorithmes de forte connexité

[modifier] Une présentation unifiée de quelques algorithmes

[modifier] Q-semi anneau

Un Q-semi anneau est un triplet $(Q,\oplus,\otimes)$ , Q étant un ensemble non vide, $\oplus$ et $\otimes$ deux lois binaires internes. A tout couple (a,b) d'éléments de Q, les relations binaires associent un élément de Q noté respectivement $a\oplus b$ et $a \otimes b$ . La loi $\oplus$ est associative, commutative et admet un élément neutre z. La loi $\otimes$ est associative et distributive par rapport à $\oplus$ . Elle admet un élément neutre e (à gauche et à droite).

[modifier] Exemple

L'algèbre de Boole est un Q-semi anneau en prenant Q={0,1}, $\oplus=\vee$ (ou) et $\otimes=\wedge$ (et). Les éléments neutres sont z=0 et e=1.

[modifier] Matrice associée à un graphe

Etant donné un graphe, on associe à chaque arc un poids qui pourra être une longueur au sens de la théorie des graphes, une distance (au sens métrique), une densité de trafic maximum, ... Dans chacun de ces cas, l'ensemble Q sera choisi différemment, pouvant être l'ensemble {0,1}, $\mathbb{R}_+$ , ... On construit alors une matrice A associée au graphe en associant à chaque arc (i,j) l'élément (i,j) de la matrice égal à son poids si l'arc existe et à z s'il n'existe pas.

[modifier] Chemin optimal

Soit un chemin de longueur d, $(X k 0, X k 1)$ , $(X k 1, X k 2)$ , ... , $(X k d - 1, X k d)$ . A chaque arc $(X k p, X k p + 1)$ on a associé le poids $a k p, k p + 1$ et le poids du chemin est par définition $a_{k0,k1}\oplus a_{k1,k2}\oplus \ldots \oplus a_{kd-1,kd}.$

On définit sur le Q-semi anneau une relation d'ordre $\gg$ par $a \gg b$ si et seulement si $a\oplus b = a$ . On suppose que la relation d'ordre est totale, donc on a soit $a \oplus b=a$ soit $a \oplus b=b$ . On peut alors dire qu'un chemin de $X k 0$ à $X k d$ de poids w est supérieur à un autre chemin de $X k 0$ à $X k d$ de poids w' si l'on a $w \gg w'$ . Un chemin est optimal s'il est supérieur à tout autre chemin de $X k 0$ à $X k d$ . Il peut en exister plusieurs.

[modifier] Algorithme de Warshall généralisé

P. Robert et J. Ferland ont montré que, étant donné un graphe de matrice associée $A$ d'ordre $n$ , on peut définir :

une suite de matrices $A (k)$ par :

A (0) = A

$A^{(k)}=\left(a_{i,j}^{(k)}\right)$ avec $a_{i,j}^{(k)}=a_{i,j}^{(k-1)}\oplus \left(a_{i,k}^{(k-1)}\otimes a_{k,j}^{(k)}\right)$ .

Cette suite de matrices est telle que les éléments $a_{i,j}^{(n)}$ de la matrice

A (n)

sont égaux au poids du chemin de

X i

X j

une autre suite de matrices $D (k)$ par :

$d_{i,j}^{(0)} = \left\{\begin{matrix} j & \mbox{ si } a_{i,j}^{(0)} \neq z \\ 0 & \mbox{ autrement dans } D^{(0)} \end{matrix}\right.$

$d_{i,j}^{(k)} = \left\{\begin{matrix} d_{i,j}^{(k-1)} & \mbox{ si } a_{i,j}^{(k)} = a_{i,j}^{(k-1)} \\ d_{i,k}^{(k-1)} & \mbox{ sinon } \end{matrix}\right.$

Cette suite de matrices est telle que les éléments $d_{i,j}^{(k)}$ ont pour valeur l'indice du premier point intermédiaire du chemin de

X i

X j

à l'étape

k

Il s'ensuit que :

$d_{i,j}^{(n)}$ est l'indice $p$ du premier sommet intermédiaire entre $X i$ et $X j$ .
Le second sommet est donné par $d_{p,j}^{(n)}$ où $p=d_{i,j}^{(n)}$ , etc.
On détermine ainsi de proche en proche les divers sommets jusqu'au sommet terminal choisi.

[modifier] Applications

[modifier] Détermination des chemins joignant un sommet

On prend l'algèbre de Boole Q={0,1}, $\oplus=\vee$ et $\otimes=\wedge$ . A chaque arc reliant $X i$ à $X j$ on affecte le poids 1 et 0 s'il n'existe pas. Après calcul de $A (n)$ , il existe un chemin entre $X i$ et $X j$ si le coefficient $a i, j$ est non nul. Le chemin n'existe pas si le coefficient est nul.

[modifier] Détermination des chemins à densité de trafic maximum entre deux sommets

On prend $Q=\mathbb{R}_+$ , $\oplus$ =maximum de deux réels, $\otimes$ =minimum de deux réels. On affecte à chaque arc $(X i, X j)$ la densité de trafic maximum si elle existe et 0 autrement. Après le calcul de $A (n)$ , à l'intersection de la ligne i et de la colonne j, $a_{i,j}^{(n)}$ représente la densité de trafic maximum entre i et j.

[modifier] Détermination de la distance minimum entre deux sommets

On prend $Q=\mathbb{R}_+$ , $\oplus$ =minimum de deux réels, $\otimes$ =addition des réels. $a_{i,j}^{(n)}$ représente la distance minimum entre i et j.

Récupérée de « http://fr.wikipedia.org../../../l/i/s/Liste_des_algorithmes_de_la_th%C3%A9orie_des_graphes.html »

Catégories : Liste en rapport avec les mathématiques • Théorie des graphes • Algorithme de la théorie des graphes