二部ハイパーグラフ

グラフ理論では、二部ハイパーグラフという用語は、いくつかの関連するハイパーグラフのクラスを表します。これらはすべて、二部グラフの自然な一般化です。

二部性の最も弱い定義は、2-彩色可能 とも呼ばれます。ハイパーグラフH = ( V , E ) は、頂点集合V を2 つの集合XとYに分割でき、各ハイパーエッジがXとY の両方に一致する場合、 2-彩色可能 と呼ばれます。同様に、 Hの頂点は2 色にすることができ、ハイパーエッジは単色ではありません。すべての二部グラフG = ( X + Y , E ) は 2-彩色可能です。つまり、各エッジにはXの頂点が 1 つとYの頂点が 1 つだけ含まれ、たとえばX は青に、Y は黄色に彩色でき、どのエッジも単色ではありません。

2色可能性の性質は、集合族の文脈でフェリックス・バーンスタインによって初めて導入されました。 ^{[1]そのため、}性質Bとも呼ばれます。

二部性のより強い定義は、頂点集合Vが2つの集合XとYに分割でき、各ハイパーエッジにXの要素が1つだけ含まれる場合、そのハイパーグラフは二部グラフと呼ばれるというものです。^{[2] [3]}すべての二部グラフは二部ハイパーグラフでもあります。

すべての二部ハイパーグラフは 2 色可能ですが、二部であることは 2 色可能であることよりも強いです。Hを頂点 {1, 2, 3, 4} 上のハイパーグラフとし、次のハイパーエッジを持ちます。

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

このH は、たとえば分割X = {1,2} およびY = {3,4} によって 2 色可能です。ただし、1 つの要素を持つすべての集合Xには 1 つのハイパーエッジとの空の交差があり、2 つ以上の要素を持つすべての集合Xには少なくとも 2 つのハイパーエッジとサイズ 2 以上の交差があるため、2 部ではありません。

ホールの結婚定理は、二部グラフから二部ハイパーグラフに一般化されています。ハイパーグラフのホール型定理を参照してください。

より強い定義は次のようになる。整数nが与えられたとき、ハイパーグラフのすべてのハイパーエッジがちょうどn個の頂点を含む場合、そのハイパーグラフはn一様であると呼ばれる。n一様ハイパーグラフは、その頂点集合V がn 個の部分集合に分割可能で、各ハイパーエッジが各部分集合からちょうど 1 つの要素を含む場合、n 部集合であると呼ばれる。 ^[4]別の用語はrainbow-colorableである。^[5]

すべてのn部ハイパーグラフは二部グラフですが、n 部は二部グラフよりも強いです。Hを頂点 {1, 2, 3, 4} 上のハイパーグラフとし、次のハイパーエッジを持ちます。

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

このHは 3 均一です。分割X = {1} およびY = {2,3,4}によって 2 部になります。ただし、3 部ではありません。Vを3 つのサブセットに分割するたびに、少なくとも 1 つのサブセットに 2 つの頂点が含まれるため、少なくとも 1 つのハイパーエッジにこのサブセットの 2 つの頂点が含まれます。

3 部ハイパーグラフは、しばしば「3 部ハイパーグラフ」と呼ばれます。ただし、2 部ハイパーグラフは2 部ハイパーグラフと同じではなく、2 部グラフと同等です。

二部グラフには、他にも自然な一般化があります。ハイパーグラフが本質的に 2 色可能であり、任意の数の頂点を削除しても本質的に 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} 、 {1,2,3,4} }

これは 2 色可能であり、任意の数の頂点を削除しても 2 色可能のままです。ただし、最初の 2 つのハイパーエッジのそれぞれに正確に 1 つの緑の頂点が存在するためには、最後のハイパーエッジに 2 つの緑の頂点が存在する必要があるため、これは二部ではありません。

• ハイパーグラフでのマッチング
• ハイパーグラフの頂点被覆