グラフの融合

グラフ理論において、グラフの併合とは、 2つのグラフの関係（一方のグラフがもう一方のグラフの併合である関係）のことです。同様の関係には、サブグラフやマイナーグラフなどがあります。併合は、グラフの構造を維持しながら、グラフをより単純なグラフに縮小する方法を提供します。併合は、元のグラフの特性をより理解しやすい文脈で研究するために使用できます。応用分野としては、埋め込み^{[ 1 ]} 、種数分布の計算^{[ 2 ]} 、ハミルトン分解などがあります。

意味

と を、辺の数が同じ2つのグラフとし、 はよりも頂点が多いものとします。このとき、 はの併合であるとは、全単射と全射が存在し、次が成り立つ場合をいいます。 ${\displaystyle G}$ ${\displaystyle H}$ ${\displaystyle G}$ ${\displaystyle H}$ ${\displaystyle H}$ ${\displaystyle G}$ ${\displaystyle \phi :E(G)\to E(H)}$ ${\displaystyle \psi :V(G)\to V(H)}$

• 、が内の 2 つの頂点であり、とが内の辺によって隣接している場合、と は内の辺によって隣接しています。${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle G}$ ${\displaystyle \psi (x)\neq \psi (y)}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle e}$ ${\displaystyle G}$ ${\displaystyle \psi (x)}$ ${\displaystyle \psi (y)}$ ${\displaystyle \phi (e)}$ ${\displaystyle H}$
• が頂点 上のループである場合、は 上のループです。${\displaystyle e}$ ${\displaystyle x\in V(G)}$ ${\displaystyle \phi (e)}$ ${\displaystyle \psi (x)\in H}$
• が に結合し、 が であるが、 の場合は上のループになります。^{[ 3 ]}${\displaystyle e}$ ${\displaystyle x,y\in V(G)}$ ${\displaystyle x\neq y}$ ${\displaystyle \psi (x)=\psi (y)}$ ${\displaystyle \phi (e)}$ ${\displaystyle \psi (x)}$

はグラフまたは擬似グラフになることができますが、通常は が擬似グラフになることに注意してください。 ${\displaystyle G}$ ${\displaystyle H}$

プロパティ

辺の色付けは併合に対して不変です。これは、2つのグラフ間のすべての辺が互いに単射であることから明らかです。しかし、明らかではないかもしれませんが、が の完全グラフである場合、ハミルトン分解（ハミルトンパスへの分解）を指定するために辺を として色付けすると、それらの辺も におけるハミルトン分解を形成します。 ${\displaystyle G}$ ${\displaystyle K_{2n+1}}$ ${\displaystyle H}$

例

図 1: 5 つの頂点を持つ完全グラフの融合。

図1は の併合を示しています。辺の色付けとハミルトン分解の不変性が明確に示されています。関数 は一対一であり、図中の文字で示されています。関数 は下の表に示されています。 ${\displaystyle K_{5}}$ ${\displaystyle \phi }$ ${\displaystyle \psi}$

${\displaystyle v\in V(G)}$	${\displaystyle \psi (v)}$
${\displaystyle v_{1}}$	${\displaystyle u_{2}}$
${\displaystyle v_{2}}$	${\displaystyle u_{2}}$
${\displaystyle v_{3}}$	${\displaystyle u_{1}}$
${\displaystyle v_{4}}$	${\displaystyle u_{3}}$
${\displaystyle v_{5}}$	${\displaystyle u_{2}}$

ハミルトン分解

融合を利用する方法の一つは、2 n  + 1 個の頂点を持つ完全グラフのハミルトン分解を求めることです。^{[ 4 ]}アイデアとしては、グラフを取り、辺を色で塗り分け、特定の性質を満たす融合（アウトライン・ハミルトン分解と呼ばれる）を作成します。そして、この融合を「逆」に行うことで、ハミルトン分解で色付けされたグラフ が得られます。${\displaystyle n}$ ${\displaystyle K_{2n+1}}$

^{[ 3 ]}において、ヒルトンはこれを行う方法と、すべてのハミルトン分解を重複なく見つける方法を概説している。これらの方法は、彼が提示した定理に基づいており、その定理は（大まかに言えば）概略的なハミルトン分解があれば、まず完全グラフのハミルトン分解から始めて、次にそのアマルガムを求めることで、その分解に到達できるというものである。

注記

1. グロス、タッカー 1987
2. グロス 2011
3. ヒルトン 1984
4. バフマニアン、アミン;ロジャー、クリス 2012

参考文献

• バマニアン、アミン、ロジャー、クリス（2012）、「グラフ融合とは何か？」オーバーン大学
• ヒルトン、AJ W (1984)、「完全グラフのハミルトン分解」、組合せ理論ジャーナル、シリーズB 36、125–134
• グロス、ジョナサン L.; タッカー、トーマス W. (1987)、位相グラフ理論、クーリエ・ドーバー出版、151
• Gross, Jonathan L. (2011)、「立方外平面グラフの種数分布」、 Journal of Graph Algorithms and Applications、第15巻、第2号、pp. 295–316