---
title: "Arbres couvrants"
date: "2025-06-06"
---

# Arbres couvrants

\Huge Les arbres couvrants

# 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 part-on? 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 un 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!

::::

:::

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

::::

:::

# 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)
    s_initial = aléatoire(graphe)
    distance[s_initial] = 0
    fp = file_p_vide()
    pour s_courant dans sommets(graphe)
        si s_courant != s_initial
            distance[s_courant] = infini
        parent[s_courant]   = indéfini
        fp = enfiler(fp, s_courant, distance[s_courant])
    retourne fp, distance, parent
```

# Algorithme de Prim

\footnotesize

## Algorithme: Pseudo-code (5min)

. . .

```C
distance, parent prim(graphe)
    fp, distance, parent initialisation(graphe)
    sommets = vide
    tant que !est_vide(fp)
        s_courant, fp = défiler(fp)
        sommets = insérer(sommets, s_courant)
        pour s_voisin dans voisinage(s_courant) et pas dans sommets 
        // ou dans fp
            si poids(s_courant, s_voisin) < distance[s_voisin]
                parent[s_voisin] = s_courant
                distance[s_voisin] = poids(s_courant, s_voisin)
                fp = changer_priorité(fp, s_voisin,
                                      poids(s_courant, s_voisin))
    retourne distance, parent
```

# 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)
        // initialisation distance et parent en O(|V|)
        fp = enfiler(fp, v, distance[v])
    retourne fp, distance, parent
distance, parent prim(graphe)
    fp, distance, parent initialisation(graphe) // O(|V|)
    sommets = vide
    tant que !est_vide(fp)
        u, fp = défiler(fp) // O(|V|)
        sommets = insérer(sommets, u)
        pour v dans voisinage de u et pas dans sommets
            si poids(u, v) < distance[v] // O(|E|)  
                // màj distance + parent
                fp = changer_priorité(fp, v, poids(u, v)) // O(|V|) 
    retourne distance, 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 ne sont traitées 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 $V_i$ et $V_j$ 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)