--- 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 {width=80%} . . . {width=80%} # Les B-arbres: suppression \footnotesize ## Cas simple {width=60%} . . . * 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? . . . {width=60%} # Les B-arbres: suppression ## Cas moins simple {width=60%} . . . * Un élément à droite, comment on fait? * Remonter `7`, serait ok si racine, mais... c'est pas forcément. * On redistribue les feuilles. . . . {width=60%} # Les B-arbres: suppression \footnotesize ## Cas ultra moins simple {width=60%} . . . * `7` seul: * Fusionner les feuilles et redistribuer, comment? . . . {width=60%} # Les B-arbres: suppression ## Cas ultra moins simple {width=60%} . . . * `8` est seul, c'est plus un B-arbre : * Fusionner le niveau 2 et redistribuer, comment? . . . {width=40%} . . . * 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! {width=60%} . . . * On sait comment effacer une valeur d'une feuille, donc? . . . {width=60%} * Ensuite? # Les B-arbres: suppression ## Cas non-feuille! {width=60%} . . . * On sait comment effacer une valeur d'une feuille! . . . {width=60%} # 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? {width=50%} . . . * Réponse: ben non! # Utilisation quotidienne ## Réseau social {width=40%} * Chaque sommet est un individu. * Chaque trait une relation d'amitié. * Miam, Miam, Facebook. # Utilisation quotidienne ## Moteurs de recherche {width=40%} * 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 {width=80%} :::: :::: column {width=80%} :::: ::: # 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 {width=80%} # 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 {width=80%} # 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 {width=80%} # Généralités ## Définition * Une **boucle** est une arête $(v,v)$ d'un sommet vers lui-même. ## Exemples {width=40%} # 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 {width=80%} :::: :::: column {width=60%} :::: ::: # 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 {width=60%} :::: :::: column {width=100%} :::: ::: # 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 {width=100%} # 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 ```{.mermaid format=pdf width=400 loc=figs/} 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 ```{.mermaid format=pdf width=400 loc=figs/} 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 ```{.mermaid format=pdf width=400 loc=figs/} 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 {width=80%} :::: :::: column ## Quelle liste d'adjacence? . . .  :::: ::: # La liste d'adjacence (orienté) ::: columns :::: column ## Quelle liste d'adjacence pour... * Matrix (2min) ```{.mermaid format=pdf width=400 loc=figs/} 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 {width=80%} # Exemple ## Étape par étape (blanc non-visité) {width=50%} ## Étape par étape (gris visité) {width=50%} # Exemple ## Étape par étape {width=50%} ## Étape par étape (vert à visiter) {width=50%} # Exemple ## Étape par étape {width=50%} ## Étape par étape {width=50%} # Exemple ## Étape par étape {width=50%} ## Étape par étape {width=50%} # Exemple ## Étape par étape {width=50%} ## Étape par étape {width=50%} # Exemple ## Étape par étape {width=50%} ## Étape par étape {width=50%} # En faisant ce parcours... ::: columns :::: column ## Du parcours de l'arbre {width=100%} :::: :::: column ## Quel arbre est créé par le parcours (2min)? . . . ```{.mermaid format=pdf width=400 loc=figs/} 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)? . . . ```C 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** . . . ```C 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 {width=50%} * 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 ```{.mermaid format=pdf width=400 loc=figs/} graph LR; 1---2; 1---3; 1---4; 2---3; 2---6; 3---6; 3---4; 3---5; 4---5; ``` # Illustration: parcours en profondeur {width=80%} # 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) . . . ```C 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? . . . ```C 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 ```{.mermaid format=pdf width=400 loc=figs/} 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.