About: 極点集合

極点集合 (きょくてんしゅうごう、英: extreme vertex set) は、グラフ理論におけるカット構造の表現のひとつである。を解くために導入された。重み付き無向グラフ G の頂点集合の空でない真部分集合 X のカットの重みより、X のすべての空でない真部分集合 Y のカットの重みが大きいとき、極点集合と呼ばれる。G のすべての極点集合の族はラミナ族である。