Séparateur (théorie des graphes)

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

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

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

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

• Portail des mathématiques
• Portail de l'informatique théorique