バランスのとれたハイパーグラフ

グラフ理論において、バランスのとれたハイパーグラフは、二部グラフと類似したいくつかの特性を持つハイパーグラフです。

バランスハイパーグラフは、二部グラフの自然な一般化として Berge ^[1]によって導入されました。彼は2つの同等の定義を提供しました。

ハイパーグラフH = ( V , E )は、その頂点が 2 色に着色でき、どのハイパーエッジも単色にならない場合、2 色着色可能と呼ばれます。すべての二部グラフG = ( X + Y , E ) は 2 色着色可能です。つまり、各エッジにはXの頂点が 1 つとYの頂点が 1 つずつ含まれ、たとえばX は青に着色でき、Y は黄色に着色でき、どのエッジも単色ではありません。

いくつかのハイパーエッジがシングルトン（頂点が1つだけ）であるハイパーグラフは、明らかに2色化可能ではない。2色化に対するこのような些細な障害を回避するために、本質的に2色化可能であるハイパーグラフ、すなわち、すべてのシングルトンハイパーエッジを削除すると2色化可能になるハイパーグラフを考えるのが一般的である。^{[2] : 468}

ハイパーグラフは本質的に 2 色可能であり、任意の数の頂点を削除しても本質的に 2 色可能である場合、バランスが取れていると呼ばれます。正式には、 Vの各サブセットUに対して、HのUへの制限をハイパーグラフH _U = ( U , E _U )として定義します。ここで、 H は、 VのすべてのサブセットUに対してH _Uが本質的に 2 色可能である場合に限り、バランスが取れていると呼ばれます。単純グラ​​フが 2 部グラフである場合と、それがバランスが取れている場合とで、その場合のどちらも 2 色可能であることに注意してください。 ${\displaystyle E_{U}=\{e\cap U|e\in E\}}$

ハイパーグラフのサイクル（または回路）は、異なる頂点とハイパーエッジが交互に繰り返される周期的なシーケンスです: ( v ₁、e ₁、v ₂、e ₂、...、v _k、e _k、v _{k +1} = v ₁ )。ここで、すべての頂点v _{i は}e _{i −1}とe _iの両方に含まれています。数値kはサイクルの 長さと呼ばれます。

ハイパーグラフがバランス型であるとは、 H内の奇数長サイクルC のそれぞれに、 Cの頂点を少なくとも 3 つ含む辺がある場合に限ります。^[3]

単純なグラフでは、すべての辺に 2 つの頂点しか含まれないことに注意してください。したがって、単純なグラフがバランスの取れたグラフである場合は、奇数長のサイクルがまったく含まれておらず、これは 2 部グラフである場合に限り当てはまります。

ベルゲ^[1]は2つの定義が同等であることを証明した。証明はここでも参照できる。^{[2] ：468–469}

二部グラフに関するいくつかの定理はバランス型ハイパーグラフにも一般化されている。^{[4] [2] : 468–470}

• すべてのバランスのとれたハイパーグラフでは、最小の頂点カバーは、その最大マッチングと同じサイズになります。これは、二部グラフにおけるケーニッヒ-エゲルヴァリの定理を一般化したものです。
• すべてのバランスのとれたハイパーグラフにおいて、次数（=ある頂点を含むハイパーエッジの最大数）は彩度指数（=同じ色を持つ2つのハイパーエッジが共通の頂点を持たないようにハイパーエッジを着色するために必要な最小の色数）に等しい。^[5]これは、二部グラフに関するケーニッヒの定理を一般化したものである。
• すべてのバランスのとれたハイパーグラフは、ホールの結婚定理の一般化を満たします。^[3] E内のすべての辺eに対して| V ₂ | ≥ | V ₁ |が成り立つ場合、 すべての互いに素な頂点集合V ₁、V _{2に対してそのときに限り、完全マッチングが認められます。}ハイパーグラフについてはホール型定理を参照してください。${\displaystyle |e\cap V_{2}|\geq |e\cap V_{1}|}$
• 最大次数Dを持つすべてのバランスのとれたハイパーグラフは、 D個の辺が互いに素なマッチングに分割できる。^{[1] ：第5章 [3] ：系3}

バランスのとれたハイパーグラフのk分割横断線はk個の対素横断線の和集合として表現することができ、そのような分割は多項式時間で得られる。^[6]

バランス以外にも、二部グラフの別の一般化があります。ハイパーグラフは、頂点集合Vが 2 つの集合XとYに分割でき、各ハイパーエッジにXの要素が1 つだけ含まれる場合、二部グラフと呼ばれます(二部ハイパーグラフを参照)。明らかに、すべての二部グラフは 2 色可能です。

二分性とバランスの特性は、互いを意味しません。

バランスは二部性を意味するものではない。Hをハイパーグラフとする: ^[7]

{ {1,2} 、 {3,4} 、 {1,2,3,4} }

これは 2 色可能であり、任意の数の頂点を削除しても 2 色可能です。ただし、最初の 2 つのハイパーエッジのそれぞれに緑の頂点が 1 つだけ存在するためには、最後のハイパーエッジに緑の頂点が 2 つ存在する必要があるため、これは二部グラフではありません。二部グラフで あることはバランスを意味するものではありません。たとえば、H を頂点 {1,2,3,4} と辺を持つハイパーグラフとします。

{ {1,2,3} 、 {1,2,4} 、 {1,3,4} }

これは、 X ={1}、Y ={2,3,4}の分割によって二部グラフになります。ただし、バランスが取れていません。たとえば、頂点 1 を削除すると、Hは{2,3,4} に制限され、次のハイパーエッジを持ちます。

{ {2,3} 、 {2,4} 、 {3,4} }

これは 2 色可能ではありません。任意の 2 色化では、同じ色の頂点が少なくとも 2 つ存在し、したがってハイパーエッジの少なくとも 1 つは単色です。

Hがバランスが取れていないことを確認する別の方法は、奇数長サイクルC = (2 - {1,2,3} - 3 - {1,3,4} - 4 - {1,2,4} - 2) が含まれており、 Cのどの辺にもCの 3 つの頂点 2、3、4 がすべて含まれていないことです。

三部であることはバランスを意味するものではありません。たとえば、H を頂点 {1,2}、{3,4}、{5,6}、辺を持つ三部ハイパーグラフとします。

{ {1,3,5}, {2,4,5}, {1,4,6} }

頂点 2、3、6 を削除すると、残りは次のようになるため、バランスが取れていません。

{ {1,5}, {4,5}, {1,4} }

これは 3 サイクルなので色付けできません。

バランスが取れていないことを確認する別の方法は、奇数長サイクルC = (1 - {1,3,5} - 5 - {2,4,5} - 4 - {1,4,6} - 1) が含まれており、 Cのどの辺にもCの 3 つの頂点 1、4、5 がすべて含まれていないことです。

ハイパーグラフは、長さが3以上（必ずしも奇数長である必要はない）のH内のすべての閉路Cに、 Cの少なくとも3つの頂点を含む辺がある場合、完全にバランスが取れていると呼ばれる。^[8]

ハイパーグラフHが完全にバランスしているためには、Hのすべてのサブハイパーグラフが木ハイパーグラフである必要があります。^[8]

ハイパーグラフ H のケーニッヒ特性は、その最小頂点被覆が最大マッチングと同じサイズであるという特性です。ケーニッヒ-エゲルヴァリ定理によれば、すべての二部グラフはケーニッヒ特性を持ちます。

バランスのとれたハイパーグラフは、 Hのすべての部分サブハイパーグラフがケーニッヒ特性を持つ ハイパーグラフ H です(つまり、H は任意の数のハイパーエッジと頂点を削除してもケーニッヒ特性を持ちます)。

Hのすべての部分ハイパーグラフがケーニッヒ特性を持つ場合（つまり、Hは任意の数のハイパーエッジを削除してもケーニッヒ特性を持つが、頂点は削除しない）、Hは通常のハイパーグラフと呼ばれる。^[9]

したがって、完全にバランスが取れているということはバランスが取れていることを意味し、それは正常であることを意味します。