マトロイドと代数双対
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/04/11 14:38 UTC 版)
連結グラフGの代数的双対G★は、GおよびG★が同じ辺の組を持っていて、Gの全てのサイクル Gは、G★のカットであり、Gの全てのカットはG★のサイクルであるようなグラフである。すべての平面グラフは代数双対を持ち、これは一般的に一意ではない（平面埋め込みによって定義される双対は一意となる）。Hassler Whitneyによる Whitneyの平面性の基準で解決されたように、この逆もまた真である。 連結グラフGは代数双対をもつ場合に限り、平面グラフである。 同じ事実はマトロイドの理論でも表現できる。MがグラフGのグラフィックマトロイドである場合、グラフG★もしGの代数デュアルでありG★のグラフィックマトロイドがある場合にのみ、デュアルマトロイド Mの。その場合、Whitneyの平面性基準は、グラフィックマトロイドM 双対マトロイドは、それ自体がM基礎となるグラフGが平面である場合に限り、それ自体がグラフィックマトロイドであると述べると言い換えることができる。Gが平面ならば、双対マトロイドはG双対グラフのグラフィックマトロイドである。特に、Gすべての異なる平面埋め込みに対して、すべての双対グラフは同型グラフィックマトロイドを持つ。 非平面曲面埋め込みの場合、平面双対とは異なり、双対グラフは一般に主グラフの代数双対ではない。そして、非平面グラフGについて、Gのグラフィックマトロイドの双対マトロイドは、グラフィックマトロイドそのものではない。しかし、それは依然として、サイクルがGのカットに対応するマトロイドであり、この意味では代数双対の一般化として考えることができる。 オイラー平面グラフと2部平面グラフの双対性は、二項マトロイド（平面グラフから派生したグラフィックマトロイドを含む）に拡張できる。二項マトロイドが2部である場合に限り、二項マトロイドはオイラー的である。ガースとエッジ接続性という2つの双対概念は、マトロイドガースによってマトロイド理論に統一される。平面グラフのグラフィックマトロイドのガースは、グラフのガースと同じである。また、双対マトロイドガース（双対のグラフィックマトロイド）はグラフのエッジ連結性である。
※この「マトロイドと代数双対」の解説は、「双対グラフ」の解説の一部です。
「マトロイドと代数双対」を含む「双対グラフ」の記事については、「双対グラフ」の概要を参照ください。
- マトロイドと代数双対のページへのリンク
