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. 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.

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

Définition formelle

S est un séparateur du graphe grille. Alors que le graphe grille est connexe, le graphe induit par $V\setminus S$ lui a deux composantes connexes : A et B.

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$ a plus de composantes connexes que $G$, i.e. tel qu'il existe deux sommets $u,v\in V\setminus S$ qui sont reliés par un chemin dans $G$ mais ne le sont plus dans le sous-graphe induit par $V\setminus S$. Dans ce cas on dit que $S$ sépare $u$ de $v$.

Séparateur minimaux

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

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 $(u,v)$-séparateurs de $G$ peut être muni d'un préordre $\sqsubseteq _{u,v}$ définit comme suit: pour tous $(u,v)$-séparateurs $S$ et $T$ de $G$, on a $S\sqsubseteq _{u,v}T$ si $T$ sépare tout sommet de $S\setminus T$ de $v$. Escalante a montré que lorsqu'elle est restreinte aux $(u,v)$-séparateurs minimaux, cette relation définit un treillis complet.

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, comme les graphes de permutation, les graphes d'intersections des cordes d'un cercle ou les graphes d'intervalles circulaires.

Articles connexes

• Décomposition arborescente
• Théorème du séparateur planaire