グラフ理論では、二部ハイパーグラフという用語は、いくつかの関連するハイパーグラフのクラスを表します。これらはすべて、二部グラフの自然な一般化です。
特性Bと2色可能性
二部グラフの最も弱い定義は、2色可能性とも呼ばれます。ハイパーグラフH = ( V , E ) は、頂点集合V を2つの集合XとYに分割でき、各ハイパーエッジがXとYの両方に接する場合、2色可能であると呼ばれます。同様に、 Hの頂点は2色にすることができ、どのハイパーエッジも単色ではありません。すべての二部グラフG = ( X + Y , E ) は2色可能です。つまり、各エッジにはXの頂点とYの頂点が1つずつ含まれているため、たとえばX を青、Y を黄色に着色でき、どのエッジも単色ではありません。
2色可能性の性質は、集合族の文脈でフェリックス・バーンスタインによって初めて導入されたため、 [1] 、性質Bとも呼ばれます。
正確な2色可能性
二部性のより強い定義は、頂点集合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以上のサイズを持つ交差を持つため、二部ではありません。
ホールの結婚定理は、二部グラフから二部ハイパーグラフに一般化されています。ハイパーグラフのホール型定理を参照してください。
n- 分離性と虹色性
より強い定義は、整数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}の分割によって二部集合となります。しかし、3-一様集合ではありません。Vを3つの部分集合に分割する場合、少なくとも1つの部分集合には2つの頂点が含まれます。したがって、少なくとも1つのハイパーエッジには、この部分集合の2つの頂点が含まれます。
3部ハイパーグラフはしばしば「三部ハイパーグラフ」と呼ばれます。しかし、2部ハイパーグラフは二部ハイパーグラフとは異なり、二部グラフと同等です。
他の二分性概念との比較
次のグラフに示すように、初期グラフから任意の数の頂点（ここでは1つの頂点、頂点「v2」）を削除できる。頂点を再着色した後も、グラフは依然として2色彩色可能であることが分かる。頂点が1つしかない辺（シングルトン
）は、明らかに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つ存在する必要があるため、2部頂点ではありません。
参照
参考文献
- ^ バーンスタイン、F. (1908)、「Zur theorie der trigonometrische Reihen」、ライプツ。ベル。、60：325～ 328。
- ^ Aharoni, Ron; Kessler, Ofra (1990-10-15). 「ホール定理の二部ハイパーグラフへの拡張の可能性について」.離散数学. 84 (3): 309– 313. doi : 10.1016/0012-365X(90)90136-6 . ISSN 0012-365X.
- ^ Annamalai, Chidambaram (2015-12-21)、「二部ハイパーグラフにおける完全マッチングの検出」、2016 Annual ACM-SIAM Symposium on Discrete Algorithms の議事録、産業応用数学協会、pp. 1814– 1823、doi : 10.1137/1.9781611974331.ch126、hdl : 20.500.11850/224679、ISBN 978-1-61197-433-1
- ^ Aharoni, Ron (1985-12-01). 「n-partiten-graphsにおけるマッチング」. Graphs and Combinatorics . 1 (1): 303– 304. doi :10.1007/BF02582958. ISSN 1435-5914. S2CID 19258298.
- ^ Guruswami, Venkatesan; Lee, Euiwoong (2018-06-01). 「Balanced Rainbow-Colorable HypergraphsにおけるStrong Inapproximability Results」. Combinatorica . 38 (3): 547– 599. doi :10.1007/s00493-016-3383-0. ISSN 1439-6912. S2CID 53566425.
