Vertex separator (grafteori)

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 . $S\undersæt V$ $-en$ $b$ $S$ $-en$ $b$

Eksempler

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.

Minimumsseparatorer

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 . $GS$ $C_{1}$ $C_{2}$ $C_{1}$ $C_{2}$

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 . $S\sqsubseteq _{a,b}^{G}T$ $x\in S\setminus T$

Se også

En akkordgraf er en graf, hvor enhver minimal separator er en klike .

Noter

↑ J. Alan George. Nested dissektion af et regulært finite element mesh // SIAM Journal on Numerical Analysis. - 1973. - T. 10 , no. 2 . - S. 345-363 . - doi : 10.1137/0710032 . — . . I stedet for at bruge grafens rækker og kolonner opdeler George grafen i fire dele ved at kombinere rækkerne og kolonnerne som en separator.
↑ Camille Jordan. Sur les assemblages de lignes (fransk) // Journal für die reine und angewandte Mathematik . - 1869. - T. 70 , Nr. 2 . - S. 185-190 .
↑ Martin Charles Golumbic. Algoritmisk grafteori og perfekte grafer. - Academic Press, 1980. - ISBN 0-12-289260-7 .
↑ F. Escalante. Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg. - 1972. - T. 38. - S. 199-220. - doi : 10.1007/BF02996932 .

Litteratur

Arnold Rosenberg, Lenwood Heath. Grafseparatorer med applikationer. Springer. - 2002. - doi : 10.1007/b115747 .