極点集合

極点集合 (きょくてんしゅうごう、英: extreme vertex set) は、グラフ理論におけるカット構造の表現のひとつである。辺連結度増大問題を解くために導入された。重み付き無向グラフ G の頂点集合の空でない真部分集合 X のカットの重みより、X のすべての空でない真部分集合 Y のカットの重みが大きいとき、極点集合と呼ばれる。G のすべての極点集合の族はラミナ族である。
アルゴリズム的側面.
G のすべての極点集合の族は最小次数順序と呼ばれるグラフの順序付けを用いて算出される。