Séparateur (théorie des graphes)

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
image illustrant la théorie des graphes image illustrant l’informatique théorique
Cet article est une ébauche concernant la théorie des graphes et l’informatique théorique.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

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 , un séparateur est un sous-ensemble de tel que le sous-graphe induit par n'est pas connexe, i.e. tel qu'il existe deux sommets qui ne sont pas reliés par un chemin dans le graphe.

Propriétés[modifier | modifier le code]

Les graphes dont tous les séparateurs minimaux sont des cliques sont les graphes cordaux[4].

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. (en) Reinhard Diestel (de), Graph Theory [détail des éditions], p. 11.
  3. Par exemple dans Jacques Labelle, Théorie des graphes, modulo éditeur, (lire en ligne) page 26
  4. Gabriel Andrew Dirac, « On rigid circuit graphs », Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg, vol. 25,‎ , p. 71-76 (DOI 10.1007/BF02992776).