組合せ最適化 輪講
第10回 2.6 平面的双対性
ERATO研究員 川原 純
平面的双対性
G
b*
a
g
e
b
a*
e*
g*
d
f
h
c
定理 2.42
G が連結なら
(G*)* = G
f*
d*
h*
c*
G* : G の
平面的双対グラフ
自己ループ
（本節のみ認める）
平面的双対性
G
b*
a
g
e
b
a*
e*
g*
d
f
h
c
f*
d*
h*
c*
閉路と極小カットは双対の関係
（定理2.43）
G* : G の
平面的双対グラフ
平面的双対性
2部グラフとオイラーグラフは双対の関係
（系2.35）

スライド 1

情報数理

ノート用PDF