Séparateur (théorie des graphes)

En théorie des graphes et en informatique théorique, un séparateur d'un graphe connexe 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, c'est-à-dire une coupe[3].

Le théorème de Menger relie connectivité et séparateurs minimum.

Définition formelleModifier

 
Un separateur du graphe grille.

Pour un graphe  , un séparateur est un sous-ensemble   de   tel que le sous-graphe induit par   a plus de composantes connexes que  , i.e. tel qu'il existe deux sommets   qui sont reliés par un chemin dans   mais ne le sont plus dans le sous-graphe induit par  . Dans ce cas on dit que   sépare   de  .


Séparateur minimauxModifier

Soit   et   deux sommets appartenant à la même composante connexe d'un graphe  . On appelle  -séparateur minimal tout ensemble de sommets qui sépare   de   et est minimal par inclusion. Un ensemble de sommets de   est un séparateur minimal de   si c'est un  -séparateur minimal, pour certains sommets   et  .

Exemple :

Chaque sommet interne d'un arbre forme un séparateur minimal.

Les séparateurs minimaux peuvent être utilisés pour caractériser les graphes cordaux.

L'ensemble des  -séparateurs de   peut être muni d'un préordre   définit comme suit: pour tous  -séparateurs   et   de  , on a   si   sépare tout sommet de   de  . Escalante a montré que lorsqu'elle est restreinte aux  -séparateurs minimaux, cette relation définit un treillis complet[4].

Les séparateurs minimaux d'un graphe peuvent être utilisés dans la résolution de problèmes algorithmiques. Ainsi, certains problèmes NP-difficiles comme le calcul de la largeur arborescente peuvent être résolus en temps polynomial sur les classes de graphes dont on sait énumérer les séparateurs minimaux en temps polynomial[5], comme les graphes de permutation, les graphes d'intersections des cordes d'un cercle ou les graphes d'intervalles circulaires.

RéférencesModifier

  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. F. Escalante, « Schnittverbände in Graphen », Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg, vol. 38,‎ , p. 199–220 (DOI 10.1007/BF02996932)
  5. T. Kloks, H. Bodlaender, H. Müller et D. Kratsch, « Proc. 1st European Symposium on Algorithms (ESA'93) », Lecture Notes in Computer Science, Springer-Verlag, vol. 726,‎ , p. 260–271 (DOI 10.1007/3-540-57273-2_61)

Article connexeModifier