中間グラフ

数学の分野であるグラフ理論において、平面グラフGのメディアルグラフは、Gの面の辺同士の隣接関係を表す別のグラフM(G)である。メディアルグラフは、凸多面体の組み合わせ特性を研究するために1922 年にエルンスト・シュタイニッツによって導入されたが^[1]、逆の構成はピーター・テイトが 1877 年に結び目とリンクの基礎研究で既に使用していた。^{[2] [3]}

連結平面グラフ Gが与えられたとき、その中間グラフM(G)は

• Gの各辺の頂点と
• Gの各面において、対応する辺が連続して発生する 2 つの頂点間の辺。

切断されたグラフの中間グラフは、各接続コンポーネントの中間グラフの非結合和です。中間グラフの定義は、より高い種数のサーフェス上のグラフ埋め込みにも変更なしで拡張されます。

• 任意の平面グラフの中心グラフは 4 次正則平面グラフです。
• 任意の平面グラフGについて、 Gの中間グラフとGの双対グラフの中間グラフは同型である。逆に、任意の4次元正則平面グラフHについて、中間グラフHを持つ2つの平面グラフだけが互いに双対である。^[4]
• 中間グラフは特定の埋め込みに依存するため、平面グラフの中間グラフは一意ではありません。同じ平面グラフに非同型中間グラフが存在する可能性があります。図では、赤いグラフは同型ではありません。これは、自己ループを持つ 2 つの頂点が 1 つのグラフではエッジを共有しますが、他のグラフでは共有しないためです。
• すべての 4-正則平面グラフは、何らかの平面グラフの中間グラフです。連結された 4-正則平面グラフHについて、 Hを中間グラフとする平面グラフG は、次のように構築できます。 Hの面を 2 色だけで着色します。これは、 Hがオイラーグラフであるため可能です(したがって、Hの双対グラフは二部グラフです)。 Gの頂点は、Hの単一色の面に対応します。これらの頂点は、 Hの対応する面が共有する各頂点の辺によって接続されます。他の色の面を頂点として使用してこの構築を実行すると、 Gの双対グラフが生成されることに注意してください。
• 3 次元正則平面グラフの中心グラフは、その線グラフと一致します。ただし、頂点の次数が 3 より大きい平面グラフの中心グラフの場合は、これは当てはまりません。

平面グラフGの場合、点 (3,3) でのTutte 多項式の評価の 2 倍は、 Gの中間グラフの重み付きオイラー方向の合計に等しくなります。ここで、方向の重みは、方向の鞍点の数 (つまり、接続辺が「イン、アウト、イン、アウト」の順に循環的に順序付けられている頂点の数) の 2 倍です。^[5] Tutte 多項式は埋め込みに対して不変であるため、この結果は、すべての中間グラフがこれらの重み付きオイラー方向の合計が同じであることを示しています。

中間グラフの定義は、方向を含めるように拡張できます。まず、中間グラフの面は、元のグラフの頂点が含まれている場合は黒に、含まれていない場合は白に色付けされます。この色付けにより、中間グラフの各辺は 1 つの黒い面と 1 つの白い面で囲まれることになります。次に、各辺は、黒い面が左側になるように方向付けられます。

平面グラフとその双対は同じ有向中位グラフを持ちません。それらの有向中位グラフは互いの 転置です。

有向中位グラフを使用すると、(3,3) における Tutte 多項式の評価に関する結果を効果的に一般化できます。平面グラフGの場合、点 ( n +1, n +1) におけるTutte 多項式の評価のn倍は、 Gの有向中位グラフでn色を使用したすべての辺彩色の加重和に等しくなり、単色辺の各 (空の場合もある) 集合は有向オイラーグラフを形成します。ここで、有向オイラー方向の重みは単色頂点の数の 2 倍です。^[6]

• 結び目とグラフ
• 平行化（幾何学） -多面体に対する同等の演算

• Brylawski, Thomas ; Oxley, James (1992) 「Tutte 多項式とその応用」(PDF)。White, Neil (編) 『Matriod の応用』 。ケンブリッジ大学出版局。pp.  123– 225。