---
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?

. . .

```C
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?

. . .

```C
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

![Ces maisons n'ont pas d'électricité.](figs/arbre_couvrant_vide.png)

# Solution: pas optimale

![Le réseau simple, mais nul.](figs/arbre_couvrant_mal.png)

* La longueur totale des câbles est super longue!

# Solution: optimale

![Le meilleur réseau.](figs/arbre_couvrant_bien.png)

# 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.

. . .

![Exemple d'arbres couvrants d'un graphe connexe.](figs/arbre_couvrant_exemples.png)

# Arbres couvrants

* Quels algorithmes que nous avons déjà vus permettent de construire des arbres couvrants?

. . .

* Les parcours en largeur et en profondeur!

. . .

![Graphe, et parcours comme arbres couvrants.](figs/arbres_couvrants_parcours.png)

# Arbres couvrants minimaux

* Un *arbre couvrant minimal* est un sous-graphe d'un graphe non-orienté pondéré $G(V,E)$, tel quel:
    * C'est un arbre (graphe acyclique);
    * Il couvre tous les sommets de $G$ et contient $|V|-1$ arê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?

![Un graphe, connexe, non-orienté, pondéré, et son arbre couvrant minimal.](figs/arbre_couvrant_minimal_exemple.png)

# Algorithme de Prim

::: columns

:::: column

## Un exemple

![Le graphe de départ.](figs/prim_0.png)

::::

:::: column

## On part de `e` (au hasard)

![Le sommet `e` est couvert.](figs/prim_1.png)

::::

:::

# Algorithme de Prim

::: columns

:::: column

## On choisit comment? 

![Quelle arête choisir?](figs/prim_1.png)

. . .

* L'arête la plus courte sortant d'un sommet déjà visité, et entrant dans un sommet non-visité.

::::

:::: column

. . .

## L'arête `e->d`

![Le sommet `d` est couvert.](figs/prim_2.png)

::::

:::

# Algorithme de Prim

::: columns

:::: column

## On choisit comment? 

![Quelle arête choisir?](figs/prim_2.png)

. . .

* L'arête la plus courte sortant d'un sommet déjà visité, et entrant dans un sommet non-visité.

::::

:::: column

. . .

## L'arête `d->a`

![Le sommet `a` est couvert.](figs/prim_3.png)

::::

:::

# Algorithme de Prim

::: columns

:::: column

## On choisit comment? 

![Quelle arête choisir?](figs/prim_3.png)

. . .

* L'arête la plus courte sortant d'un sommet déjà visité, et entrant dans un sommet non-visité.

::::

:::: column

. . .

## L'arête `d->c`

![Le sommet `c` est couvert.](figs/prim_4.png)

::::

:::

# Algorithme de Prim

::: columns

:::: column

## On choisit comment? 

![Quelle arête choisir?](figs/prim_4.png)

. . .

* L'arête la plus courte sortant d'un sommet déjà visité, et entrant dans un sommet non-visité.

::::

:::: column

. . .

## L'arête `e->b`

![Le sommet `b` est couvert.](figs/prim_5.png)

* 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)

. . .

```C
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)

. . .

```C
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

![Étape 1.](figs/prim_1.png)

::::

:::: 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

![Étape 2.](figs/prim_2.png)

::::

:::: 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

![Étape 3.](figs/prim_3.png)

::::

:::: 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

![Étape 4.](figs/prim_4.png)

::::

:::: 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

![Étape 5.](figs/prim_4.png)

::::

:::: 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):

![En démarrant du sommet $V_1$.](figs/prim_exercice.png)

# Exercice: algorithme de Prim

## Solution

![](figs/prim_solution.png)

# Complexité de l'algorithme de Prim

\footnotesize

```C
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
```

* $O(|V|)+O(|E|)+O(|V|^2)=O(|E|+|V|^2)$
* Remarque: $O(|E|)$ n'est pas mutliplié par $O(|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

![Le graphe de départ.](figs/kruskal_0.png)

::::

:::: column

## On part de `(a, d)` (poids le plus faible)

![Les sommets `a, d` sont couverts.](figs/kruskal_1.png)

::::

:::

# Algorithme de Kruskal: exemple

::: columns

:::: column

## On continue avec `(c, d)`

![On aurait pu choisir `(d, e)` aussi.](figs/kruskal_1.png)

::::

:::: column

## Résultat

![Les sommets `a, d, c` sont couverts.](figs/kruskal_2.png)

::::

:::

# Algorithme de Kruskal: exemple

::: columns

:::: column

## On continue avec `(d, e)`

![Le poids de `(d, e)` est le plus bas.](figs/kruskal_2.png)

::::

:::: column

## Résultat

![Les sommets `a, d, c, e` sont couverts.](figs/kruskal_3.png)

::::

:::

# Algorithme de Kruskal: exemple

::: columns

:::: column

## On continue avec `(b, e)`

![Le poids de `(b, e)` est le plus bas.](figs/kruskal_3.png)

::::

:::: column

## Résultat

![Les sommets `a, d, c, e, b` sont couverts.](figs/kruskal_4.png)

::::

:::

# Algorithme de Kruskal: exemple

::: columns

:::: column

## Mais pourquoi pas `(c, e)`?

![Le poids de `(b, e)` ou `(a,c)` est le même.](figs/kruskal_3.png)

::::

:::: column

## Résultat: un cycle

![Les sommets `a, d, c, e` sont couverts.](figs/kruskal_cycle.png)

::::

:::

* 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 $n$ sommets, il y a $n$ $V_i$.
* Initialiser l'ensemble $A$ des 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)$ de $E$,
    * Si $u\in V_i$ et $v\in V_j$ avec $V_i\cap V_j=\emptyset$:
        * Ajouter $(u,v)$ à $A$;
        * Fusionner $U$ et $V$ dans $F$.

# Algorithme de Kruskal: exemple

::: columns

:::: column

![Couvrir cet arbre bon sang!](figs/kruskal_enonce.png)

::::

:::: column

::::

:::

# Algorithme de Kruskal: solution

![La solution!](figs/kruskal_solution.png)

# Algorithme de Kruskal: exercice

::: columns

:::: column

![Couvrir cet arbre bon sang!](figs/kruskal_exercice.png)

::::

:::: column

::::

:::

# Algorithme de Kruskal: solution

![La solution!](figs/kruskal_solution_exercice.png)