一致排除

グラフ理論（数学の一分野）において、グラフのマッチング排除数とは、${\displaystyle G}$、と表記される${\displaystyle \mathrm {mp} (G)}$は、削除するとすべての完全一致またはほぼ完全一致（奇数個の頂点を持つグラフで1つの頂点を除くすべての頂点をカバーする一致）がなくなる最小のエッジ数です。 ^{[ 1 ]}マッチング排除は、分散システムの各ノードが隣接するパートナーノードとマッチングされることを必要とする分散アルゴリズムの通信ネットワークトポロジーとしてのグラフの品質を測定します。^{[ 2 ]}

多くのグラフでは、${\displaystyle \mathrm {mp} (G)}$は、グラフ内の任意の頂点の最小次数に等しくなります。なぜなら、単一の頂点に接続するすべてのエッジを削除すると、その頂点がマッチングされなくなるからです。このエッジの集合は、自明なマッチング排除集合と呼ばれます。 ^{[ 2 ]}条件付きマッチング排除数という別の定義では、削除すると完全またはほぼ完全なマッチングも孤立した頂点も持たないグラフになるエッジの最小数を求めます。^{[ 3 ] [ 4 ]}

与えられたグラフのマッチング排除数が与えられた閾値を下回るかどうかをテストすることはNP完全である。 ^{[ 5 ] [ 6 ]}

強力一致排除数（または単にSMP数）は、一致排除数の一般化です。グラフのSMP数は、${\displaystyle G}$、と表記される${\displaystyle \mathrm {smp} (G)}$は、削除すると完全マッチングもほぼ完全マッチングも持たないグラフになるような頂点および/または辺の最小数である。^{[ 7 ]}

グラフ${\displaystyle G}$偶数個の頂点を持つものは、最大一致と呼ばれます。${\displaystyle \mathrm {mp} (G)=\delta (G)}$、 どこ${\displaystyle \delta (G)}$は最小次数を表します。このようなグラフでは、いくつかの自明なマッチング排除セット（最小次数の頂点に接続するエッジ）が最適になります。すべての最適なマッチング排除セットが自明である場合、グラフはスーパーマッチドと呼ばれます。^{[ 8 ]}すべてのスーパーマッチドグラフは最大限にマッチしていますが、その逆は必ずしも真ではありません。

スーパーマッチであることは、相互接続ネットワークにとって望ましい特性と考えられています。これは、ランダムなリンク障害が発生した場合でも、すべての障害リンクが単一の頂点に接続される可能性が低いことを示しているからです。ハイパーキューブグラフとその変種はスーパーマッチであることが知られています。^{[ 8 ]}

さまざまなグラフ積演算を使用して構築されたグラフの場合、マッチング排除数を制限できます。グラフの場合、${\displaystyle G}$そして${\displaystyle H}$偶数個の頂点を持つ: ^{[ 8 ]}

直積${\displaystyle G\square H}$:

${\displaystyle \mathrm {mp} (G)+\mathrm {mp} (H)\leq \mathrm {mp} (G\square H)\leq \delta (G)+\delta (H)}$

両方${\displaystyle G}$そして${\displaystyle H}$非常に相性が良いので、${\displaystyle G\square H}$非常に互角だ。

優れた製品${\displaystyle G\boxtimes H}$:

${\displaystyle \mathrm {mp} (G)\mathrm {mp} (H)+\mathrm {mp} (G)+\mathrm {mp} (H)\leq \mathrm {mp} (G\boxtimes H)\leq \delta (G)\delta (H)+\delta (G)+\delta (H)}$

両方${\displaystyle G}$そして${\displaystyle H}$非常に相性が良い${\displaystyle \delta (G)\geq 2}$そして${\displaystyle \delta (H)\geq 2}$、 それから${\displaystyle G\boxtimes H}$非常に互角だ。

直接製品${\displaystyle G\times H}$:

${\displaystyle \mathrm {mp} (G)\mathrm {mp} (H)\leq \mathrm {mp} (G\times H)\leq \delta (G)\delta (H)}$

両方${\displaystyle G}$そして${\displaystyle H}$非常に相性が良い${\displaystyle \delta (G)\geq 2}$そして${\displaystyle \delta (H)\geq 2}$、 それから${\displaystyle G\times H}$非常に互角だ。

辞書製品${\displaystyle G\circ H}$:

${\displaystyle \mathrm {mp} (H)+\mathrm {mp} (G)|V(H)|\leq \mathrm {mp} (G\circ H)\leq \delta (H)+\delta (G)|V(H)|}$

もし${\displaystyle G}$最大限に一致し、${\displaystyle H}$非常にマッチしています${\displaystyle \delta (H)\geq 2}$、 それから${\displaystyle G\circ H}$非常に互角だ。

結合、コロナ、クラスタ操作などの他のバイナリグラフ操作についても、マッチング除外数の上限が確立されていますが、これらの操作は一般的にスーパーマッチド特性を保持しません。 ^{[ 8 ]}

分数マッチングは関数です${\displaystyle f}$各エッジに番号を割り当てる${\displaystyle [0,1]}$そのため${\displaystyle \sum _{e\sim v}f(e)\leq 1}$各頂点について${\displaystyle v}$ここで、和は、に接続するすべての辺について取られる。${\displaystyle v}$分数完全マッチングは分数マッチングである${\displaystyle f}$満足${\displaystyle \sum _{e\sim v}f(e)=1}$すべての頂点について${\displaystyle v\in V(G)}$明らかに、完全マッチングは部分完全マッチングでもあるが、その逆は必ずしも真ではない。^{[ 9 ]}

グラフの分数一致排除数${\displaystyle G}$、と表記される${\displaystyle \mathrm {fmp} (G)}$は、削除すると部分的な完全マッチングを持たないグラフになるようなエッジの最小数である。^{[ 9 ]}任意のグラフについて${\displaystyle G}$順序${\displaystyle n}$、

${\displaystyle 0\leq \mathrm {fmp} (G)\leq n-1}$

どちらの境界も厳密である。頂点数が偶数のグラフの場合、分数マッチング排除数は通常のマッチング排除数によって制限される。

${\displaystyle \mathrm {mp} (G)\leq \mathrm {fmp} (G)\leq \delta (G)}$

どこ${\displaystyle \delta (G)}$は最小次数を表します。特に、${\displaystyle G}$は偶数個の頂点を持つグラフであり、${\displaystyle \mathrm {mp} (G)=\delta (G)}$、 それから${\displaystyle \mathrm {fmp} (G)=\mathrm {mp} (G)=\delta (G)}$[ ^{9 ]​}

完全なグラフについては${\displaystyle K_{n}}$と${\displaystyle n\geq 7}$、小数一致除外番号は${\displaystyle \mathrm {fmp} (K_{n})=n-1}$より一般的には、偶数次のグラフの場合${\displaystyle n\geq 4k+6}$、${\displaystyle \mathrm {fmp} (G)=n-k}$かつその場合に限り${\displaystyle \delta (G)=n-k}$。

マッチング排除の一般化として、整数の概念${\displaystyle k}$-マッチング除外により、分析は整数に拡張されます${\displaystyle k}$-マッチング。^{[ 10 ]}整数${\displaystyle k}$グラフのマッチング${\displaystyle G}$関数です${\displaystyle h:E(G)\to {0,1,\ldots ,k}}$そのため${\displaystyle \sum _{e\in \Gamma (v)}h(e)\leq k}$任意の頂点${\displaystyle v\in V(G)}$、 どこ${\displaystyle \Gamma (v)}$は、${\displaystyle v}$整数${\displaystyle k}$-マッチングが完璧な場合${\displaystyle \sum _{e\in \Gamma (v)}h(e)=k}$各頂点について${\displaystyle v}$頂点がちょうど１つ存在する場合はほぼ完璧${\displaystyle v'}$そのため${\displaystyle \sum _{e\in \Gamma (v')}h(e)=k-1}$そして、他のすべての頂点は完全条件を満たします。なお、整数1マッチングは、マッチングの標準的な定義と一致します。

整数​${\displaystyle k}$-一致除外番号、表記${\displaystyle \mathrm {mp} _{k}(G)}$は、削除しても完全な整数もほぼ完全な整数も持たないグラフになるような最小のエッジ数です。${\displaystyle k}$-マッチング。強い整数${\displaystyle k}$-一致除外番号、表記${\displaystyle \mathrm {smp} _{k}(G)}$は、削除しても完全な整数もほぼ完全な整数も持たないグラフになるような頂点および/または辺の最小数です。${\displaystyle k}$-マッチング。定義により、${\displaystyle \mathrm {mp} _{1}(G)=\mathrm {mp} (G)}$そして${\displaystyle \mathrm {smp} _{1}(G)=\mathrm {smp} (G)}$[ ^{10 ]​}

偶数値の場合${\displaystyle k}$整数${\displaystyle k}$グラフが完全な整数マッチングを持つ場合に限り、完全な分数マッチングを持つため、-マッチング排除数は分数マッチング排除数に等しい。${\displaystyle k}$-マッチング時${\displaystyle k}$偶数である。さらに、すべてのグラフにはほぼ完全な整数は存在しない。${\displaystyle k}$-偶数に一致する${\displaystyle k}$したがって、分析は通常、奇数値に焦点を当てます。${\displaystyle k\geq 3}$[ ^{10 ]​}

無向グラフにおける辺の削除によって同様の方法で定義される他の数値には、辺連結性（グラフを分断するために削除する必要のある最小辺数）や、循環数（すべてのサイクルを解消するために削除する必要のある最小辺数）などがある。