INGIniousArbres et forêts
Un arbre est un graphe connexe qui ne possède pas de cycle. Une forêt est un graphe sans cycle : ses composantes connexes sont donc des arbres. Un nœud isolé est un arbre (à un nœud et sans arête), et un graphe sans arête est une forêt.
Rappel de quelques propriétés équivalentes vues au cours, pour un graphe \(G = (N, R)\) :
- \(G\) est connexe et sans cycle (c'est un arbre) ;
- \(G\) est connexe et \(|R| = |N| - 1\) ;
- \(G\) est sans cycle et \(|R| = |N| - 1\) ;
- \(G\) est sans cycle et lui ajouter une arête crée un et un seul cycle.
À gauche, une forêt de trois arbres (une couleur par arbre). À droite, un graphe qui n'est pas une forêt : l'arête \(3 - 6\) ferme le cycle \((1, 3, 6, 1)\).
Arbres sous-tendants de poids minimum
Soit \(G = (N, R)\) un graphe connexe et \(c : R \to \mathbb{R}^{>0}\) une fonction qui associe un poids à chaque arête. Un arbre \(A = (N, R')\) est un arbre sous-tendant \(G\) si \(R' \subseteq R\) : il relie tous les nœuds de \(G\) en utilisant uniquement des arêtes de \(G\). Son poids est \(c(A) = \sum_{r \in R'} c(r)\). Un arbre sous-tendant de poids minimum est un arbre sous-tendant dont le poids est le plus petit possible. Un graphe possède un arbre sous-tendant si et seulement s'il est connexe.
L'exemple des slides : un arbre sous-tendant de poids minimum (en vert), de poids \(2 + 3 + 4 + 5 + 7 = 21\).
Représentation des graphes et union-find
Dans les deux exercices, le graphe a n nœuds numérotés de 0 à n - 1, et edges est la liste de ses arêtes (non orientées). Le graphe n'est pas forcément simple : une arête peut apparaître plusieurs fois et une arête (u, u) est une boucle.
Les deux exercices reposent sur la même question : si j'ajoute l'arête \(\{u, v\}\) aux arêtes déjà retenues, est-ce que je crée un cycle ? C'est le cas si et seulement si \(u\) et \(v\) sont déjà reliés par un chemin, c'est-à-dire s'ils sont dans la même composante connexe. Pour répondre efficacement à cette question, on vous donne une structure union-find, qui maintient les composantes connexes au fur et à mesure qu'on ajoute des arêtes. Elle n'est pas la matière du cours : vous pouvez l'utiliser telle quelle, sans comprendre son fonctionnement interne. Sur INGInious, la classe UnionFind est déjà importée avant votre code : ne la recopiez pas (pour tester sur votre ordinateur, copiez-la au début de votre fichier).
class UnionFind:
"""Partition des nœuds 0, 1, ..., n - 1 en ensembles disjoints.
Au départ, chaque nœud est seul dans son ensemble. Si on appelle union(u, v) pour chaque arête (u, v)
d'un graphe, les ensembles sont exactement les composantes connexes de ce graphe.
Chaque opération coûte un temps quasi constant.
"""
def __init__(self, n):
self.parent = list(range(n))
self.taille = [1] * n
def find(self, x):
"""Renvoie le représentant de l'ensemble qui contient x.
Deux nœuds sont dans le même ensemble si et seulement s'ils ont le même représentant."""
racine = x
while self.parent[racine] != racine:
racine = self.parent[racine]
while self.parent[x] != racine:
self.parent[x], x = racine, self.parent[x]
return racine
def union(self, x, y):
"""Fusionne l'ensemble qui contient x et celui qui contient y."""
rx, ry = self.find(x), self.find(y)
if rx == ry:
return
if self.taille[rx] < self.taille[ry]:
rx, ry = ry, rx
self.parent[ry] = rx
self.taille[rx] += self.taille[ry]
Exemple d'utilisation :
uf = UnionFind(4) # quatre ensembles : {0}, {1}, {2}, {3}
uf.union(0, 1) # {0, 1}, {2}, {3}
uf.union(2, 3) # {0, 1}, {2, 3}
uf.find(0) == uf.find(1) # True : 0 et 1 sont dans le même ensemble
uf.find(1) == uf.find(2) # False