Construisez un arbre couvrant de coût minimal

Une collectivité veut relier par la fibre optique six communes de la métropole rennaise. Tirer un câble entre deux communes a un coût, et toutes les liaisons ne sont pas possibles. Il faut que chaque commune soit reliée à toutes les autres, directement ou non, pour le moins cher possible. Faut-il des boucles dans le réseau ? Non : une boucle, c’est un câble de trop. On cherche donc un arbre, et plus précisément un arbre couvrant de coût minimal.

Ce chapitre commence par ce qu’est un arbre (la notion a plusieurs définitions équivalentes, toutes utiles), puis présente les deux grands algorithmes gloutons qui résolvent ce problème : Kruskal et Prim.

Qu’est-ce qu’un arbre ?

Six définitions pour un même objet

Un arbre est un graphe non orienté connexe et sans cycle. Pour un graphe à $n \geq 2$ sommets, les propriétés suivantes sont équivalentes (chacune suffit à dire que c’est un arbre) :

il est connexe et sans cycle ;
il est connexe et a exactement $n - 1$ arêtes ;
il est sans cycle et a exactement $n - 1$ arêtes ;
il est sans cycle, et l’ajout de n’importe quelle arête crée exactement un cycle ;
il est connexe, et la suppression de n’importe quelle arête le déconnecte (il est minimal pour la connexité : chaque arête est un isthme) ;
entre deux sommets quelconques, il existe une chaîne et une seule.

Ces équivalences sont très pratiques : pour vérifier qu’un graphe est un arbre, il suffit souvent de compter ses arêtes et de vérifier une seule autre propriété. Un graphe sans cycle, pas forcément connexe, s’appelle une forêt : chacune de ses composantes connexes est un arbre.

À n = 5 sommets, 4 arêtes est le seul nombre qui donne un arbre : une de moins déconnecte, une de plus crée un cycle.

Le nombre cyclomatique

Combien d’arêtes « en trop » un graphe a-t-il par rapport à une forêt ? C’est son nombre cyclomatique :

\nu(G) = m - n + p

où $m$ est le nombre d’arêtes, $n$ le nombre de sommets et $p$ le nombre de composantes connexes. On a toujours $\nu(G) \geq 0$ , et $\nu(G) = 0$ si et seulement si $G$ est une forêt. Le nombre cyclomatique compte les cycles « indépendants » (c’est la dimension de la base des cycles) : c’est exactement le nombre d’arêtes qu’il faut retirer pour casser tous les cycles sans déconnecter le graphe.

Vous l’avez peut-être croisé en génie logiciel : la complexité cyclomatique d’un programme (nombre de chemins indépendants dans son graphe de contrôle) est la même formule, appliquée au graphe du flot d’exécution.

Arbres couvrants et arborescences

Un arbre couvrant (spanning tree) d’un graphe $G$ est un graphe partiel de $G$ (tous les sommets, une partie des arêtes) qui est un arbre. Un graphe admet un arbre couvrant si et seulement s’il est connexe : il suffit de retirer des arêtes de cycles tant qu’il en reste. Le BFS et le DFS du chapitre 2 en construisent un gratuitement (l’arbre des parents).

Dans un graphe orienté, l’équivalent est l’arborescence de racine $r$ : un arbre dont les arcs sont orientés de sorte que $r$ atteigne chaque sommet par un chemin unique. Concrètement : $d^-(r) = 0$ , $d^-(x) = 1$ pour tout autre sommet, et pas de cycle. L’arborescence des répertoires d’un disque dur, ou l’arbre des plus courts chemins depuis une source (chapitre 7), en sont des exemples.

Le fil rouge : relier six communes

Les six communes sont Rennes (R), Cesson-Sévigné (C), Chantepie (H), Saint-Grégoire (G), Pacé (P) et Bruz (Z). Les liaisons possibles et leur coût, en centaines de milliers d’euros :

Liaison	C-H	R-G	R-C	G-P	R-H	C-G	R-P	R-Z	H-Z	P-Z
Coût	4	5	6	6	7	8	9	11	13	14

Le graphe a $n = 6$ sommets et $m = 10$ arêtes. Un arbre couvrant en gardera $n - 1 = 5$ : il faut donc écarter $\nu = 10 - 6 + 1 = 5$ liaisons. Le coût d’un arbre est la somme des coûts de ses arêtes, et l’on cherche un arbre couvrant de coût minimum (ACM, en anglais minimum spanning tree). Les arêtes en surbrillance sur le schéma sont la solution : voyons comment la trouver.

L’algorithme de Kruskal

Trier, puis ajouter sans créer de cycle

L’idée de Kruskal est d’une simplicité désarmante :

Trier les arêtes par coût croissant.
Les examiner dans cet ordre, et ajouter chaque arête qui ne crée pas de cycle avec celles déjà retenues.
S’arrêter quand on a retenu $n - 1$ arêtes.

Arête	Coût	Décision	Blocs reliés après l’étape
C-H	4	gardée	$\lbrace C, H \rbrace$
R-G	5	gardée	$\lbrace C, H \rbrace$ , $\lbrace R, G \rbrace$
R-C	6	gardée	$\lbrace R, G, C, H \rbrace$
G-P	6	gardée	$\lbrace R, G, C, H, P \rbrace$
R-H	7	rejetée : R et H sont déjà reliés (cycle R, C, H)
C-G	8	rejetée : cycle R, G, C
R-P	9	rejetée : cycle R, G, P
R-Z	11	gardée : c’est la 5e arête, on s’arrête	$\lbrace R, G, C, H, P, Z \rbrace$

L’arbre retenu (C-H, R-G, R-C, G-P, R-Z) coûte $4 + 5 + 6 + 6 + 11 = 32$ , soit 3,2 millions d’euros.

Kruskal examine les arêtes de la moins chère à la plus chère et rejette R-H, C-G et R-P, qui fermeraient un cycle. L'arbre final coûte 32.

Au passage, remarquez que Kruskal manipule une forêt qui grossit : au début, chaque sommet est seul ; chaque arête retenue fusionne deux arbres. Tester « cette arête crée-t-elle un cycle ? » revient à tester « ses deux extrémités sont-elles déjà dans le même arbre ? ».

La structure union-find

Pour répondre vite à cette question, on utilise une structure union-find (ensembles disjoints) : chaque sommet pointe vers un représentant de son bloc ; trouver(x) renvoie ce représentant, et unir(x, y) fusionne deux blocs.

def kruskal(sommets, aretes):
    """aretes : liste de (cout, u, v). Renvoie l'arbre couvrant minimal et son coût."""
    parent = {x: x for x in sommets}

    def trouver(x):                           # représentant du bloc de x
        while parent[x] != x:
            parent[x] = parent[parent[x]]     # compression de chemin (raccourci)
            x = parent[x]
        return x

    arbre, total = [], 0
    for cout, u, v in sorted(aretes):         # coûts croissants
        ru, rv = trouver(u), trouver(v)
        if ru != rv:                          # pas dans le même bloc : pas de cycle
            parent[ru] = rv                   # union des deux blocs
            arbre.append((u, v, cout))
            total += cout
            if len(arbre) == len(sommets) - 1:
                break
    return arbre, total

aretes = [(6, "R", "C"), (7, "R", "H"), (5, "R", "G"), (9, "R", "P"), (11, "R", "Z"),
          (4, "C", "H"), (8, "C", "G"), (6, "G", "P"), (14, "P", "Z"), (13, "H", "Z")]
print(kruskal("RCHGPZ", aretes))              # coût total 32

Le tri coûte $O(m \log m)$ et, avec union-find, le reste est quasi linéaire : Kruskal est en $O(m \log m)$ . Il est particulièrement adapté aux graphes creux.

Il existe aussi une version « à l’envers », vue en cours : partir du graphe complet et supprimer les arêtes par coût décroissant, tant que la suppression ne déconnecte pas le graphe. On supprime alors exactement $m - n + 1 = \nu$ arêtes, et on obtient le même arbre.

L’algorithme de Prim

Faire pousser un seul arbre

Prim procède autrement : il fait croître un seul arbre à partir d’un sommet de départ. À chaque étape, il ajoute l’arête la moins chère qui sort de l’arbre, c’est-à-dire l’arête de coût minimal du cocycle $\omega(A)$ , où $A$ est l’ensemble des sommets déjà dans l’arbre.

Prim fait grandir un seul arbre depuis R en prenant à chaque fois la moins chère des arêtes qui sortent de A. Il retrouve l'arbre de Kruskal.

Avec une matrice et un tableau des meilleures arêtes, Prim est en $O(n^2)$ , ce qui est optimal pour un graphe dense. Avec un tas (file de priorité), il passe en $O(m \log n)$ .

Pourquoi ces algorithmes gloutons sont-ils justes ?

Un algorithme glouton fait à chaque étape le choix qui semble le meilleur, sans jamais revenir dessus. En général, c’est une mauvaise stratégie (vous le verrez pour la coloration au chapitre suivant). Mais ici, une propriété garantit le résultat :

L’argument est un échange : si un ACM n’utilisait pas cette arête $e$ , l’y ajouter créerait un cycle, qui traverse forcément la coupe par une autre arête $e'$ au moins aussi chère. Remplacer $e'$ par $e$ donne un arbre couvrant de coût inférieur ou égal : il est donc lui aussi minimal.

Pour A = {R, G, P}, les arêtes qui traversent la coupe coûtent 6, 7, 8, 11 et 14 : la moins chère, R-C, fait partie d'un arbre couvrant minimal.

	Kruskal	Prim
Principe	trier les arêtes, ajouter sans cycle	faire croître un arbre depuis un sommet
Structure clé	union-find	file de priorité (tas)
Complexité	$O(m \log m)$	$O(n^2)$ en matrice, $O(m \log n)$ avec tas
Plutôt pour	graphes creux, arêtes déjà triées	graphes denses
Pendant l’exécution	une forêt qui fusionne	un seul arbre qui grandit

import networkx as nx

G = nx.Graph()
G.add_weighted_edges_from([(u, v, c) for c, u, v in aretes])
acm = nx.minimum_spanning_tree(G, algorithm="kruskal")    # ou "prim"
print(sorted(acm.edges(data="weight")), acm.size(weight="weight"))   # coût 32

L’arbre couvrant minimal sert aussi en data : le clustering hiérarchique à lien simple (single linkage) revient exactement à construire l’ACM des points (avec les distances comme coûts) puis à couper ses $k - 1$ arêtes les plus longues pour obtenir $k$ groupes.

En résumé

Un arbre est un graphe connexe sans cycle ; à $n$ sommets, il a exactement $n - 1$ arêtes, et plusieurs définitions équivalentes permettent de le reconnaître.
Le nombre cyclomatique $\nu(G) = m - n + p$ compte les arêtes en trop par rapport à une forêt ; il est nul si et seulement si $G$ est une forêt.
Un graphe admet un arbre couvrant si et seulement s’il est connexe ; l’équivalent orienté est l’arborescence.
Kruskal trie les arêtes et ajoute celles qui ne créent pas de cycle (union-find, $O(m \log m)$ ) ; Prim fait croître un arbre par l’arête minimale du cocycle ( $O(n^2)$ ou $O(m \log n)$ ).
Leur justesse repose sur la propriété de la coupe ; l’ACM n’est pas forcément unique, mais son coût l’est.

Exercices

Exercice · Vérifier un arbre

facile

Un graphe a 8 sommets, 7 arêtes et aucun cycle. Est-ce un arbre ? Un autre graphe a 8 sommets, 10 arêtes et 2 composantes connexes : quel est son nombre cyclomatique, et combien d’arêtes faut-il retirer pour obtenir une forêt couvrante ?

Voir la solution

Le premier graphe est sans cycle et a $n - 1 = 7$ arêtes : d’après la définition 3, c’est un arbre (il est donc automatiquement connexe).

Pour le second, $\nu = m - n + p = 10 - 8 + 2 = 4$ . Il faut retirer 4 arêtes, prises dans des cycles, pour obtenir une forêt couvrante de 2 arbres, qui aura $8 - 2 = 6$ arêtes.

En code

Python
R

def foret(n, aretes):
    """Union-find : renvoie (arêtes gardées, arêtes rejetées car elles fermeraient un cycle)."""
    parent = list(range(n))
    def trouver(x):
        while parent[x] != x:
            x = parent[x]
        return x
    gardees, rejetees = 0, 0
    for u, v in aretes:
        ru, rv = trouver(u), trouver(v)
        if ru == rv:
            rejetees += 1                    # u et v déjà reliés : cette arête ferme un cycle
        else:
            parent[ru] = rv
            gardees += 1
    return gardees, rejetees

# Premier graphe : 8 sommets, 7 arêtes, sans cycle (ici une chaîne)
print(foret(8, [(i, i + 1) for i in range(7)]))   # (7, 0) : 7 = n - 1 arêtes gardées, c'est un arbre

# Second graphe : un K4 + une arête pendante (sommets 0 à 4) et un triangle (5, 6, 7)
aretes = [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3), (3, 4), (5, 6), (6, 7), (5, 7)]
n, m, p = 8, len(aretes), 2
print(m - n + p, foret(n, aretes))   # 4 (6, 4) : nu = 4 arêtes rejetées, forêt de 6 arêtes

foret <- function(n, aretes) {
  # renvoie (arêtes gardées, arêtes rejetées car elles fermeraient un cycle)
  bloc <- 1:n
  gardees <- 0; rejetees <- 0
  for (k in 1:nrow(aretes)) {
    a <- bloc[aretes[k, 1]]; b <- bloc[aretes[k, 2]]
    if (a == b) rejetees <- rejetees + 1       # déjà reliés : cette arête ferme un cycle
    else { bloc[bloc == b] <- a; gardees <- gardees + 1 }
  }
  c(gardees = gardees, rejetees = rejetees)
}

# Premier graphe : 8 sommets, 7 arêtes, sans cycle (ici une chaîne)
foret(8, cbind(1:7, 2:8))      # 7 0 : 7 = n - 1 arêtes gardées, c'est un arbre

# Second graphe : un K4 + une arête pendante (sommets 1 à 5) et un triangle (6, 7, 8)
aretes <- rbind(c(1, 2), c(1, 3), c(1, 4), c(2, 3), c(2, 4), c(3, 4), c(4, 5),
                c(6, 7), c(7, 8), c(6, 8))
nrow(aretes) - 8 + 2           # nu = 4
foret(8, aretes)               # 6 4 : 4 arêtes rejetées, forêt de 6 arêtes

Exercice · Dérouler Prim depuis Bruz

moyen

Déroulez l’algorithme de Prim sur le réseau des six communes, en partant de Bruz (Z). Retrouvez-vous le même coût ?

Voir la solution

$A = \lbrace Z \rbrace$ : candidates R-Z 11, H-Z 13, P-Z 14. On prend R-Z (11).
$A = \lbrace Z, R \rbrace$ : candidates R-G 5, R-C 6, R-H 7, R-P 9, H-Z 13, P-Z 14. On prend R-G (5).
$A = \lbrace Z, R, G \rbrace$ : R-C 6 et G-P 6 sont à égalité ; prenons R-C (6).
$A = \lbrace Z, R, G, C \rbrace$ : C-H 4 devient la moins chère, on prend C-H (4).
$A = \lbrace Z, R, G, C, H \rbrace$ : il reste P, par G-P 6, R-P 9 ou P-Z 14. On prend G-P (6).

Coût : $11 + 5 + 6 + 4 + 6 = 32$ . C’est le même arbre, construit dans un autre ordre : le sommet de départ ne change pas le coût de l’ACM.

En code

Python
R

cout = {("R", "C"): 6, ("R", "H"): 7, ("R", "G"): 5, ("R", "P"): 9, ("R", "Z"): 11,
        ("C", "H"): 4, ("C", "G"): 8, ("G", "P"): 6, ("P", "Z"): 14, ("H", "Z"): 13}
voisins = {x: {} for x in "RCHGPZ"}
for (u, v), c in cout.items():
    voisins[u][v] = voisins[v][u] = c

def prim(voisins, depart):
    arbre = {depart}
    meilleur = {y: (c, depart) for y, c in voisins[depart].items()}   # arête la moins chère vers y
    aretes, total = [], 0
    while meilleur:
        y = min(meilleur, key=lambda s: (meilleur[s][0], s))   # arête minimale du cocycle
                                                              # (égalité : ordre alphabétique)
        c, x = meilleur.pop(y)
        arbre.add(y)
        aretes.append(f"{x}-{y} ({c})")
        total += c
        for z, cz in voisins[y].items():                  # y offre peut-être de meilleures arêtes
            if z not in arbre and cz < meilleur.get(z, (float("inf"),))[0]:
                meilleur[z] = (cz, y)
    return aretes, total

print(prim(voisins, "Z"))
# (['Z-R (11)', 'R-G (5)', 'R-C (6)', 'C-H (4)', 'G-P (6)'], 32)

villes <- c("R", "C", "H", "G", "P", "Z")
W <- matrix(Inf, 6, 6, dimnames = list(villes, villes))
liaisons <- rbind(c("R", "C", 6), c("R", "H", 7), c("R", "G", 5), c("R", "P", 9), c("R", "Z", 11),
                  c("C", "H", 4), c("C", "G", 8), c("G", "P", 6), c("P", "Z", 14), c("H", "Z", 13))
W[liaisons[, 1:2]] <- W[liaisons[, 2:1]] <- as.numeric(liaisons[, 3])

prim <- function(W, depart) {
  dans_arbre <- rownames(W) == depart
  meilleur <- W[depart, ]; origine <- rep(depart, nrow(W))   # arête la moins chère vers chaque ville
  total <- 0
  while (!all(dans_arbre)) {
    y <- which.min(ifelse(dans_arbre, Inf, meilleur))         # arête minimale du cocycle
    cat(origine[y], "-", rownames(W)[y], " (", meilleur[y], ")\n", sep = "")
    total <- total + meilleur[y]; dans_arbre[y] <- TRUE
    mieux <- W[y, ] < meilleur                                # y offre de meilleures arêtes
    meilleur[mieux] <- W[y, mieux]; origine[mieux] <- rownames(W)[y]
  }
  unname(total)
}
prim(W, "Z")   # Z-R (11), R-G (5), R-C (6), C-H (4), G-P (6) ; total 32

Exercice · Une liaison en promotion

difficile

L’opérateur propose la liaison Pacé-Bruz (P-Z) à 10 au lieu de 14. L’arbre optimal change-t-il ? Même question si c’est la liaison Rennes-Chantepie (R-H) qui passe de 7 à 3. Justifiez sans tout recalculer, en utilisant l’ajout d’une arête à l’arbre.

Voir la solution

Méthode : ajouter l’arête modifiée à l’arbre actuel crée exactement un cycle (définition 4 d’un arbre). Si l’arête modifiée est plus chère que toutes les autres arêtes de ce cycle, l’arbre reste optimal ; sinon, on retire l’arête la plus chère du cycle.

P-Z à 10 : le cycle créé est P, Z, R, G, P, avec les arêtes P-Z 10, R-Z 11, R-G 5, G-P 6. L’arête la plus chère est R-Z (11) : on la remplace par P-Z. Nouvel arbre : C-H, R-G, R-C, G-P, P-Z, de coût $32 - 11 + 10 = 31$ .
R-H à 3 : le cycle créé est R, H, C, R, avec R-H 3, C-H 4 et R-C 6. On retire R-C (6), la plus chère. Nouvel arbre : R-H, C-H, R-G, G-P, R-Z, de coût $32 - 6 + 3 = 29$ . On peut vérifier avec Kruskal : R-H 3, C-H 4, R-G 5, puis R-C est rejetée (cycle R, H, C), G-P 6, et enfin R-Z 11.

En code

Python
R

def kruskal(sommets, aretes):
    parent = {x: x for x in sommets}
    def trouver(x):
        while parent[x] != x:
            x = parent[x]
        return x
    arbre, total = [], 0
    for c, u, v in sorted(aretes):          # coûts croissants
        ru, rv = trouver(u), trouver(v)
        if ru != rv:                        # pas de cycle : on garde l'arête
            parent[ru] = rv
            arbre.append(f"{u}-{v}")
            total += c
    return arbre, total

base = {("R", "C"): 6, ("R", "H"): 7, ("R", "G"): 5, ("R", "P"): 9, ("R", "Z"): 11,
        ("C", "H"): 4, ("C", "G"): 8, ("G", "P"): 6, ("P", "Z"): 14, ("H", "Z"): 13}
for modif in [{}, {("P", "Z"): 10}, {("R", "H"): 3}]:
    couts = {**base, **modif}
    print(kruskal("RCHGPZ", [(c, u, v) for (u, v), c in couts.items()]))
# (['C-H', 'R-G', 'G-P', 'R-C', 'R-Z'], 32)
# (['C-H', 'R-G', 'G-P', 'R-C', 'P-Z'], 31)
# (['R-H', 'C-H', 'R-G', 'G-P', 'R-Z'], 29)

kruskal <- function(aretes) {
  aretes <- aretes[order(aretes$cout), ]              # coûts croissants
  bloc <- setNames(seq_along(unique(c(aretes$u, aretes$v))), unique(c(aretes$u, aretes$v)))
  garde <- logical(nrow(aretes))
  for (k in 1:nrow(aretes)) {
    a <- bloc[aretes$u[k]]; b <- bloc[aretes$v[k]]
    if (a != b) { bloc[bloc == b] <- a; garde[k] <- TRUE }   # pas de cycle : on garde
  }
  cat(paste0(aretes$u, "-", aretes$v)[garde], " coût", sum(aretes$cout[garde]), "\n")
}

base <- data.frame(u = c("R", "R", "R", "R", "R", "C", "C", "G", "P", "H"),
                   v = c("C", "H", "G", "P", "Z", "H", "G", "P", "Z", "Z"),
                   cout = c(6, 7, 5, 9, 11, 4, 8, 6, 14, 13))
kruskal(base)                                           # C-H R-G R-C G-P R-Z  coût 32
promo <- base; promo$cout[promo$u == "P" & promo$v == "Z"] <- 10
kruskal(promo)                                          # C-H R-G R-C G-P P-Z  coût 31
promo <- base; promo$cout[promo$u == "R" & promo$v == "H"] <- 3
kruskal(promo)                                          # R-H C-H R-G G-P R-Z  coût 29