Skip to content
Snippets Groups Projects
Select Git revision
  • a214eadd1cc04e2f79986a33d76e72dee8d99b74
  • main default protected
2 results

cours_27.md

Blame
  • Orestis's avatar
    orestis.malaspin authored
    a214eadd
    History
    cours_27.md 12.42 KiB
    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

    Ces maisons n'ont pas d'électricité.

    Solution: pas optimale

    Le réseau simple, mais nul.

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

    Solution: optimale

    Le meilleur réseau.

    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.

    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.

    Arbres couvrants minimaux

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

    Algorithme de Prim

    ::: columns

    :::: column

    Un exemple

    Le graphe de départ.

    ::::

    :::: column

    On part de e (au hasard)

    Le sommet e est couvert.

    ::::

    :::

    Algorithme de Prim

    ::: columns

    :::: column

    On choisit comment?

    Quelle arête choisir?

    . . .

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

    ::::

    :::

    Algorithme de Prim

    ::: columns

    :::: column

    On choisit comment?

    Quelle arête choisir?

    . . .

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

    ::::

    :::

    Algorithme de Prim

    ::: columns

    :::: column

    On choisit comment?

    Quelle arête choisir?

    . . .

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

    ::::

    :::

    Algorithme de Prim

    ::: columns

    :::: column

    On choisit comment?

    Quelle arête choisir?

    . . .

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

    • 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

    Étape 1.

    ::::

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

    ::::

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

    ::::

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

    ::::

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

    ::::

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

    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(V2)=O(E+V2)O(|V|)+O(|E|)+O(|V|^2)=O(|E|+|V|^2)
    • Remarque:
      O(E)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.

    ::::

    :::: column

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

    Les sommets a, d sont couverts.

    ::::

    :::

    Algorithme de Kruskal: exemple

    ::: columns

    :::: column

    On continue avec (c, d)

    On aurait pu choisir (d, e) aussi.

    ::::

    :::: column

    Résultat

    Les sommets a, d, c sont couverts.

    ::::

    :::

    Algorithme de Kruskal: exemple

    ::: columns

    :::: column

    On continue avec (d, e)

    Le poids de (d, e) est le plus bas.

    ::::

    :::: column

    Résultat

    Les sommets a, d, c, e sont couverts.

    ::::

    :::

    Algorithme de Kruskal: exemple

    ::: columns

    :::: column

    On continue avec (b, e)

    Le poids de (b, e) est le plus bas.

    ::::

    :::: column

    Résultat

    Les sommets a, d, c, e, b sont couverts.

    ::::

    :::

    Algorithme de Kruskal: exemple

    ::: columns

    :::: column

    Mais pourquoi pas (c, e)?

    Le poids de (b, e) ou (a,c) est le même.

    ::::

    :::: column

    Résultat: un cycle

    Les sommets a, d, c, e sont couverts.

    ::::

    :::

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

    ::::

    :::: column

    ::::

    :::

    Algorithme de Kruskal: solution

    La solution!

    Algorithme de Kruskal: exercice

    ::: columns

    :::: column

    Couvrir cet arbre bon sang!

    ::::

    :::: column

    ::::

    :::

    Algorithme de Kruskal: solution

    La solution!