Elvágó csúcshalmaz
A matematika, azon belül a  gráfelmélet területén csúcsok egy  részhalmaza a nem szomszédos  és  csúcsok tekintetében elvágó csúcshalmaz vagy elvágó ponthalmaz (angol nyelvterületen: vertex separator, vertex cut, separating set), ha a gráfból -t eltávolítva  és  különböző összefüggő komponensekbe kerülnek. Általánosabb megfogalmazásban: egy gráf elvágó csúcshalmaza csúcsok olyan halmaza, melyek elhagyásával a maradék gráf szétesik.

Példák

Tekintsünk egy s sorral és o oszloppal rendelkező rácsgráfot; ekkor a csúcsok n darabszáma éppen s · o. Például az illusztrációban s = 5, o = 8 és n = 40. Ha s páratlan, egyetlen középső sor van, egyébként két a középhez egyformán közel húzódó sor található; hasonlóan, ha o páratlan, egyetlen középső oszlop van, egyébként két a középhez egyformán közel húzódó oszlop van. Ha az S-t ezen középső oszlop vagy sor csúcsaiból választjuk ki, az S gráfból való eltávolítása a gráfot két kisebb, egyenként összefüggő A és B részgráfra osztja, melyek mindegyike legfeljebb n/2 csúcsból áll. Ha s ≤ o (ahogy a példában szerepel), a középső oszlopot választva az S csúcsainak száma s ≤ √n; hasonlóan, ha o ≤ r, akkor egy középső sort választva az elvágó ponthalmaz elemeinek száma legfeljebb √n. Tehát minden rácsgráf rendelkezik legfeljebb √n csúcsból álló S elvágó ponthalmazzal, melynek eltávolítása a gráfot két, legfeljebb n/2 méretű összefüggő komponensre osztja.

Egy más jellegű példa: minden T szabad fa rendelkezik egy olyan S elvágó csúcshalmazzal, ami egyetlen csúcsból áll, és aminek eltávolítása T-t két vagy több összefüggő, legfeljebb n/2 méretű komponensre bontja. Precízebben, minden fa esetében pontosan egy vagy pontosan két ilyen csúcs létezik, attól függően, hogy a fa egy vagy két középpontú (centered, bicentered). 

Az előbbi példák annyiból kivételesnek tekinthetők, hogy nem minden elvágó csúcshalmaz „kiegyensúlyozott”. de ez a tulajdonság a legtöbb számítástudományi alkalmazásban hasznosnak bizonyul, pl..

Minimális elvágó halmazok
Legyen S egy (a,b)-szeparátor, tehát a nem szomszédos a és b csúcsokat elvágó csúcshalmaz. Az S akkor minimális (a,b)-elvágó csúcshalmaz, ha S-nek egyetlen valódi részhalmaza sem elvágó csúcshalmaz a és b tekintetében. Általánosabban, S minimális elvágó csúcshalmaz, ha valamely (a,b) nem szomszédos csúcsokra nézve minimális elvágó csúcshalmaz. A  lokális összefüggőség az  és  csúcsokhoz tartozó minimális elvágó csúcshalmaz mérete.

A minimális elvágó csúcshalmazokat karakterizáló jól ismert eredmény a következő: 

Lemma. Egy G gráf S elvágó csúcshalmaza akkor és csak akkor minimális, ha az S G-ből való eltávolításával kapott  gráf rendelkezik két összefüggő  és  komponenssel, amikre igaz, hogy minden S-beli csúcs szomszédos valamely -beli és valamely -beli csúccsal is.

A minimális elvágó csúcshalmazok algebrai struktúrát is alkotnak: adott G gráf kiválasztott a és b csúcsára nézve valamely S (a,b)-elvágó csúcshalmaz egy másik T (a,b)-elvágó csúcshalmaz elődjének tekinthető, ha minden a és b közötti út először S-t érinti, mielőtt T-t érintené. Ennél precízebben fogalmazva az előd reláció a következőképpen definiálható: legyen S és T két (a,b)-elválasztó csúcshalmaza G gráfnak. Ekkor S elődje T-nek, azaz , ha minden  esetében, az x-et b-vel összekötő összes út érinti T-t. A definícióból következik, hogy az előd reláció előrendezést eredményez az (a,b)-elvágó csúcshalmazok halmazán. Továbbá  igazolta, hogy az előd reláció teljes hálót eredményez, ha G gráf minimális (a,b)-elvágó csúcshalmazaira korlátozzuk.

Kapcsolódó szócikkek
 Húrgráf, olyan gráf, melynek minden minimális elvágó csúcshalmaza klikk.
 k-szorosan összefüggő gráf

Jegyzetek

.
.

Gráfok összefüggősége
A matematika , azon belül a gráfelmélet területén csúcsok egy részhalmaza a nem szomszédos és csúcsok tekintetében elvágó csúcshalmaz vagy elvágó ponthalmaz ( angol nyelvterületen : vertex separator , vertex cut , separating set ) , ha a gráfból -t eltávolítva és különböző összefüggő komponensekbe kerülnek . Általánosabb megfogalmazásban : egy gráf elvágó csúcshalmaza csúcsok olyan halmaza , melyek elhagyásával a maradék gráf szétesik . Példák Tekintsünk egy s sorral és o oszloppal rendelkező rácsgráfot ; ekkor a csúcsok n darabszáma éppen s · o . Például az illusztrációban s = 5 , o = 8 és n = 40. Ha s páratlan , egyetlen középső sor van , egyébként két a középhez egyformán közel húzódó sor található ; hasonlóan , ha o páratlan , egyetlen középső oszlop van , egyébként két a középhez egyformán közel húzódó oszlop van . Ha az S-t ezen középső oszlop vagy sor csúcsaiból választjuk ki , az S gráfból való eltávolítása a gráfot két kisebb , egyenként összefüggő A és B részgráfra osztja , melyek mindegyike legfeljebb n/2 csúcsból áll . Ha s ≤ o ( ahogy a példában szerepel ) , a középső oszlopot választva az S csúcsainak száma s ≤ √n ; hasonlóan , ha o ≤ r , akkor egy középső sort választva az elvágó ponthalmaz elemeinek száma legfeljebb √n . Tehát minden rácsgráf rendelkezik legfeljebb √n csúcsból álló S elvágó ponthalmazzal , melynek eltávolítása a gráfot két , legfeljebb n/2 méretű összefüggő komponensre osztja . Egy más jellegű példa : minden T szabad fa rendelkezik egy olyan S elvágó csúcshalmazzal , ami egyetlen csúcsból áll , és aminek eltávolítása T-t két vagy több összefüggő , legfeljebb n/2 méretű komponensre bontja . Precízebben , minden fa esetében pontosan egy vagy pontosan két ilyen csúcs létezik , attól függően , hogy a fa egy vagy két középpontú ( centered , bicentered ) . Az előbbi példák annyiból kivételesnek tekinthetők , hogy nem minden elvágó csúcshalmaz „ kiegyensúlyozott”. de ez a tulajdonság a legtöbb számítástudományi alkalmazásban hasznosnak bizonyul , pl.. Minimális elvágó halmazok Legyen S egy ( a,b)-szeparátor , tehát a nem szomszédos a és b csúcsokat elvágó csúcshalmaz . Az S akkor minimális ( a,b)-elvágó csúcshalmaz , ha S-nek egyetlen valódi részhalmaza sem elvágó csúcshalmaz a és b tekintetében . Általánosabban , S minimális elvágó csúcshalmaz , ha valamely ( a,b ) nem szomszédos csúcsokra nézve minimális elvágó csúcshalmaz . A lokális összefüggőség az és csúcsokhoz tartozó minimális elvágó csúcshalmaz mérete . A minimális elvágó csúcshalmazokat karakterizáló jól ismert eredmény a következő : Lemma . Egy G gráf S elvágó csúcshalmaza akkor és csak akkor minimális , ha az S G-ből való eltávolításával kapott gráf rendelkezik két összefüggő és komponenssel , amikre igaz , hogy minden S-beli csúcs szomszédos valamely -beli és valamely -beli csúccsal is . A minimális elvágó csúcshalmazok algebrai struktúrát is alkotnak : adott G gráf kiválasztott a és b csúcsára nézve valamely S ( a,b)-elvágó csúcshalmaz egy másik T ( a,b)-elvágó csúcshalmaz elődjének tekinthető , ha minden a és b közötti út először S-t érinti , mielőtt T-t érintené . Ennél precízebben fogalmazva az előd reláció a következőképpen definiálható : legyen S és T két ( a,b)-elválasztó csúcshalmaza G gráfnak . Ekkor S elődje T-nek , azaz , ha minden esetében , az x-et b-vel összekötő összes út érinti T-t . A definícióból következik , hogy az előd reláció előrendezést eredményez az ( a,b)-elvágó csúcshalmazok halmazán . Továbbá igazolta , hogy az előd reláció teljes hálót eredményez , ha G gráf minimális ( a,b)-elvágó csúcshalmazaira korlátozzuk . Kapcsolódó szócikkek Húrgráf , olyan gráf , melynek minden minimális elvágó csúcshalmaza klikk. k-szorosan összefüggő gráf Jegyzetek . . Gráfok összefüggősége