cours_27.md

title: "Graphes - Arbres couvrants"
date: "2022-05-03"
patat:
    eval:
        tai:
            command: fish
            fragment: false
            replace: true
        ccc:
            command: fish
            fragment: false
            replace: true
    images:
      backend: auto

Questions

• A quoi sert l'algorithme de Floyd--Warshall?

. . .

• A trouver le plus court chemin entre n'importe quelle paire de sommets d'un graphe pondéré.
• Quelle est la limitation de l'algorithme de Dijkstra n'est pas présente pour l'algorithme de Floyd--Warshall?

. . .

• Les poids peuvent être négatifs.
• Qu'est-ce qu'un arbre couvrant minimal?

. . .

• Un arbre couvrant minimal d'un graphe non-orienté et connexe est:
  • un arbre inclu dans le graphe qui connecte tous les sommets du graphe et dont le poids total des arêtes est minimal.

Arbres couvrants minimaux

• Comment générer un arbre couvrant minimal?

Algorithme de Prim

::: columns

:::: column

Un exemple

::::

:::: column

On part de e (au hasard)

::::

:::

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

. . .

L'arête e->d

::::

:::

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

. . .

L'arête d->a

::::

:::

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

. . .

L'arête d->c

::::

:::

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

. . .

L'arête e->b

::::

:::

• 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

• $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

::::

:::: column

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

::::

:::

Algorithme de Kruskal: exemple

::: columns

:::: column

On continue avec (c, d)

::::

:::: column

Résultat

::::

:::

Algorithme de Kruskal: exemple

::: columns

:::: column

On continue avec (d, e)

::::

:::: column

Résultat

::::

:::

Algorithme de Kruskal: exemple

::: columns

:::: column

On continue avec (b, e)

::::

:::: column

Résultat

::::

:::

Algorithme de Kruskal: exemple

::: columns

:::: column

Mais pourquoi pas (c, e)?

::::

:::: 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
    $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 A$
    à poids minimal:
  • Retirer
    $(u,v)$
    de
    $A$
    ,
  • 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

::::

:::: column

::::

:::

Algorithme de Kruskal: solution

Algorithme de Kruskal: exercice

::: columns

:::: column

::::

:::: column

::::

:::

Algorithme de Kruskal: solution