Séparateur (théorie des graphes)

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En théorie des graphes et en informatique théorique, un séparateur d'un graphe est un sous-ensemble des sommets du graphe dont la suppression rend le graphe non-connexe[1],[2]. Cet objet est intéressant notamment pour décomposer un graphe en des graphes plus petits et plus simples.

On appelle parfois séparateur un ensemble d'arêtes dont la suppression rend le graphe non-connexe[3].

Définition formelle[modifier | modifier le code]

Un separateur du graphe grille.

Pour un graphe G=(V,E), un séparateur est un sous-ensemble S de V tel que le sous-graphe induit par  V \setminus S n'est pas connexe, i.e. tel qu'il existe deux sommets u,v \in V \setminus S qui ne sont pas reliés par un chemin dans le graphe.

Notes et références[modifier | modifier le code]

  1. Fouquet, Théorie des graphes : une brève introduction : avec un biais algébrique assumé (lire en ligne)
  2. Reinhard Diestel, Graph Theory, Springer, coll. « Graduate Texts in Mathematics » (no 173),‎ 2012, 4e éd., 451 p. (ISBN 978-3-642-14278-9, présentation en ligne, lire en ligne), p. 11.
  3. Par exemple dans Jacques Labelle, Théorie des graphes, modulo éditeur,‎ 1981 (lire en ligne) page 26