欠陥（グラフ理論）

不足はグラフ理論の概念であり、ホールの結婚定理など、グラフの完全マッチングに関連するさまざまな定理を洗練するために使用されます。これは、 Øystein Oreによって最初に研究されました。^{[1] [2] ：17}関連するプロパティは余剰です。

G = ( V , E )をグラフとし、Uを独立した頂点の集合、つまり、U は2 つの頂点が辺で接続されていないVのサブセットであるとします。 N _G ( U )は、 Uの 1 つ以上の頂点に辺で接続された 'V' のすべての頂点によって形成されるUの隣接頂点の集合を表します。集合Uの欠陥は次のように定義されます。

${\displaystyle \mathrm {def} _{G}(U):=|U|-|N_{G}(U)|}$

Gが二部グラフであり、二分割V = X ∪ Yであるとします。Gの1 つの部分 (たとえばX )に関する欠損は、 Xのサブセットの最大欠損です。

${\displaystyle \mathrm {def} (G;X):=\max _{U\subseteq X}\mathrm {def} _{G}(U)}$

この量はGの臨界差と呼ばれることもある。^[3]

空集合のdef _{Gは0なので、def(} G; X) ≥ 0となることに注意してください。

def( G; X) = 0 の場合、 Xのすべての部分集合Uに対して、 |N _G ( U )| ≥ | U |が成立することを意味します。したがって、ホールの結婚定理により、G は完全マッチングを許容します。

対照的に、def( G; X) > 0 の場合、Xの一部のサブセットUに対して、|N _G ( U )| < | U | が成立することを意味します。したがって、同じ定理により、G は完全なマッチングを許容しません。さらに、不足の概念を使用して、ホールの定理の定量的なバージョンを述べることができます。

証明。d = def(G;X)とします。これは、 Xのすべての部分集合Uについて、 |N _G ( U )| ≥ | U |- d であることを意味します。d 個のダミー頂点をYに追加し、すべてのダミー頂点をXのすべての頂点に接続します。追加の後、Xのすべての部分集合Uについて、 |N _G ( U )| ≥ | U | です。ホールの結婚定理により、新しいグラフはXのすべての頂点が一致するマッチングを許容します。ここで、 d 個のダミー頂点を削除して元のグラフを復元します。これにより、最大でd個のXの頂点が一致しなくなります。

この定理は次のようにも表現できる: ^{[2] : 17}

${\displaystyle \nu (G)=|X|-\operatorname {def} (G;X),}$

ここでν ( G )はGにおける最大マッチングの大きさ（Gのマッチング数と呼ばれる）である。

二部グラフ G = ( X + Y , E ) において、不足関数はスーパーモジュラー集合関数である。Xの2つの部分集合X ₁、X ₂に対して、次のようになる。^{[2] Lem.1.3.2}

${\displaystyle \operatorname {def} _{G}(X_{1}\cup X_{2})+\operatorname {def} _{G}(X_{1}\cap X_{2})\geq \operatorname {def} _{G}(X_{1})+\operatorname {def} _{G}(X_{2})}$

タイトな部分集合とは、 Xの部分集合で、その欠損がグラフ全体の欠損に等しい（つまり、最大値に等しい）ものである。タイトな集合の交差と和はタイトである。これは、上限付きスーパーモジュラー集合関数の性質から導かれる。^{[2] : Lem.1.3.3}

非二部グラフでは、欠損関数は一般にスーパーモジュラーではありません。

グラフGがホール特性を持つのは、そのグラフにホールの結婚定理が成り立つ場合、つまりG が完全マッチングまたは正の欠損を持つ頂点集合を持つ場合です。グラフが強いホール特性を持つのは、def(G) = |V| - 2 ν(G) の場合です。明らかに、強いホール特性はホール特性を意味します。二部グラフはこれら両方の特性を持ちますが、これらの特性を持つ非二部グラフのクラスもあります。

特に、グラフが強いホール特性を持つのは、安定している場合、つまり最大マッチングサイズが最大分数マッチングサイズに等しい場合に限られます。^[3]

VのサブセットUの 余剰は次のように定義されます。

sur _G ( U ) := |NG ₍ U ) | − |う| = −def _G ( U )

グラフGの部分集合Xに対する余剰は、 Xの空でない部分集合の最小余剰によって定義される: ^{[2] : 19}

sur( G; X) := min [ U はXの空でない部分集合] sur _G ( U )

空でない部分集合への制限に注意してください。これがなければ、すべてのグラフの余剰は常に 0 になります。また、次のことにも注意してください。

def(G;X) = max[0, −sur( G; X)]

二部グラフG = ( X + Y , E ) において、剰余関数はサブモジュラ集合関数である。Xの任意の2つの部分集合X ₁、X ₂に対して、

${\displaystyle \operatorname {sur} _{G}(X_{1}\cup X_{2})+\operatorname {sur} _{G}(X_{1}\cap X_{2})\leq \operatorname {sur} _{G}(X_{1})+\operatorname {sur} _{G}(X_{2})}$

余剰タイトな部分集合とは、 Xの部分集合で、その余剰がグラフ全体の余剰に等しい（つまり、最小値に等しい）ものである。交差が空でないタイトな集合の交差と和はタイトである。これは、下限付きサブモジュラ集合関数の性質から導かれる。^{[2] : Lem.1.3.5}

def( G ; X )=0となる二部グラフGにおいて、sur( G ;X)はX内の各頂点xに対して次の性質を満たす最大の整数sである。すなわち、Xにs個の新しい頂点を追加し、それらをNG ( x )内の頂点に接続すると、結果として得られるグラフに_は非負の余剰が存在する。^{[2] ：Thm.1.3.6}

Gが正の余剰を持つ二部グラフであり、Gから任意の辺を削除するとsur( G; X)が減少する場合、Xのすべての頂点の次数はsur( G ;X) + 1になります。 ^[4]

二部グラフが正の余剰（Xに関して）を持つのは、 Xのすべての頂点がFの次数2であるような森Fを含む場合のみである。^{[2] ：Thm.1.3.8}

正の余剰を持つグラフはグラフ構造の理論において重要な役割を果たします。Gallai -Edmonds 分解を参照してください。

非二部グラフでは、余剰関数は一般にサブモジュラではありません。