ホール違反者

グラフ理論において、ホール違反とは、グラフ内の頂点の集合のうち、ホールの結婚定理の条件に違反するものを指す。^[1]

正式には、二部グラフ G = ( X  +  Y ,  E )が与えられたとき、 X内のホール違反はXのサブセットWであり、| N _G ( W )| < | W |となります。ここで、N _G ( W ) はG内の Wの隣接点の集合です。

Wがホール違反である場合、 Wのすべての頂点を飽和させるマッチングは存在しません。したがって、 X を飽和させるマッチングも存在しません。ホールの結婚定理によれば、逆も真です。つまり、ホール違反がない場合は、  X を飽和させるマッチングが存在します。

ホール違反は効率的なアルゴリズムによって検出できます。以下のアルゴリズムでは、次の用語を使用します。

• M交代パスは、何らかのマッチングMに対して、最初のエッジがMのエッジではなく、2 番目のエッジがMのエッジであり、3 番目のエッジがMのエッジではない、などのパスです。
• 頂点z は、頂点xからM到達可能であり、 xからzへのM交互パスが存在する場合に限られます。

例として、右の図を考えてみましょう。垂直 (青) のエッジは対応するM を示しています。頂点セットY ₁、X ₁、Y ₂、X _2はx _{0 (または}X ₀の他の任意の頂点)からM到達可能ですが、Y ₃とX _3はx ₀からM到達可能ではありません。

ホール違反者を見つけるアルゴリズムは次のように進行します。

1. 最大マッチングMを見つけます（ホップクロフト-カープアルゴリズムで見つけることができます）。
2. Xのすべての頂点が一致する場合は、「ホール違反者は存在しません」を返します。
3. それ以外の場合、x _{0 は}一致しない頂点になります。
4. W をx ₀からM到達可能なXのすべての頂点の集合とします（これは幅優先探索を使用して見つけることができます。図では、Wにはx ₀とX ₁とX _{2 が}含まれています）。
5. Wを返します。

このW は、次の事実により、確かにホール違反です。

• N _G ( W )のすべての頂点はMと一致します。矛盾により、N _G ( W )のいくつかの頂点y はMと一致しないとします。x をW内のその隣接頂点とします。 x _0からxを経てyに至るパスはM増加パスです。つまり、 M交代パスであり、一致しない頂点で始まり、一致しない頂点で終わるため、これを「反転」することでM を増やすことができますが、これはその最大性と矛盾します。
• W には、MによるN _G ( W )のすべての一致が含まれます。これは、これらすべての一致がx ₀からM到達可能だからです。
• W には、定義によりMと一致しない別の頂点 ( x ₀ ) が含まれます。
• したがって、| W | = | N _G ( W )| + 1 > | N _G ( W )|となり、W は確かにホール非対称性の定義を満たします。

包含最小ホール違反とは、そのサブセットのそれぞれがホール違反ではないホール違反のことです。

実際、上記のアルゴリズムは包含最小ホール違反を見つけます。これは、Wから任意の頂点が削除された場合、残りの頂点はN _G ( W )の頂点と完全に一致できるためです（ Mの辺、またはx ₀からの M 交互パスの辺によって）。^[2]

上記のアルゴリズムは、必ずしも最小基数のホール違反者を見つけるわけではありません。たとえば、上の図では、サイズ 5 のホール違反者を返しますが、X ₀はサイズ 3 のホール違反者です。

実際、最小濃度ホール違反を見つけることはNP困難である。これはクリーク問題からの還元によって証明できる。^[3]

以下のアルゴリズム^{[4] [5]}は、グラフ内の任意のマッチングMと、 Mによって飽和していないX内の頂点x ₀を入力として取ります。

出力として、 x _{0 を}含むホール違反者、またはM を拡張するために使用できるパスのいずれかを返します。

1. k = 0、W _k  := { x ₀ }、Z _k  := {}と設定します。
2. アサート：
   • W _k = { x ₀ ,..., x _k }ここで、 x _iはXの異なる頂点です。
   • Z _k = { y ₁ ,..., y _k } ここで、 y _{i は}Yの異なる頂点です。
   • すべてのi ≥ 1について、y _{i は}Mによってx _iと一致します。
   • すべてのi ≥ 1について、y _{i は}Mにない辺によって何らかのx _{j < i}に接続されます。
3. N _G ( W _k ) ⊆ Z _kの場合、| W _k | = k +1 > k = | Z _k | ≥ | N _G ( W _k )|であるため、W _{k は}ホール違反になります。ホール違反W _kを返します。
4. それ以外の場合、y _{k +1を}N _G ( W _k ) \ Z _kの頂点とします。次の2つのケースを考えます。
5. ケース1: y _{k +1は}Mと一致します。
   • x _{0 は}一致せず、W _k内のすべてのx _{i は}Z _k内のy _iと一致するため、このy _{k +1}のパートナーはW _kにないXの頂点である必要があります。これをx _{k +1}と表記します。
   • W _{k +1}  := W _k U { x _{k +1} }かつZ _{k +1}  := Z _k U { y _{k +1} }かつk  := k  + 1とします。
   • 手順 2 に戻ります。
6. ケース2: y _{k +1は}Mと一致しません。
   • y _{k +1}はN _G ( W _k )にあるため、 Mにないエッジによってx _i ( i  <  k  + 1 )に接続されます。x _{i は}Mにあるエッジによってy _iに接続されます。y _{i は}Mにないエッジによってx _j ( j  <  i )に接続されます。以下同様に続きます。これらの接続をたどると、最終的には一致しないx ₀にたどり着くはずです。したがって、 M 増加パスが得られます。 M増加パスを返します。

各反復で、W _kとZ _{k は} 1 つの頂点ずつ増加します。したがって、アルゴリズムは最大| X |回の反復後に終了する必要があります。

この手順は反復的に使用できます。まずM を空のマッチングとして開始し、ホール違反が見つかるか、マッチングM がXのすべての頂点を飽和するまで、この手順を何度も呼び出します。これにより、ホールの定理の構成的証明が得られます。

• 制約プログラミングにおけるホール違反の応用。^[6]
• 「ホール条件に違反する二部グラフのサブセットを見つける」。コンピュータサイエンススタックエクスチェンジ。2014-09-15。2019-09-08に取得。