エッジの収縮

グラフ理論において、辺の縮約とは、グラフから辺を削除すると同時に、その辺が以前結合していた 2 つの頂点を結合する操作です。辺の縮約は、グラフマイナーの理論における基本的な操作です。頂点の識別は、この操作の制限が少ない形式です。

辺の縮約操作は、特定の辺 に対して行われます。辺 は削除され、その 2 つの接続頂点および が新しい頂点 にマージされます。ここで、各接続辺はまたはのいずれかに接続する辺に対応します。より一般的には、操作は各辺を縮約することによって (任意の順序で) 辺のセットに対して実行できます。^[1]${\displaystyle e}$${\displaystyle e}$${\displaystyle u}$${\displaystyle v}$${\displaystyle w}$${\displaystyle w}$${\displaystyle u}$${\displaystyle v}$

結果として得られるグラフは、 と表記されることもあります。( と比較すると、 は接続頂点をマージせずに 単に辺を削除することを意味します。)${\displaystyle G/e}$${\displaystyle G\setminus e}$${\displaystyle e}$

以下に定義されるように、元のグラフが単純なグラフであったとしても、エッジ収縮操作によって複数のエッジを持つグラフが生成される場合がある。^[2]しかし、一部の著者^[3]は複数のエッジの作成を禁止しているため、単純なグラフに対して実行されるエッジ収縮は常に単純なグラフを生成する。

を、 との辺を含むグラフ（または有向グラフ）とします。を、 内のすべての頂点を自身にマッピングし、それ以外の場合は新しい頂点 にマッピングする関数とします。 を縮約すると、新しいグラフ が生成されます。ここで、、、であり、すべての に対して、が辺に付随するのは、対応する辺 がでに付随する場合に限ります。 ${\displaystyle G=(V,E)}$${\displaystyle e=(u,v)}$${\displaystyle u\neq v}$${\displaystyle f}$${\displaystyle V\setminus \{u,v\}}$${\displaystyle w}$${\displaystyle e}$${\displaystyle G'=(V',E')}$${\displaystyle V'=(V\setminus \{u,v\})\cup \{w\}}$${\displaystyle E'=E\setminus \{e\}}$${\displaystyle x\in V}$${\displaystyle x'=f(x)\in V'}$${\displaystyle e'\in E'}$${\displaystyle e\in E}$${\displaystyle x}$${\displaystyle G}$

頂点の識別（頂点の縮約と呼ばれることもある）は、縮約が接続辺を共有する頂点上で行われなければならないという制約を取り除きます。（したがって、辺の縮約は頂点の特定のケースです。）この操作は、グラフ内の任意の頂点のペア（またはサブセット）で行うことができます。2つの縮約頂点間の辺は削除されることがあります。と がの異なる成分の頂点である場合、 の とをの新しい頂点として識別することにより、新しいグラフを作成できます。^[4]より一般的には、頂点セットの分割が与えられた場合、分割内の頂点を識別できます。結果として得られるグラフは商グラフと呼ばれます。 ${\displaystyle v}$${\displaystyle v'}$${\displaystyle G}$${\displaystyle G'}$${\displaystyle v}$${\displaystyle v'}$${\displaystyle G}$${\displaystyle {\textbf {v}}}$${\displaystyle G'}$

頂点分割は頂点分割と同じで、1 つの頂点が 2 つに分割され、これらの 2 つの新しい頂点が元の頂点が隣接していた頂点に隣接することを意味します。これは頂点識別の逆操作ですが、一般に頂点識別では、識別された 2 つの頂点の隣接頂点は同じセットではありません。

パスの縮小は、パス内のエッジのセットが縮小して、パスのエンドポイント間に 1 つのエッジを形成する場合に発生します。パスに沿った頂点に接続するエッジは削除されるか、エンドポイントの 1 つに任意に (または体系的に) 接続されます。

2つの互いに素なグラフと を考えます。ここで は頂点とを含み、 は頂点と を含みます。 の頂点との頂点をの頂点として、 の頂点と の頂点を の頂点として識別することで、グラフを取得できるとします。を頂点集合 に関してねじることで、代わりに を 、をと同一視します。^[5]${\displaystyle G_{1}}$${\displaystyle G_{2}}$${\displaystyle G_{1}}$${\displaystyle u_{1}}$${\displaystyle v_{1}}$${\displaystyle G_{2}}$${\displaystyle u_{2}}$${\displaystyle v_{2}}$${\displaystyle G}$${\displaystyle u_{1}}$${\displaystyle G_{1}}$${\displaystyle u_{2}}$${\displaystyle G_{2}}$${\displaystyle u}$${\displaystyle G}$${\displaystyle v_{1}}$${\displaystyle G_{1}}$${\displaystyle v_{2}}$${\displaystyle G_{2}}$${\displaystyle v}$${\displaystyle G}$ ${\displaystyle G'}$${\displaystyle G}$${\displaystyle \{u,v\}}$${\displaystyle u_{1}}$${\displaystyle v_{2}}$${\displaystyle v_{1}}$${\displaystyle u_{2}}$

辺と頂点の縮小手法はどちらも、グラフ内の頂点または辺の数を帰納的に証明する際に役立ちます。帰納法では、ある特性がすべての小さいグラフに当てはまると仮定でき、これを使用して大きいグラフの特性を証明できます。

辺の縮約は、任意の連結グラフの木の数を求める再帰式^[6]や、単純グラフの彩色多項式を求める再帰式^{[7]で用いられる。}

縮約は、本質的に同等のエンティティを表す頂点を識別することによってグラフを単純化したい構造でも役立ちます。最も一般的な例の 1 つは、各強く連結されたコンポーネント内のすべての頂点を縮約することによって、一般的な有向グラフを非循環有向グラフに縮小することです。グラフによって記述される関係が推移的である場合、各頂点に、グラフを形成するために縮約された頂点のラベルのセットでラベルを付ける限り、情報は失われません。

もう 1 つの例は、グローバル グラフ カラーリング レジスタ割り当てで実行される合体です。ここでは、異なる変数間の移動操作を排除するために、頂点が縮小されます (安全な場合)。

エッジの縮小は、3D モデリング パッケージで (手動またはモデリング ソフトウェアの機能を通じて) 使用され、一貫して頂点数を削減して、低ポリゴン モデルの作成に役立ちます。

• 細分化（グラフ理論）

• グロス、ジョナサン、イエレン、ジェイ（1998）、グラフ理論とその応用、CRC Press、ISBN 0-8493-3982-0
• オクスリー、ジェームズ（2006）[1992]、マトロイド理論、オックスフォード大学出版局、ISBN 978-0-19-920250-8
• ローゼン、ケネス（2011）、離散数学とその応用（第7版）、マグロウヒル、ISBN 978-0-07-338309-5
• ウェスト、ダグラス B. (2001)、グラフ理論入門(第 2 版)、Prentice-Hall、ISBN 0-13-014400-2

• Weisstein、Eric W.「エッジ収縮」。MathWorld。