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

  • 平面グラフでは|V| - |E| + |F| =2が成り立つ
  • この式を変形して(|V|-1) + |F|-1) = |E|が得られる
  • 頂点を1つ取り除き、面も1つ取り除くと、辺の数は、残った頂点の数と残った面の数の和に等しい、と読める
  • 「等しい」ということを、「辺に対して、頂点もしくは面を一つ対応させると、完全マッチングさせることができる」と読み替える
  • この読み替えが、具体的には、平面グラフから、その頂点・辺・面のすべてを頂点とした平面グラフを構成し、そこから元の頂点と元の面とに対応する頂点を取り除いた後の平面グラフでは、完全マッチングが取れる、ということに対応付けられる
  • ただし、取り除く元の頂点は、取り除く元の面を構成する頂点であることが必要
  • この構成法において、「取り除く予定の頂点」を根とした有向全域木と、元の平面グラフの双対グラフにおいて「取り除く予定の面」に対応する頂点を根とする有向全域木とが、フォークの相互かみ合わせのようになっていると見立てられることから、全域木とも関係する
  • それについて記した文書がこちら:"Trees and matchings"

http://emis.impa.br/EMIS/journals/EJC/Volume_7/PDF/v7i1r25.pdf

www.math.lsa.umich.edu