Arbres couvrants

Sous graphes et graphes partiels

Définition On dit qu’un graphe \(G'\) est un graphe partiel d’un graphe \(G=(V;E)\) s’il est formé par les même sommets mais un sous ensemble des arêtes de \(G\). Formellement, \(G'\) est de la forme \((V; F)\) avec \(F\subset E\).

Note : On parle parfois aussi de graphe couvrant.

Note : Ne pas confondre avec la notion de sous-graphe où l’on a aussi un sous ensemble des sommets.

Définition Étant donné un graphe \(G=(V;E)\), on appelle arbre couvrant de \(G\) un graphe \(T=(V;F)\) tel que

  • \(T\) est un arbre;

  • \(T\) est un graphe partiel de \(G\).

Intuitivement : \(T\) est construit avec les arêtes \(U\) de \(G\) en connectant (“couvre”) tous les sommets de \(V\).

../../_images/4x4_grid_spanning_tree.svg ../../_images/Minimum_spanning_tree.svg

Proposition 5. : Un graphe \(G=(V;E)\) admet un arbre couvrant si et seulement si il est connexe.

Preuve : Le sens direct est évident, si \(G\) admet un graphe partiel connexe alors \(G\) est connexe.

On prouve la réciproque avec l’algorithme suivant:

on pose T := G
tant que que T admet un cycle C
    // Invariant : T est un graphe partiel connexe de G
    supprimer dans T une arête du cycle C
renvoyer T

En effet, supprimer une arête d’un cycle d’un graphe, ne change pas sa connexité (pourquoi ?). En conséquence quand ou sort de la boucle, T contient un graphe partiel connexe et sans cycle de G.

Note : L’algorithme ci dessus n’est pas efficace. On verra ci-dessous deux algorithmes plus efficaces, dû à Kruskal et Prim.

  • Implanter l’algorithme ci-dessus.

  • Vérifier sur tous les graphes connexe que le résultat est bien un arbre.

YOUR ANSWER HERE

Exercice 1. : Combien d’arbres couvrants différents les graphes ci-contre possèdent-ils ? ../../_images/arb-000.jpg

# YOUR CODE HERE
raise NotImplementedError()

Arbre couvrant de poids minimum

Soit un graphe où l’on a mis un poids sur les arêtes.

Le problème de l’arbre couvrant de poids minimum consiste à trouver un arbre couvrant dont la somme des poids \(c(e)\) des arêtes est minimum.

Ne pas confondre:

  • arbre couvrant de poids minimum (MST, Minimum Spanning Tree) : minimise la somme des poids des arêtes

  • arbre des plus courts chemins (SPT, Shortest Paths Tree) construit par exemple par BFS (Breadth First Search) ou Dijsktra : minimise la distance de la racine à chaque sommet

Voici deux arbres convrants (en rouge). Le premier est de poids \(14\), le deuxieme de poids \(10\).

Il y a deux algorithmes classiques pour calculer un arbre couvrant de poids minimum:

  • l’algorithme de Kruskal

  • l’algorithme de Prim

Algorithme de Kruskal

Idée : On part du graphe \(T=(V, \emptyset)\) et on ajoute tour à tour la nouvelle arête de plus petit poids qui ne crée pas de cycles (i.e. qui connecte deux composantes connexes différentes).

Invariant : À l’étape \(i\), le graphe \(T\) est acyclique avec \(i\) arêtes de poids minimal

Algorithme de Prim

Idée : On choisi un noeuds \(n\) part du graphe \(T=(\{n\}, \emptyset)\) et on ajoute tour à tour un nouveau noeud en le connectant autre en choisissant l’arête de poids minimum parmis.

Invariant : Le graphe \(T=(U,F)\) est toujours l’arbre convrant de poids minimal sur \(U\subset V\).