Plan
.65@percent
-
Composantes fortement connexes -- Tarjan
- Fermeture transitive -- Warshall
- Plus courts chemins
- Plus court chemin -- Dijkstra
Connexité forte (1/11)
Composantes fortement connexes = parties maximales
où toute paire de sommets distincts est reliée par un chemin.
Connexité forte (2/11)
(point d'attaches, cf. biconnexité)
Connexité forte (3/11)
(point d'attaches, cf. biconnexité)
Connexité forte (4/11)
(point d'attaches, cf. biconnexité)
Connexité forte (5/11)
(point d'attaches, cf. biconnexité)
Connexité forte (6/11)
(point d'attaches, cf. biconnexité)
Connexité forte (7/11)
| point d'attaches en foncé |
º premier sommet visité par dfs
Connexité forte (8/11)
Le graphe G'=(V',E') des composantes fortement
connexes du graphe G=(V,E) est défini par:
-
V' = { C | C composante fortement connexe de G
}
- E'= { (C,C') | $ e, e Î E Ù org(e) Î C Ù
ext(e) Î C' }.
Proposition
1
Le graphe G=(V',E') des composantes fortement connexes de G=(V,E)
est acyclique.
mprimerComposanteDeRISLANCOIRfsilempilerepilerystemutrintrintln
Connexité forte (9/11)
[Tarjan, 72]
static int numOrdre;
static void imprimerCompFortementConnexes (Graphe g) {
int n = g.succ.length; int num = new int[n]; numOrdre = -1;
for (int x = 0; x < n; ++x) num[x] = -1;
Pile p = new Pile(n);
for (int x = 0; x < n; ++x)
if (num[x] == -1)
imprimerComposanteDe(g, x, num, p);
}
Connexité forte (10/11)
[Tarjan, 72]
static int imprimerComposanteDe (Graphe g, int x, int[ ] num, Pile p) {
Pile.empiler(x, p);
int min = num[x] = ++numOrdre;
for (Liste ls = g.succ[x]; ls != null; ls = ls.suivant) {
int y = ls.val; int m;
if (num[y] == -1)
m = imprimerComposanteDe (g, y, num, p);
else m = num[y];
min = Math.min (min, m);
}
if (min == num[x]) {
int y; do {
y = Pile.depiler(p);
System.out.print (y + " ");
num[y] = g.succ.length; // équivalent à num[y] ¬ ¥
} while (y != x);
System.out.println();
min = g.succ.length;
}
return min;
}
Connexité forte (11/11)
Le point d'attache est le sommet en premier visité par
dfs
- pour un circuit: test acyclicité
- pour tous les circuits élémentaires contenant un fils dans l'arbre de
recouvrement d'un sommet donné: points d'articulation dans
un graphe non-orienté.
- pour une composante fortement connexe:
points d'attache de cette composante
- Les arcs de retour e vérifient num[ext(e)] < num[org(e)]
Þ calculs de minimum
Þ arithmétique sur la numérotation par dfs
|
Complexité O (V+E) º linéaire sur le nombre de sommets
et d'arcs |
|
Donc O(V2) dans le pire cas.
Fermeture transitive (1/3)
Le graphe G+ = (V,E+) de la fermeture transitive de G+ = (V,E)
est tel que E+ est minimum vérifiant
-
E Ì E+
- (x,y) Î E+ Ù (y,z) Î E+ Þ (x,z) Î E+
(transitivité)
Fermeture transitive (2/3)
E matrice n× n d'adjacence pour un graphe avec n sommets.
On veut calculer
| E+ |
|
= |
|
E + E2 + E3 + ··· |
| |
|
= |
|
E + E2 + E3 + ··· + En-1 |
La multiplication de matrices n × n a une complexité
O(n3).
La fermeture transitive peut donc se faire en O(n4) opérations.
Faire mieux?
Fermeture transitive (3/3)
Définition inductive des chemins selon le plus grand des
noeuds intermédiaires par lesquels ils passent.
Ek est la fermeture transitive en n'utilisant des chemins passant
par des sommets intermédiaires strictement inférieurs à k.
| E0 = E |
| Ek+1 = Ek È {(x,y) | (x,k) Î Ek, (k,y) Î Ek } |
static Graphe fermetureTransitive (Graphe g) {
int n = g.e.length;
Graphe gplus = copieGraphe (g);
for (int k = 0; k < n; ++k)
for (int x = 0; x < n; ++x)
for (int y = 0; y < n; ++y)
gplus.e[x][y] = gplus.e[x][y] || (gplus.e[x][k] && gplus.e[k][y]);
return gplus;
}
| Complexité en O(n3) ou encore O(V3). |
Plus courts chemins (1/2)
G=(V,E, d) est un graphe valué (d : V × V |® N).
d(x,y) est la distance de x à y.
On représente G par sa matrice d'adjacence d à valeurs
entières.
On pose d(x,y) = +¥ si pas d'arc de x à y.
Plus courts chemins (2/2)
Plus courts chemins entre tous les sommets d'un graphe.
dx,yk est la longueur du plus court chemin entre x et y
passant par des sommets intermédiaires strictement inférieurs à k.
| dx,y0= d(x,y) |
| dx,yk+1 = min{ dx,yk,
dx,kk + dk,yk } |
static Graphe plusCourtsChemins (Graphe g) {
int n = g.d.length;
Graphe gplus = copieGraphe (g);
for (int k = 0; k < n; ++k)
for (int x = 0; x < n; ++x)
for (int y = 0; y < n; ++y)
gplus.d[x][y] = Math.min (gplus.d[x][y], gplus.d[x][k] + gplus.d[k][y]);
return gplus;
}
| Complexité en O(n3) ou encore O(V3).
Espace mémoire en O(n2). |
Floyd-Warshall = programmation dynamique (cf. cours 4).
Plus court chemin (1/5)
Plus court chemin entre deux sommets x et y dans un graphe
valué. Soit dx,y sa longueur.
| distx,x = 0 |
| distx,z = min{distx,y + d(y,z) |
0 £ y < n} |
Plus court chemin (2/5)
Plus court chemin entre un sommet x et tous les autres sommets.
(Problème généralisé)
- On envoie une onde de la source x vers
les sommets destination.
- Deux sous-ensembles S et Q de V:
-
-- S sommets
NOIR dont la distance de x
minimale est définitive;
- -- Q sommets
GRIS accessibles à partir de x dont on
ne connait que partiellement la distance minimale depuis x.
- ·Au début S=Ø, Q= {x}
- ·Soit y le sommet à distance minimale depuis x dans Q. On fait
NOIR |
|
S ¬ S È {y} |
GRIS |
|
Q ¬ Q - {y} È {z | (y,z)Î E, z ÏS} |
- ·Pour les nouveaux dans Q, on met à jour la distance minimale
connue à partir de x. (relaxation)
- Parcours en largeur selon la distance à x;
algorithme glouton (cf. cours 4)
mprimerComposanteDeheminMin
Plus court chemin (3/5)
[Dijkstra, 1959]
static int[ ] plusCourtChemin (GrapheV g, int x, int u) {
int n = g.succ.length; int[ ] couleur = new int[n];
int[ ] dMin = new int[n]; int[ ] chemin = new int[n];
for (int t = 0; t < n; ++t) {
couleur[t] = BLANC; dMin[t] = Integer.MAX_VALUE;
chemin[t] = -1;
}
dMin[x] = 0; couleur[x] = GRIS; int y;
while ( (y = iMin(dMin, couleur)) != -1) {
couleur[y] = NOIR;
if (y == u) return chemin;
for (ListeV ls = g.succ[y]; ls != null; ls = ls.suivant) {
int z = ls.val; int dyz = ls.d;
if (dMin[y] + dyz < dMin[z]) {
dMin[z] = dMin[y] + dyz; // relaxation
chemin[z] = y; couleur[z] = GRIS;
} } }
return chemin;
}
où iMin(dMin, couleur) rend l'indice du minimum
GRIS dans dMin
Plus court chemin (4/5)
[Dijkstra, 1959]
static int[ ] plusCourtChemin (GrapheV g, int x, int u) {
int n = g.succ.length; int[ ] couleur = new int[n];
int[ ] dMin = new int[n]; int[ ] chemin = new int[n];
for (int t = 0; t < n; ++t) {
couleur[t] = BLANC; dMin[t] = Integer.MAX_VALUE;
chemin[t] = -1;
}
dMin[x] = 0; couleur[x] = GRIS; int y;
while ( (y = iMin(dMin, couleur)) != -1) {
couleur[y] = NOIR;
for (ListeV ls = g.succ[y]; ls != null; ls = ls.suivant) {
int z = ls.val; int dyz = ls.d;
if (dMin[y] + dyz < dMin[z]) {
dMin[z] = dMin[y] + dyz; // relaxation
chemin[z] = y; couleur[z] = GRIS;
} } }
return chemin;
}
où iMin(dMin, couleur) rend l'indice du minimum
GRIS dans dMin
Plus court chemin (5/5)
| Complexité en O(V2 + E), soit O(n2).
Mémoire en O(n). |
En utilisant des files de priorité pour retrouver le sommet à distance
minimum et changer la distance par relaxation, on arrive
à
| Complexité en O((V+E) logV), soit O(n2 logn).
Mémoire en O(n). |
(On peut ramener à O(V logV + E), soit O(n2) avec des
tas de Fibonacci).
[Fredman, Tarjan]
Exercice 1 Calculer le plus court chemin depuis tous les sommets jusqu'à un
même sommet destination.
Exercice 2 Que se passe-t-il s'il y a des distances négatives?
Autres problèmes sur les graphes
- Planarité (
dfs, [Tarjan, 72])
- Circuit hamiltonien
- Voyageur de commerce
- Coloriage de graphe, coloriage de graphes planaires
- Optimisation de flot
- Matching
- Couverture
- de sous-graphes,
- etc
Beaucoup de problèmes sur les graphes sont NP-complets.
This document was translated from LATEX by
HEVEA.
