境界（グラフ理論）

グラフ理論では、グラフGの頂点の部分集合Sの外側の境界は、グラフ Sの頂点に隣接しているが、グラフS自体には隣接していないGの頂点の集合です。内側の境界は、グラフS の外側に隣接する頂点を持つグラフSの頂点の集合です。辺の境界は、内側の境界に 1 つの端点があり、外側の境界に 1 つの端点がある辺の集合です。^[1]

これらの境界とそのサイズは、グラフの等周問題、セパレータ定理、最小カット、エキスパンダグラフ、およびパーコレーション理論に特に関連しています。