2021-04-17から1日間の記事一覧

平面グラフを全域木と完全マッチングに対応させる

平面グラフではが成り立つ この式を変形してが得られる 頂点を1つ取り除き、面も1つ取り除くと、辺の数は、残った頂点の数と残った面の数の和に等しい、と読める 「等しい」ということを、「辺に対して、頂点もしくは面を一つ対応させると、完全マッチング…