Кіріспе
Графтың түйіндерінің жиынтығы, егер алынып тасталса, берілген түйіндер жұбын бөліп тастайды. Граф теориясында, S ⊆ V жиыны – егер графтан S-ті алып тастау a және b түйіндерін жеке байланысқан компоненттерге бөліп тастаса, жанаспайтын a және b түйіндері үшін түйін бөлгіші (немесе түйін кесімі, бөлу жиынтығы) болып табылады.
In graph theory, a vertex subset S \subset V is a vertex separator (or vertex cut, separating set) for nonadjacent vertices a and b if the removal of S from the graph separates a and b into distinct connected components.
Мысалдар
r қатарлы және c бағаналы тор графигін қарастырайық; n төбелерінің жалпы саны r × c-ға тең. Мысалы, суретте r = 5, c = 8, және n = 40. Егер r тақ болса, онда ортада бір қатар болады, әйтпесе ортаға бірдей жақын екі қатар болады; ұқсас түрде, егер c тақ болса, онда ортада бір баған болады, әйтпесе ортаға бірдей жақын екі баған болады. S-ті осы орталық қатарлар мен бағандардың кез келгені ретінде таңдап, S-ті графиктен алып тастау графикті екі кішірек байланысты A және B подграфтарына бөледі, олардың әрқайсысының ең көп төбесі болады. Егер r ≤ c (суреттегідей) болса, онда орталық бағанды таңдау төбелері бар S бөлгішін береді, ал егер c ≤ r болса, онда орталық қатарды таңдау ең көп төбелері бар бөлгішін береді. Осылайша, әрбір тор графигінің S өлшемді бөлгіші бар, оны алып тастау екі байланысты компонентке бөледі, олардың әрқайсысының мөлшері ең көп . Тағы бір мысалдар класын келтіру үшін, әрбір еркін ағаш T-де бір төбеден тұратын S бөлгіші болады, оны алып тастау T-ді екі немесе одан да көп байланысты компонентке бөледі, олардың әрқайсысының мөлшері ең көп . Нақтырақ айтқанда, әрқашан дәл бір немесе дәл екі төбе болады, олар осындай бөлгішке тең, ағаштың орталық немесе екі орталыққа ие болуына байланысты. Бұл мысалдардан айырмашылығы, барлық төбелік бөлгіштер теңдестірілмейді, бірақ бұл қасиет компьютерлік ғылымдағы қолданбалар үшін, мысалы, жазықтық бөлгіш теоремасы үшін өте пайдалы.
To give another class of examples, every free tree T has a separator S consisting of a single vertex, the removal of which partitions T into two or more connected components, each of size at most More precisely, there is always exactly one or exactly two vertices, which amount to such a separator, depending on whether the tree is centered or bicentered. As opposed to these examples, not all vertex separators are balanced, but that property is most useful for applications in computer science, such as the planar separator theorem.
Ең аз бөлгіштер
S болсын (a,b) бөлгіші, яғни, а және b екі іргелес емес төбелерді бөліп тұратын төбелердің ішкі жиыны. Егер S-тің а және b-ді бөлетін дұрыс ішкі жиыны болмаса, онда S – минималды (a,b) бөлгіш. Жалпы алғанда, S – егер ол екі іргелес емес төбелердің (a,b) жұбы үшін минималды бөлгіш болса, минималды бөлгіш деп аталады. Бұл, S-тің ешбір дұрыс ішкі жиыны кез келген (u,v) төбелер жұбы үшін минималды (u,v) бөлгіш емес екенін көрсететін минималды бөлгіш жиынынан өзгеше екенін ескеріңіз. Минималды бөлгіштерді сипаттайтын жақсы белгілі нәтиже:
Лемма. G графигіндегі S төбелік бөлгіші, егер және тек қана G-ден S-ті алып тастау арқылы алынған G – S графигінің екі байланысқан компоненті болса және S-дегі әрбір төбе S-дегі кейбір төбеге және екінші компоненттегі кейбір төбеге іргелес болса, онда ғана минималды болады. Минималды (a,b) бөлгіштер де алгебралық құрылымды құрайды: берілген G графигінің a және b екі белгілі төбелері үшін (a,b) бөлгіші S-ді басқа (a,b) бөлгіш T-нің алдағысы ретінде қарастыруға болады, егер a-дан b-ге дейінгі әрбір жол S-ге дейін T-ге жетпесе. Нақтырақ айтқанда, алдағы қатынас былай анықталады: S және T G графигіндегі екі (a,b) бөлгіштері болсын. Онда S, T-нің алдағысы болады, яғни , егер S \ T-дегі әрбір x үшін, x-тен b-ге дейінгі әрбір жол T-ге кездессе. Анықтамадан, алдағы қатынас (a,b) бөлгіштерінің барлық жиынындағы преордерді тудырады. Сонымен қатар, G-дегі минималды (a,b) бөлгіштер жиынымен шектелген кезде алдағы қатынас толық торға әкелетінін дәлелдеді.
The minimal (a,b) separators also form an algebraic structure: For two fixed vertices a and b of a given graph G, an (a,b) separator S can be regarded as a predecessor of another (a,b) separator T, if every path from a to b meets S before it meets T. More rigorously, the predecessor relation is defined as follows: Let S and T be two (a,b) separators in G. Then S is a predecessor of T, in symbols , if for each x ∈ S \ T, every path connecting x to b meets T. It follows from the definition that the predecessor relation yields a preorder on the set of all (a,b) separators. Furthermore, proved that the predecessor relation gives rise to a complete lattice when restricted to the set of minimal (a,b) separators in G.