Graphe valué sur les arêtes

Algorithmes de référence : Graphe valué sur les arêtes

Définitions et notations :
Un graphe G=(V,E) est dit valué sur les arêtes (GVA) quand il existe une application de E vers ℝ.
Un chemin est dit élémentaire quand il ne contient pas plusieurs fois le même sommet (càd il ne contient pas de circuit).
Un chemin entre deux sommets x et y d'un GVA est dit minimal quand il n'existe aucun autre chemin entre x et y dont la somme des valuations d'arêtes est plus petite.
Un arbre recouvrant d'un GVA est dit minimal (ARM) quand il n'existe aucun arbre recouvrant du graphe dont la somme des valuations d'arêtes est plus petite.
Un chemin élémentaire entre deux sommets x et y d'un GVA est dit maximal quand il n'existe aucun autre chemin entre x et y dont la somme des valuations d'arêtes est plus grande.
Différence de vocabulaire entre concepts de graphe : non-orienté / orienté, arête / arc, sommet pendant / source ou puits, arbre / arborescence, chaine / chemin, cycle / circuit, connexe / fortement connexe. Les notions des graphes non-orientés peuvent être utilisées pour des graphes orientés (réciproque invalide).

algorithme DIJKSTRA
Donnée : un graphe orienté G=(V,E) avec une valuation positive valp : E→ℝ⁺. Un sommet x_o de G.
Résultat : une application VMC donnant la valeur du chemin minimal entre chaque sommet et x_o. L'arborescence A=(V,F) de chemins optimaux correspondante : xy∈F ssi Pred[y]=x.

// Initialisation
Atteint← {x_o};
vmc(x_o)← 0;
Pourchaque sommet x≠x_o faire

Si x∈Succ(x_o)

alors VMC(x)← valp(x_ox); Pred[x]← x_o
sinon VMC(x)← +∞.

// Traitement
Tantque Atteint≠V faire

// Choix faisable en O(n) :
Choisir dans X−Atteint un sommet y de valp(y) minimum;
Atteint← Atteint+{y};
Pourchaque z dans Succ(y)−Atteint tel que VMC(y)+valp(yz)<VMC(z) faire

VMC(z)← VMC(y)+valp(yz);
Pred[z]← y.

Complexité en O(n²) avec Choisir effectué en O(n). On pourrait arriver à O(m lg(n)) avec d'autres structures de données.

algorithme PRIM
Donnée : un graphes non-orienté connexe G=(V,E) et une valuation des arêtes val.
Résultat : un ARM A=(V,F).

// Initialisation
Choisir x_o∈V;
Atteint← {x_o};
F← ∅;
minval← 0; Pourchaque x≠x_o faire

Si x_ox∈E

alors VMC(x)← val(x_ox); Pred[x]← x_o;
sinon VMC(x)← +∞

// Traitement
Tantque Atteint≠V faire

Choisir x∈Atteint et y∈X−Atteint tels que val(xy) soit minimale;
Atteint← Atteint+{y};
F← F∪{xy};
minval← minval+val(xy);
Pourchaque yz∈E tel que z∉Atteint faire

Si valp(yz)<VMC(z) alors

VMC(z)← valp(yz);
Pred[z]← y.

Complexité : O(n²).

N.B. Cet algorithme est structurellement identique à celui de DIJKSTRA pour le chemin minimal, au calcul de VMC et F près. Plus généralement, le problème de l'ARM est structurellement équivalent au problème du chemin minimal.

algorithme KRUSKAL
Donnée : un graphes non-orienté G=(V,E) et une valuation des arêtes val.
Résultat : un ARM A=(V,F).

Trier les arêtes de E par valuation croissante dans un tableau T;
Initialiser une partition P composée des n singletons de V;
F← ∅;
Tantque F contient moins de n−1 arêtes faire

Prendre dans T l'arête suivante xy;
Si les classes de x et y dans P sont différentes alors

fusionner les classes de x et de y;
F← F∪{xy}.

Complexité : en O(m lg(n)). Dépend de l'implémentation de T, P, et F.

Création et tri du tableau T en O(m lg(m)). Modélisation de T par un tas, choix et suppression de l'arête de moindre valeur en O(lg(m)).
Partition P initialisée en O(n). Et choix alternatif privilégiant l'obtention du représentant d'une classe en O(1) sur la réunion de deux parties en O(n), ou l'inverse en respectivement O(lg(n)) et O(1).
Gestion de F par une liste chainée permettant l'ajout d'une arête en O(1).
N.B. O(lg(m))=O(lg(n)), avec lg logarithme en base 2.

schéma algorithmique SOLLIN
Donnée : un graphes non-orienté G=(V,E) et une valuation des arêtes val.
Résultat : un ARM.

Chaque sommet de V forme un sous-arbre isolé;
Tantque cette forêt ne forme pas un arbre faire

Choisir une arête incidente de valeur minimale à un des sous-arbres;
Ajouter cette arête à ce sous-arbre.

Complexité : meilleure que celle de Kruskal ?

N.B. dans le cas où toutes les valuations d'arêtes ont la même valeur, la donnée de ces algorithmes est ramenée à un graphe non valué.

Définitions et notations :
Un flot associé à un GVA G=(V,E,cmax) est une fonction f : E→ℝ associée à une source s et un puits p de G et telle que ∀e∈E f(e)≤cmax(e) et f(e)=−f(ē), et ∀x∈V−{s,p} Σ_y∈V f(xy)=0.
ē dénote l'arc symétrique de e (càd ē=yx quand e=xy). cmax est la capacité maximale de chaque arc.
f est dit maximal quand il n'existe pas d'autre flot pour lequel f(sp) est plus grand.

algorithme Ford-Fulkerson
Donnée : un graphes orienté G=(V,E) et une valuation rationnelle positive des arêtes cmax : E→ℚ⁺, deux sommets s et p de G.
Résultat : un flot f maximal de s à p.

// Création d'un graphe d'écart GE=(X,F,cmax)
F← E;
Pour a∈F faire

f(a)← 0;
val(a)← cmax(a);

// Améliorer le flot
Tantque il existe un chemin H dans F faire

// augmenter le flot
Pourchaque a∈H faire

// arc "avançant"
Si a∈E alors f(a)← f(a)+min(val(e) | e∈H);
// arc "reculant"
Si ā∈E alors f(a)← f(a)−min(val(e) | e∈H);

// Mise à jour du graphe d'écart
Pour a∈H faire

Si ā∈E alors

e← ā;

Si a∈E alors

e← a;
F← F−{a};

Si f(e)<cmax(e) alors

F←F∪{e};
val(e)← cmax(e)−f(e);

Si f(e)>0 alors

F←F∪{ē};
val(ē)← f(e);

Complexité : O(n m²).