I grafteori kaldes en delmængde af knudepunkter en toppunktseparator for ikke-tilstødende knudepunkter , og hvis fjernelse fra grafen adskilles og i to forbundne komponenter .
Antag, at givet et gitter med r rækker og c kolonner, så er det samlede antal n hjørner r*c . For eksempel på figuren er r = 5, c = 8 og n = 40. Hvis r er ulige, er der én central række, ellers er der to rækker lige tæt på midten. På samme måde, hvis c er ulige, er der én central kolonne, ellers er der to kolonner lige tæt på midten. Ved at vælge en af disse rækker eller kolonner som S , og fjerne S fra grafen, opnår vi en opdeling af grafen i to mindre forbundne undergrafer A og B , som hver især indeholder højst n /2 hjørner. Hvis r ≤ c (som i illustrationen), så vil valg af midtersøjlen give en separator S med r ≤ √ n hjørner, og på samme måde, hvis c ≤ r , vil valg af midterrækken give en separator med højst √ n hjørner . Ethvert grafgitter har således en separator S med størrelse højst √ n , hvis fjernelse deler grafen i to forbundne komponenter, hver med størrelse højst n /2 [1] .
En anden klasse af eksempler er et frit træ T , der har en enkelt-vertex-separator S , hvis fjernelse opdeler T i to (eller flere) forbundne komponenter, hver af størrelsen højst n /2. Mere præcist er der præcis et eller to hjørner, afhængigt af om træet er centreret eller bicenteret [2] .
I modsætning til de givne eksempler er ikke alle toppunktseparatorer afbalancerede , men denne egenskab er mest anvendelig til computervidenskabelige applikationer.
Lad S være en (a,b) -separator, det vil sige en delmængde af toppunkter, der adskiller to ikke-tilstødende toppunkter a og b . Så er S en minimal (a,b)-separator, hvis ingen delmængde af S adskiller a og b . Et sæt S kaldes en minimal separator , hvis det er en minimal separator for ethvert par (a,b) af ikke-tilstødende hjørner. Nedenfor er et velkendt resultat vedrørende karakterisering af minimale separatorer [3] :
Lemma. En toppunktsseparator S i G er minimal, hvis og kun hvis grafen opnået ved at fjerne S fra G har to forbundne komponenter og sådan, at hvert toppunkt i S er forbundet med et toppunkt i og noget toppunkt i .
Minimale separatorer danner et algebraisk system : for to faste hjørner a og b i en given graf G , kan en (a,b) -separator S betragtes som en forgænger for en anden (a,b)-separator T , hvis der er nogen vej fra a til b rammer S før, end at komme til T . Mere strengt defineres præcedensrelationen som følger: Lad S og T være to (a,b) -separatorer i 'G'. Så er S forgængeren til T , som betegnes som om, for et hvilket som helst toppunkt , enhver sti mellem x og b indeholder et toppunkt fra T . Det følger af definitionen, at præcedensrelationen er en forudbestilling på mængden af alle (a,b) -separatorer. Desuden beviste Escalante [4] , at præcedensrelationen bliver et komplet gitter, hvis vi begrænser os til sættet af minimale (a,b) -separatorer G .