グラフの融合

グラフ理論において、グラフの合併とは、2つのグラフの関係（1つのグラフが別のグラフの合併である）である。同様の関係には、サブグラフやマイナーグラフがある。合併は、特定の構造をそのまま維持しながら、グラフをより単純なグラフに縮小する方法を提供することができる。合併は、元のグラフの特性をより理解しやすいコンテキストで研究するために使用できる。応用分野には、埋め込み、^[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 は の融合を示しています。エッジカラーリングとハミルトン分解の不変性が明確にわかります。関数は一対一であり、図では文字で示されています。関数は以下の表に示されています。 ${\displaystyle K_{5}}$${\displaystyle \phi}$${\displaystyle \psi}$

融合を利用する方法の 1 つは、2 n  + 1 個の頂点を持つ完全グラフのハミルトン分解を見つけることです。^[4]アイデアは、グラフを取り、エッジが色で色付けされ、特定のプロパティを満たす融合 (アウトライン ハミルトン分解と呼ばれる) を生成することです。次に、融合を「逆転」させると、ハミルトン分解で色付け されたものが残ります。${\displaystyle n}$${\displaystyle K_{2n+1}}$

^[3]でヒルトンはこれを行う方法と、繰り返しなしですべてのハミルトン分解を見つける方法を概説しています。この方法は、彼が提供する定理に依存しており、（大まかに言えば）アウトラインハミルトン分解があれば、まず完全グラフのハミルトン分解から始めて、次にそのアマルガムを見つけることで、その分解に到達できると述べています。

• バマニアン、アミン、ロジャー、クリス (2012)、「グラフ融合とは何か?」オーバーン大学
• ヒルトン、AJ W (1984)、「完全グラフのハミルトン分解」、組合せ理論ジャーナル、シリーズ B 36、125–134
• グロス、ジョナサン L.; タッカー、トーマス W. (1987)、トポロジカル グラフ理論、Courier Dover Publications、151
• Gross, Jonathan L. (2011)、「Cubic Outerplanar Graphs の種数分布」、 Journal of Graph Algorithms and Applications、第 15 巻、第 2 号、295 ～ 316 ページ