半グラフは開放辺を持つ無向グラフである。半グラフに対するアンカリングとは:
- Aアンカリング: 各頂点に接続する辺の集合に全順序を入れる。Aは All ports から。
- Bアンカリング: 各頂点に接続する辺の集合を二分割して、2つのパートにそれぞれ全順序を入れる。Bは Bipartite〈二部〉、bipartitioning〈二分割〉 から。
- Cアンカリング: 各頂点に接続する辺の集合に循環順序を入れる。Cは Cyclic から。
それぞれのアンカリングを施された半グラフをxアンカー付き半グラフ〈x-anchored semigraph〉と呼ぶ。
Bアンカー付きグラフの二分割を極性で行った場合、偏極半グラフと呼ぶ。ポート〈半辺〉集合を全順序付けせずに二分割のみしただけの半グラフも偏極半グラフと呼ぶ。偏極半グラフの辺は次のように分類される。
- 有向辺 : 両端がプラスとマイナス
- 不可向辺
- プラス不可向辺: 両端が共にプラス
- マイナス不可向辺: 両端が共にマイナス
不可向辺を排除しない。不可向辺を単位・余単位で消去することもできる。