縁の収縮

させて${\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つの頂点間のエッジが削除される場合もあります。${\displaystyle v}$そして${\displaystyle v'}$は、異なるコンポーネントの頂点です。${\displaystyle G}$そうすれば新しいグラフを作成できます${\displaystyle G'}$特定することによって${\displaystyle v}$そして${\displaystyle v'}$で${\displaystyle G}$新しい頂点として${\displaystyle {\textbf {v}}}$で${\displaystyle G'}$^{[ 4 ]}より一般的には、頂点集合の分割が与えられた場合、分割内の頂点を識別することができます。結果として得られるグラフは商グラフとして知られています。

頂点分割（頂点スプリッティングとも呼ばれる）とは、1つの頂点を2つに分割し、分割後の2つの頂点が元の頂点に隣接していた頂点と隣接させる操作のことです。これは頂点識別の逆操作ですが、一般的に頂点識別の場合、識別された2つの頂点の隣接頂点は同じ集合ではありません。

パスの収縮とは、パス上のエッジの集合が収縮して、パスの両端点間に単一のエッジを形成する処理のことです。パス上の頂点に接続するエッジは、削除されるか、または任意（あるいは体系的に）にいずれかの端点に接続されます。

互いに素な2つのグラフを考える${\displaystyle G_{1}}$そして${\displaystyle G_{2}}$、 どこ${\displaystyle G_{1}}$頂点を含む$u_1$そして${\displaystyle v_{1}}$そして${\displaystyle G_{2}}$頂点を含む$u2$そして${\displaystyle v_{2}}$グラフを取得できると仮定します${\displaystyle G}$頂点を特定することによって$u_1$の${\displaystyle G_{1}}$そして$u2$の${\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\}}$代わりに、$u_1$と${\displaystyle v_{2}}$そして${\displaystyle v_{1}}$と$u2$[ ^{5 ]​}

有限個のエッジが与えられた場合、グラフ上で縮約を行う順序は（同型を除いて）結果を変えない。結果は、次のことを示すことに帰着する。${\displaystyle G/e/(f/e)}$は同型である${\displaystyle G/f/(e/f)}$2つの辺について${\displaystyle e,f}$の${\displaystyle G}$[ ^{6 ]​}