頂点セパレータ

グラフ理論において、グラフからSを除去するとaとb が異なる連結成分に分離される場合、頂点部分集合 ⁠ ⁠${\displaystyle S\subset V}$は、隣接していない頂点aとb の頂点セパレータ（または頂点カット、分離集合）と呼ばれます。

r行c列のグリッド グラフを考えます。頂点の総数nはr × cです。たとえば、図では、r = 5、c = 8、n = 40です。rが奇数の場合は中央の行が 1 つあり、それ以外の場合は中心に等しく近い行が 2 つあります。同様に、cが奇数の場合は中央の列が 1 つあり、それ以外の場合は中心に等しく近い列が 2 つあります。S をこれらの中央の行または列のいずれかに選択し、グラフからS を削除すると、グラフは 2 つの小さな接続されたサブグラフAとBに分割され、それぞれのサブグラフの頂点は最大でn ⁄ 2になります。r ≤ c (図のように) の場合は、中央の列を選択すると頂点を持つセパレーターSが生成され、同様に、c ≤ rの場合は中央の行を選択すると頂点が最大で 個のセパレーターが生成されます。したがって、すべてのグリッドグラフには最大でn ⁄ 2のサイズのセパレータSがあり、これを除去すると2つの接続されたコンポーネントに分割され、それぞれのサイズは最大でn ⁄ 2になります。^[1]${\displaystyle r\leq {\sqrt {n}}}$${\displaystyle {\sqrt {n}}}$${\displaystyle {\sqrt {n}},}$

別の例として、すべての自由木 Tには単一の頂点からなるセパレータSがあり、このセパレータ S を削除すると、 T は2 つ以上の連結成分に分割され、各成分のサイズは最大でn ⁄ 2になります。より正確には、木が中心化されているか双中心化されているかに応じて、常に 1 つまたは 2 つの頂点がこのようなセパレータに相当します。^[2]

これらの例とは対照的に、すべての頂点セパレータがバランスが取れているわけではありませんが、その特性は、平面セパレータ定理などのコンピュータサイエンスのアプリケーションに最も役立ちます。

S を( a , b ) -セパレータ、つまり隣接していない 2 つの頂点aとb を分離する頂点部分集合とします。Sの適切な部分集合がaとb を分離しない場合、 S は最小の ( a , b ) -セパレータです。より一般的には、隣接していない頂点のペア( a , b )に対して S が最小のセパレータである場合、Sは最小のセパレータと呼ばれます。これは、 Sの適切な部分集合が任意の頂点のペア( u , v )に対して最小の( u , v ) -セパレータではないという最小分離集合とは異なることに注意してください。以下は、最小のセパレータを特徴付けるよく知られた結果です: ^[3]

補題. G内の頂点セパレータSが最小となるのは、 GからS を取り除いたグラフG – Sが 2 つの連結成分C ₁とC ₂を持ち、 S内の各頂点がC ₁内のいずれかの頂点とC ₂内のいずれかの頂点に隣接している場合に限ります。

最小の( a , b ) -セパレータも代数構造を形成します。つまり、与えられたグラフGの２つの固定された頂点aとbについて、aからbへのすべてのパスがTに出会う前にSに出会う場合、( a , b ) -セパレータS は別の( a , b ) -セパレータTの先行子と見なすことができます。より厳密には、先行子関係は次のように定義されます。SとT をG内の２つの( a , b ) -セパレータとします。このとき、各x ∈ S \ Tについて、 xとbを結ぶすべてのパスがT に出会う場合、 S はTの先行子です(記号で)。定義から、先行子関係によってすべての( a , b ) -セパレータの集合に事前順序が生じることがわかります。さらに、エスカランテ（1972）は、先行関係がG内の最小の（a、b） -セパレータの集合に制限されると、完全な格子を生成することを証明した。 ${\displaystyle S\sqsubseteq _{a,b}^{G}T}$

• 弦グラフ、すべての最小セパレータがクリークであるグラフ。
• k 頂点連結グラフ

• エスカランテ、F. (1972)。 「グラフェンのシュニットベルバンデ」。ハンブルク大学アブハンドルゲン数学セミナー。38：199-220。土井：10.1007/BF02996932。
• ジョージ、J. アラン(1973)、「正規有限要素メッシュのネストされた解剖」、SIAM Journal on Numerical Analysis、10 (2): 345–363、Bibcode :1973SJNA...10..345G、doi :10.1137/0710032、JSTOR  2156361。
• ゴルビック、マーティン・チャールズ（1980）、アルゴリズムグラフ理論と完全グラフ、アカデミックプレス、ISBN 0-12-289260-7。
• ジョーダン、カミーユ(1869)。 「シュール・レ・アッサンブラージュ・ド・リーニュ」。Journal für die reine und angewandte Mathematik (フランス語)。70 (2): 185-190。
• Rosenberg, Arnold ; Heath, Lenwood (2002)。グラフセパレータとその応用。コンピュータサイエンスの最前線。Springer。doi : 10.1007/b115747。ISBN 0-306-46464-0。