cours_27.md

- Rappel (1/2)
- Algorithme de Dijkstra: à quoi sert-il?
- Algorithme de Dijkstra: algorithme?
- Rappel (2/2)
- Algorithme de Floyd: à quoi sert-il?
- Algorithme de Floyd: algorithme?
- La suite
- Trouver un réseau électrique pour
- Solution: pas optimale
- Solution: optimale
- Formalisation: Les arbres couvrants
- Application: minimisation des coûts
- Formalisation: Les arbres couvrants
- Arbres couvrants
- Arbres couvrants minimaux
- Arbres couvrants minimaux
- Algorithme de Prim
- Un exemple
- On part de e (au hasard)
- Algorithme de Prim
- On choisit comment?
- L'arête e->d
- Algorithme de Prim
- On choisit comment?
- L'arête d->a
- Algorithme de Prim
- On choisit comment?
- L'arête d->c
- Algorithme de Prim
- On choisit comment?
- L'arête e->b
- Algorithme de Prim
- Structures de données
- Algorithme de Prim
- Initialisation: Pseudo-code (2min)
- Algorithme de Prim
- Algorithme: Pseudo-code (5min)
- Exemple d'algorithme de Prim
- Un exemple
- Devient?
- Exemple d'algorithme de Prim
- Un exemple
- Devient?
- Exemple d'algorithme de Prim
- Un exemple
- Devient?
- Exemple d'algorithme de Prim
- Un exemple
- Devient?
- Exemple d'algorithme de Prim
- Un exemple
- Devient?
- Exercice: algorithme de Prim
- Appliquer l'algorithme de Prim à (15min):
- Exercice: algorithme de Prim
- Solution
- Complexité de l'algorithme de Prim
- Algorithme de Kruskal
- Algorithme de Kruskal: exemple
- Un exemple
- On part de (a, d) (poids le plus faible)
- Algorithme de Kruskal: exemple
- On continue avec (c, d)
- Résultat
- Algorithme de Kruskal: exemple
- On continue avec (d, e)
- Résultat
- Algorithme de Kruskal: exemple
- On continue avec (b, e)
- Résultat
- Algorithme de Kruskal: exemple
- Mais pourquoi pas (c, e)?
- Résultat: un cycle
- Algorithme de Kruskal
- L'initialisation
- Mise à jour
- Algorithme de Kruskal: exemple
- Algorithme de Kruskal: solution
- Algorithme de Kruskal: exercice
- Algorithme de Kruskal: solution
title: "Flots dans les graphes"
date: "2024-06-04"
Rappel (1/2)
Algorithme de Dijkstra: à quoi sert-il?
. . .
A trouver le plus court chemin entre deux sommets d'un graphe!
Algorithme de Dijkstra: algorithme?
. . .
distance[source] = 0
distance[reste] = inf;
pour sommet dans liste_sommets:
fp = enfiler(fp, sommet, w(source, sommet)) // file min
tant !est_vide(fp):
sommet_courant, fp = défiler(fp);
pour sommet_voisin dans voisinage(sommet_courant):
n_dist = distance[sommet_courant] + w(sommet_courant, sommet_voisin)
si distance[sommet_voisin] > n_dist:
distance[sommet_voisin] = n_dist
precedence[sommet_voisin] = sommet_courant
fp = mettre_a_jour(fp, sommet_voisin, n_dist)
Rappel (2/2)
Algorithme de Floyd: à quoi sert-il?
. . .
A trouver le plus court chemin entre toutes les paires de sommets d'un graphe!
Algorithme de Floyd: algorithme?
. . .
matrice, matrice floyd_warshall(distance, n, w)
pour k de 1 à n
pour i de 1 à n
pour j de 1 à n
n_distance = distance[i][k] + distance[k][j]
si n_distance < distance[i][j]
distance[i][j] = n_distance
précédence[i][j] = précédence[k][j]
retourne distance, précédence
La suite
\Huge Sans transition.... la suite!
Trouver un réseau électrique pour
Solution: pas optimale
- La longueur totale des câbles est super longue!
Solution: optimale
Formalisation: Les arbres couvrants
Application: minimisation des coûts
- Équipement d'un lotissement avec des lignes électriques/téléphoniques, des canalisations, ...
. . .
- Pour réduire les coûts, on cherche à minimiser la longueur totale des câbles/tuyaux.
. . .
- Les lignes/tuyaux forment un arbre couvrant.
. . .
- La meilleure option est un arbre couvrant minimal.
Formalisation: Les arbres couvrants
- Qu'est-ce qu'un arbre couvrant? Des idées? De quel objet on part? Où va-t-on?
. . .
- Un arbre couvrant d'un graphe non-orienté et connexe est:
- un arbre inclus dans le graphe qui connecte tous les sommets du graphe.
. . .
Arbres couvrants
- Quels algorithmes que nous avons déjà vus permettent de construire des arbres couvrants?
. . .
- Les parcours en largeur et en profondeur!
. . .
Arbres couvrants minimaux
- Un arbre couvrant minimal est un sous-graphe d'un graphe non-orienté pondéré , tel quel:
- C'est un arbre (graphe acyclique);
- Il couvre tous les sommets de et contientarêtes;
- Le coût total associé aux arêtes de l'arbre est minimum parmi tous les arbres couvrants possibles.
. . .
- Est-il unique?
. . .
- Pas forcément.
Arbres couvrants minimaux
- Comment générer un arbre couvrant minimal?
Algorithme de Prim
::: columns
:::: column
Un exemple
::::
:::: column
e
(au hasard)
On part de
::::
:::
Algorithme de Prim
::: columns
:::: column
On choisit comment?
. . .
- L'arête la plus courte sortant d'un sommet déjà visité, et entrant dans un sommet non-visité.
::::
:::: column
. . .
e->d
L'arête
::::
:::
Algorithme de Prim
::: columns
:::: column
On choisit comment?
. . .
- L'arête la plus courte sortant d'un sommet déjà visité, et entrant dans un sommet non-visité.
::::
:::: column
. . .
d->a
L'arête
::::
:::
Algorithme de Prim
::: columns
:::: column
On choisit comment?
. . .
- L'arête la plus courte sortant d'un sommet déjà visité, et entrant dans un sommet non-visité.
::::
:::: column
. . .
d->c
L'arête
::::
:::
Algorithme de Prim
::: columns
:::: column
On choisit comment?
. . .
- L'arête la plus courte sortant d'un sommet déjà visité, et entrant dans un sommet non-visité.
::::
:::: column
. . .
e->b
L'arête
- Game over!
::::
:::
Algorithme de Prim
Structures de données
- Dans quoi allons nous stocker les sommets?
. . .
- File de priorité min.
- Autre chose?
. . .
- Tableau des distances (comme pour Dijkstra).
- Autre chose?
. . .
- Tableau des parents (presque comme pour Dijkstra).
- Autre chose?
. . .
- Non.
Algorithme de Prim
Initialisation: Pseudo-code (2min)
. . .
file_priorité, distance, parent initialisation(graphe)
r = aléatoire(graphe)
distance[r] = 0
parent[r] = indéfini
fp = file_p_vide()
pour v dans sommets(graphe)
si v != r
distance[v] = infini
parent[v] = indéfini
fp = enfiler(fp, v, distance[v])
retourne fp, distance, parent
Algorithme de Prim
Algorithme: Pseudo-code (5min)
. . .
sommets, parent prim(file_priorité, distance, parent)
sommets = vide
tant que !est_vide(file_priorité)
u, fp = défiler(file_priorité)
sommets = insérer(sommets, u)
pour v dans voisinage de u et pas dans sommets
// ou dans file_priorité
si w(u, v) < distance[v]
parent[w] = u
distance[w] = w(u, v)
fp = changer_priorité(fp, w, w(u, v))
retourne sommets, parent
Exemple d'algorithme de Prim
::: columns
:::: {.column width="40%"}
Un exemple
::::
:::: column
FP | e | d | b | c | a |
----------------------------------
D | 0 | inf | inf | inf | inf |
| e | d | b | c | a |
----------------------------------
P | - | - | - | - | - |
Devient?
. . .
FP | d | b | c | a |
----------------------------
D | 4 | 5 | 5 | inf |
| e | d | b | c | a |
----------------------------------
P | - | e | e | e | - |
::::
:::
Exemple d'algorithme de Prim
::: columns
:::: {.column width="40%"}
Un exemple
::::
:::: column
FP | d | b | c | a |
----------------------------
D | 4 | 5 | 5 | inf |
| e | d | b | c | a |
----------------------------------
P | - | e | e | e | - |
Devient?
. . .
FP | a | c | b |
----------------------
D | 2 | 4 | 5 |
| e | d | b | c | a |
----------------------------------
P | - | e | e | d | d |
::::
:::
Exemple d'algorithme de Prim
::: columns
:::: {.column width="40%"}
Un exemple
::::
:::: column
FP | a | c | b |
----------------------
D | 2 | 4 | 5 |
| e | d | b | c | a |
----------------------------------
P | - | e | e | d | d |
Devient?
. . .
FP | c | b |
----------------
D | 4 | 5 |
| e | d | b | c | a |
----------------------------------
P | - | e | e | d | d |
::::
:::
Exemple d'algorithme de Prim
::: columns
:::: {.column width="40%"}
Un exemple
::::
:::: column
FP | c | b |
----------------
D | 4 | 5 |
| e | d | b | c | a |
----------------------------------
P | - | e | e | d | d |
Devient?
. . .
FP | b |
----------
D | 5 |
| e | d | b | c | a |
----------------------------------
P | - | e | e | d | d |
::::
:::
Exemple d'algorithme de Prim
::: columns
:::: {.column width="40%"}
Un exemple
::::
:::: column
FP | b |
----------
D | 5 |
| e | d | b | c | a |
----------------------------------
P | - | e | e | d | d |
Devient?
. . .
FP |
----
D |
| e | d | b | c | a |
----------------------------------
P | - | e | e | d | d |
::::
:::
Exercice: algorithme de Prim
Appliquer l'algorithme de Prim à (15min):
Exercice: algorithme de Prim
Solution
Complexité de l'algorithme de Prim
\footnotesize
file_priorité, distance, parent initialisation(graphe)
// choix r et initialisation
pour v dans sommets(graphe)
O(|V|) // initialisation distance et parent
fp = enfiler(fp, v, distance[v])
retourne fp, distance, parent
sommets, parent prim(file_priorité, distance, parent)
sommets = vide
tant que !est_vide(file_priorité)
O(|V|) u, fp = défiler(file_priorité)
sommets = insérer(sommets, u)
pour v dans voisinage de u et pas dans sommets
O(|E|) si w(u, v) < distance[v]
// màj dista + parent
O(|V|) fp = changer_priorité(fp, w, w(u, v))
retourne sommets, parent
- Remarque: n'est pas mutliplié parO(|V|), car les arêtes parcourues qu'une fois en tout.
Algorithme de Kruskal
- On ajoute les arêtes de poids minimal:
- si cela ne crée pas de cycle;
- on s'arrête quand on a couvert tout le graphe.
. . .
- Comment on fait ça?
. . .
- Faisons un exemple pour voir.
Algorithme de Kruskal: exemple
::: columns
:::: column
Un exemple
::::
:::: column
(a, d)
(poids le plus faible)
On part de
::::
:::
Algorithme de Kruskal: exemple
::: columns
:::: column
(c, d)
On continue avec
::::
:::: column
Résultat
::::
:::
Algorithme de Kruskal: exemple
::: columns
:::: column
(d, e)
On continue avec
::::
:::: column
Résultat
::::
:::
Algorithme de Kruskal: exemple
::: columns
:::: column
(b, e)
On continue avec
::::
:::: column
Résultat
::::
:::
Algorithme de Kruskal: exemple
::: columns
:::: column
(c, e)
?
Mais pourquoi pas
::::
:::: column
Résultat: un cycle
::::
:::
- Comment faire pour empêcher l'ajout de
(c, e)
ou(a, c)
?
. . .
- Si les deux sommets sont déjà couverts nous sommes sauvés (presque)!
Algorithme de Kruskal
L'initialisation
- Créer un ensemble de sommets pour chaque de sommet du graphe (V_1,V_2, ...):
-
V_1=\{v_1\},V_2=\{v_2\}, ...
- S'il y a nsommets, il y anV_i.
-
- Initialiser l'ensemble Ades arêtes "sûres" constituant l'arbre couvrant minimal,A=\emptyset.
- Initialiser l'ensemble des sommets couverts F=\emptyset
- Trier les arêtes par poids croissant dans l'ensemble E.
Mise à jour
- Tant qu'il reste plus d'un V_i:
- Pour (u,v)\in Eà poids minimal:
- Retirer (u,v)deE,
- Si u\in V_ietv\in V_javecV_i\cap V_j=\emptyset:
- Ajouter (u,v)àA;
- Fusionner UetVdansF.
- Ajouter
- Pour
Algorithme de Kruskal: exemple
::: columns
:::: column
::::
:::: column
::::
:::
Algorithme de Kruskal: solution
Algorithme de Kruskal: exercice
::: columns
:::: column
::::
:::: column
::::
:::