cours_23.md

title: "B-arbres et Graphes"
date: "2023-05-24"
patat:
  eval:
    tai:
      command: fish
      fragment: false
      replace: true
    ccc:
      command: fish
      fragment: false
      replace: true
  images:
    backend: auto

Les B-arbres: suppression

Cas simplissime

. . .

Les B-arbres: suppression

\footnotesize

Cas simple

. . .

• On retire 27, mais....
  • Chaque page doit avoir au moins 2 éléments.
  • On doit déplacer des éléments dans une autre feuille! Mais comment?

. . .

Les B-arbres: suppression

Cas moins simple

. . .

• Un élément à droite, comment on fait?
  • Remonter 7, serait ok si racine, mais... c'est pas forcément.
  • On redistribue les feuilles.

. . .

Les B-arbres: suppression

\footnotesize

Cas ultra moins simple

. . .

• 7 seul:
  • Fusionner les feuilles et redistribuer, comment?

. . .

Les B-arbres: suppression

Cas ultra moins simple

. . .

• 8 est seul, c'est plus un B-arbre :
  • Fusionner le niveau 2 et redistribuer, comment?

. . .

. . .

• La profondeur a diminué de 1.

Les B-arbres: suppression

Algorithme pour les feuilles!

• Si la clé est supprimée d'une feuille:
  • Si on a toujours n (ordre de l'arbre) clés dans la feuille on décale simplement les clés.
  • Sinon on combine (récursivement) avec le nœud voisin et on descend la clé médiane.

Les B-arbres: suppression

Cas non-feuille!

. . .

• On sait comment effacer une valeur d'une feuille, donc?

. . .

• Ensuite?

Les B-arbres: suppression

Cas non-feuille!

. . .

• On sait comment effacer une valeur d'une feuille!

. . .

Les B-arbres: suppression

Algorithme pour les non-feuilles!

• Si la clé est supprimée d'une page qui n'est pas une feuille:
  • On échange la valeur avec la valeur de droite de la page de gauche
  • On supprime comme pour une feuille!

Et maintenant des exercices par millions!

Les graphes! Historique

Un mini-peu d'histoire...

L. Euler et les 7 ponts de Koenigsberg:

• Existe-t-il une promenade sympa, passant une seule fois par les 7 ponts et revenant au point de départ?

. . .

• Réponse: ben non!

Utilisation quotidienne

Réseau social

• Chaque sommet est un individu.
• Chaque trait une relation d'amitié.
• Miam, Miam, Facebook.

Utilisation quotidienne

Moteurs de recherche

• Sommet est un site.
• Liens sortants;
• Liens entrants;
• Notion d'importance d'un site: combien de liens entrants, pondérés par l'importance du site.
• Miam, Miam, Google (PageRank).

Introduction

Définition, plus ou moins

• Un graphe est un ensemble de sommets, reliés par des lignes ou des flèches.

• Des sommets (numérotés 1 à 6);
• Connectés ou pas par des traits ou des flèches!

Généralités

Définitions

• Un graphe G(V, E) est constitué
  • V: un ensemble de sommets;
  • E: un ensemble d'arêtes.
• Une arête relie une paire de sommets de V.

Remarques

• Il y a au plus une arête E par paire de sommets de V.
• La complexité d'un algorithme dans un graphe se mesure en terme de |E| et |V|, le nombre d'éléments de E et V respectivement.

Généralités

Notations

• Une arête d'un graphe non-orienté est représentée par une paire non-ordonnée (u,v)=(v,u), avec u,v\in V.
• Les arêtes ne sont pas orientées dans un graphe non-orienté (elles sont bi-directionnelles, peuvent être parcourues dans n'importe quel ordre).

Exemple

::: columns

:::: column

::::

:::: column

Que valent V, |V|, E, et |E|?

. . .

\begin{align*} V&={1, 2, 3, 4},\ |V|&=4,\ E&={(1,2),(2,3),(2,4),(4,1)},\ |E|&=4. \end{align*}

::::

:::

Généralités

Notations

• Une arête d'un graphe orienté est représentée par une paire ordonnée (u,v)\neq(v,u), avec u,v\in V.
• Les arêtes sont orientées dans un graphe orienté (étonnant non?).

Exemple

::: columns

:::: column

::::

:::: column

Que valent V, |V|, E, et |E|?

. . .

\begin{align*} V&={1, 2, 3, 4},\ |V|&=4,\ E&={(1,2),(2,3),(2,4),(4,1),(4,2)},\ |E|&=5. \end{align*}

::::

:::

Généralités

Définition

• Le somme v est adjacent au sommet u, si et seulement si (u,v)\in E;
• Si un graphe non-orienté contient une arête (u,v), v est adjacent à u et u et adjacent à v.

Exemple

::: columns

:::: column

::::

:::: column

::::

:::

Généralités

Définition

• Un graphe pondéré ou valué est un graphe dont chaque arête a un poids associé, habituellement donné par une fonction de pondération w:E\rightarrow\mathbb{R}.

Exemples

Généralités

Définition

• Dans un graphe G(V,E), une chaîne reliant un sommet u à un sommet v est une suite d'arêtes entre les sommets, w_0, w_1, ..., w_k, telles que (w_i, w_{i+1})\in E,\quad u=w_0,\quad v=w_k,\quad \mbox{pour }0\leq i< k, avec k la longueur de la chaîne (le nombre d'arêtes du chemin).

Exemples

Généralités

Définition

• Une chaîne élémentaire est une chaîne dont tous les sommets sont distincts, sauf les extrémités qui peuvent être égales

Exemples

Généralités

Définition

• Une boucle est une arête (v,v) d'un sommet vers lui-même.

Exemples

Généralités

Définition

• Un graphe non-orienté est dit connexe, s'il existe un chemin reliant n'importe quelle paire de sommets distincts.

Exemples

\

::: columns

:::: column

::::

:::: column

::::

:::

Généralités

Définition

• Un graphe orienté est dit fortement connexe, s'il existe un chemin reliant n'importe quelle paire de sommets distincts.

Exemples

\

::: columns

:::: column

::::

:::: column

::::

:::

Généralités

Définition

• Un cycle dans un graphe non-orienté est une chaîne de longueur \leq 3 telle que le 1er sommet de la chaîne est le même que le dernier, et dont les arêtes sont distinctes.
• Pour un graphe orienté on parle de circuit.
• Un graphe sans cycles est dit acyclique.

Exemples

Question de la mort

• Qu'est-ce qu'un graphe connexe acyclique?

. . .

• Un arbre!

Représentations

• La complexité des algorithmes sur les graphes s'expriment en fonction du nombre de sommets V, et du nombre d'arêtes E:
  • Si |E|\sim |V|^2, on dit que le graphe est dense.
  • Si |E|\sim |V|, on dit que le graphe est peu dense.
• Selon qu'on considère des graphes denses ou peu denses, différentes structure de données peuvent être envisagées.

Question

• Comment peut-on représenter un graphe informatiquement? Des idées (réflexion de quelques minutes)?

. . .

• Matrice/liste d'adjacence.

Matrice d'adjacence

• Soit le graphe G(V,E), avec V=\{1, 2, 3, ..., n\};
• On peut représenter un graphe par une matrice d'adjacence, A, de dimension n\times n définie par A_{ij}=\left\{ \begin{array}{ll} 1 & \mbox{si } i,j\in E,\\ 0 & \mbox{sinon}. \end{array} \right.

::: columns

:::: column

Exemple

graph LR;
    1---2;
    1---4;
    2---5;
    4---5;
    5---3;

::::

:::: column

\footnotesize

Quelle matrice d'adjacence?

. . .

   || 1 | 2 | 3 | 4 | 5
===||===|===|===|===|===
 1 || 0 | 1 | 0 | 1 | 0
---||---|---|---|---|---
 2 || 1 | 0 | 0 | 0 | 1
---||---|---|---|---|---
 3 || 0 | 0 | 0 | 0 | 1
---||---|---|---|---|---
 4 || 1 | 0 | 0 | 0 | 1
---||---|---|---|---|---
 5 || 0 | 1 | 1 | 1 | 0

::::

:::

Matrice d'adjacence

Remarques

• Zéro sur la diagonale.
• La matrice d'un graphe non-orienté est symétrique

A_{ij}=A_{ji}, \forall i,j\in[1,n] .

::: columns

:::: column

graph LR;
    1---2;
    1---4;
    2---5;
    4---5;
    5---3;

::::

:::: column

\footnotesize

   || 1 | 2 | 3 | 4 | 5
===||===|===|===|===|===
 1 || 0 | 1 | 0 | 1 | 0
---||---|---|---|---|---
 2 || 1 | 0 | 0 | 0 | 1
---||---|---|---|---|---
 3 || 0 | 0 | 0 | 0 | 1
---||---|---|---|---|---
 4 || 1 | 0 | 0 | 0 | 1
---||---|---|---|---|---
 5 || 0 | 1 | 1 | 1 | 0

::::

:::

Matrice d'adjacence

• Pour un graphe orienté (digraphe)

::: columns

:::: column

Exemple

graph LR;
    2-->1;
    1-->4;
    2-->5;
    5-->2;
    4-->5;
    5-->3;

::::

:::: column

\footnotesize

Quelle matrice d'adjacence?

. . .

   || 1 | 2 | 3 | 4 | 5
===||===|===|===|===|===
 1 || 0 | 0 | 0 | 1 | 0
---||---|---|---|---|---
 2 || 1 | 0 | 0 | 0 | 1
---||---|---|---|---|---
 3 || 0 | 0 | 0 | 0 | 0
---||---|---|---|---|---
 4 || 0 | 0 | 0 | 0 | 1
---||---|---|---|---|---
 5 || 0 | 1 | 1 | 0 | 0

::::

:::

• La matrice d'adjacence n'est plus forcément symétrique A_{ij}\neq A_{ji}.

Stockage

• Quel est l'espace nécessaire pour stocker une matrice d'adjacence pour un graphe orienté?

. . .

• \mathcal{O}(|V|^2).
• Quel est l'espace nécessaire pour stocker une matrice d'adjacence pour un graphe non-orienté?

. . .

• \mathcal{O}(|V|-1)|V|/2.

Considérations d'efficacité

• Dans quel type de graphes la matrice d'adjacence est utile?

. . .

• Dans les graphes denses.
• Pourquoi?

. . .

• Dans les graphes peu denses, la matrice d'adjacence est essentiellement composée de 0.

Remarque

• Dans la majorité des cas, les grands graphes sont peu denses.
• Comment représenter un graphe autrement?

La liste d'adjacence (non-orienté)

• Pour chaque sommet v\in V, stocker les sommets adjacents à v-
• Quelle structure de données pour la liste d'adjacence?

. . .

• Tableau de liste chaînée, vecteur (tableau dynamique), etc.

::: columns

:::: column

Exemple

::::

:::: column

Quelle liste d'adjacence?

. . .

::::

:::

La liste d'adjacence (orienté)

::: columns

:::: column

Quelle liste d'adjacence pour...

• Matrix (2min)

graph LR;
    0-->1;
    0-->2;
    1-->2;
    3-->0;
    3-->1;
    3-->2;

::::

:::: column

::::

:::

Complexité

Stockage

• Quelle espace est nécessaire pour stocker une liste d'adjacence (en fonction de |E| et |V|)?

. . .

\mathcal{O}(|E|)

• Pour les graphes non-orientés: \mathcal{O}2|E|.
• Pour les graphes orientés: \mathcal{O}|E|.

Définition

• Le degré d'un sommet v, est le nombre d'arêtes incidentes du sommet (pour les graphes orientés on a un degré entrant ou sortant).
• Comment on retrouve le degré de chaque sommet avec la liste d'adjacence?

. . .

• C'est la longueur de la liste chaînée.

Parcours

• Beaucoup d'applications nécessitent de parcourir des graphes:
  • Trouver un chemin d'un sommet à un autre;
  • Trouver si le graphe est connexe;
• Il existe deux parcours principaux:
  • en largeur (Breadth-First Search);
  • en profondeur (Depth-First Search).
• Ces parcours créent un arbre au fil de l'exploration (si le graphe est non-connexe cela crée une forêt, un ensemble d'arbres).

Illustration: parcours en largeur

Exemple

Étape par étape (blanc non-visité)

Étape par étape (gris visité)

Exemple

Étape par étape

Étape par étape (vert à visiter)

Exemple

Étape par étape

Étape par étape

Exemple

Étape par étape

Étape par étape

Exemple

Étape par étape

Étape par étape

Exemple

Étape par étape

Étape par étape

En faisant ce parcours...

::: columns

:::: column

Du parcours de l'arbre

::::

:::: column

Quel arbre est créé par le parcours (2min)?

. . .

graph LR;
    0[x]-->1[w];
    0-->2[t];
    0-->3[y];
    2-->9[u];
    1-->4[s];
    4-->5[r];
    5-->6[v];

::::

:::

Remarques

• Le parcours dépend du point de départ dans le graphe.
• L'arbre sera différent en fonction du noeud de départ, et de l'ordre de parcours des voisins d'un noeud.

Le parcours en largeur

L'algorithme, idée générale (3min, matrix)?

. . .

v = un sommet du graphe
i = 1
pour sommet dans graphe et sommet non-visité
    visiter(v, sommet, i) // marquer sommet à distance i visité 
    i += 1

Remarque

• i est la distance de plus cours chemin entre v et les sommets en cours de visite.

Le parcours en largeur

L'algorithme, pseudo-code (3min, matrix)?

• Comment garder la trace de la distance?

. . .

• Utilisation d'une file

. . .

initialiser(graphe) // tous sommets sont non-visités
file = visiter(sommet, vide) // sommet est un sommet du graphe au hasard
tant que !est_vide(file)
    v = défiler(file)
    file = visiter(v, file)

Que fait visiter?

file visiter(sommet, file)
    sommet = visité
    pour w = chaque arête de sommet
        si w != visité
            file = enfiler(file, w)
    retourne file

Exercice (5min)

Appliquer l'algorithme sur le graphe

• En partant de v, s, ou u (par colonne de classe).
• Bien mettre à chaque étape l'état de la file.

Complexité du parcours en largeur

Étape 1

• Extraire un sommet de la file;

Étape 2

• Traîter tous les sommets adjacents.

Quelle est la complexité?

. . .

• Étape 1: \mathcal{O}(|V|),
• Étape 2: \mathcal{O}(2|E|),
• Total: \mathcal{O}(|V| + |2|E|).

Exercice

• Établir la liste d'adjacence et appliquer l'algorithme de parcours en largeur au graphe

graph LR;
    1---2;
    1---3;
    1---4;
    2---3;
    2---6;
    3---6;
    3---4;
    3---5;
    4---5;

Illustration: parcours en profondeur

Parcours en profondeur

Idée générale

• Initialiser les sommets comme non-lus
• Visiter un sommet
• Pour chaque sommet visité, on visite un sommet adjacent s'il est pas encore visité récursivement.

Remarque

• La récursivité est équivalent à l'utilisation d'une pile.

Parcours en profondeur

Pseudo-code (5min)

. . .

initialiser(graphe) // tous sommets sont non-visités
pile = visiter(sommet, vide) // sommet est un sommet du graphe au hasard
tant que !est_vide(pile)
    v = dépiler(pile)
    pile = visiter(v, pile)

Que fait visiter?

. . .

pile visiter(sommet, pile)
    sommet = visité
    pour w = chaque arête de sommet
        si w != visité
            pile = empiler(pile, w)
    retourne pile

Exercice

• Établir la liste d'adjacence et appliquer l'algorithme de parcours en profondeur au graphe

graph LR;
    1---2;
    1---3;
    1---4;
    2---3;
    2---6;
    3---6;
    3---4;
    3---5;
    4---5;

Interprétation des parcours

• Un graphe vu comme espace d'états (sommet: état, arête: action);
  • Labyrinthe;
  • Arbre des coups d'un jeu.

. . .

• BFS (Breadth-First) ou DFS (Depth-First) parcourent l'espace des états à la recherche du meilleur mouvement.
  • Les deux parcourent tout l'espace;
  • Mais si l'arbre est grand, l'espace est gigantesque!

. . .

• Quand on a un temps limité
  • BFS explore beaucoup de coups dans un futur proche;
  • DFS explore peu de coups dans un futur lointain.