バランスのとれたハイパーグラフ
初期グラフは2色彩色可能であり、頂点を各辺に1色ずつ割り当てることができる。

次のグラフに示すように、初期グラフから任意の数の頂点（ここでは1つの頂点、頂点「v2」）を削除できる。頂点を再着色した後も、グラフは依然として2色彩色可能であることが分かる。頂点が1つしかない辺（シングルトン

）は、明らかに2色彩色できないため、無視される。

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

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

2色可能性による定義

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

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

ハイパーグラフが本質的に2色可能であり、かつ任意の数の頂点を削除しても本質的に2色可能である場合、そのハイパーグラフは平衡型と呼ばれます。正式には、 V の各部分集合 U に対して、HのUへの制約をハイパーグラフ H U = ( U , E U ) （ただし ）として定義します。この場合、Hが平衡型と呼ばれるのは、H UがVの任意の部分集合Uに対して本質的に2色可能である場合のみです。単純グラ​​フが2部グラフである場合と2色可能である場合とで、かつ平衡型である必要があることに注意してください。 E あなた ＝ { e ∩ あなた | e ∈ E } {\displaystyle E_{U}=\{e\cap U|e\in E\}}

奇数サイクルによる定義

ハイパーグラフにおけるサイクル（または回路）とは、異なる頂点とハイパーエッジが交互に現れる周期的な列である：( v 1 , e 1 , v 2 , e 2 , ..., v k , e k , v k +1 = v 1 )。ここで、すべての頂点v iはe i −1とe iの両方に含まれる。数値kはサイクルの 長さと呼ばれる。

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

単純グラフでは、すべての辺は2つの頂点のみを含むことに注意してください。したがって、単純グラフがバランス型であるためには、奇数長閉路が全く含まれず、かつ二部グラフであるためには、そのグラフがバランス型である必要があります。

ベルゲ[1]は2つの定義が同等であることを証明した。証明はここにもある。[2] :468–469 

プロパティ

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

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

他の二分性概念との比較

二部グラフには、バランス以外にも様々な一般化があります。ハイパーグラフは、その頂点集合Vが二つの集合XとYに分割可能であり、各ハイパーエッジがXの要素を一つだけ含む場合、二部グラフと呼ばれます（二部ハイパーグラフを参照）。明らかに、すべての二部グラフは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のすべての部分サブハイパーグラフが Konig プロパティを持つハイパーグラフ H です(つまり、任意の数のハイパーエッジと頂点を削除しても、H は Konig プロパティを持ちます)。

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

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

参考文献

  1. ^ abc ベルジュ、クロード (1970)。 「確実なハイパーグラフ一般、グラフ二部構成」。組み合わせ理論とその応用。1：119～ 133。
  2. ^ abc ロヴァース、ラスロー;プラマー医学博士(1986 年)、『マッチング理論』、『離散数学年報』、第 1 巻。 29、北オランダ、ISBN 0-444-87916-1、MR  0859549
  3. ^ abc Conforti, Michele; Cornuéjols, Gérard; Kapoor, Ajai; Vušković, Kristina (1996-09-01). 「バランス型ハイパーグラフにおける完全マッチング」. Combinatorica . 16 (3): 325– 329. doi :10.1007/BF01261318. ISSN  1439-6912. S2CID  206792822.
  4. ^ ベルジュ, クロード; ヴェルグナス, ミシェル LAS (1970). 「Sur Un Theorems Du Type König Pour Hypergraphes」. Annals of the New York Academy of Sciences . 175 (1): 32– 40. doi :10.1111/j.1749-6632.1970.tb56451.x. ISSN  1749-6632. S2CID  84670737.
  5. ^ Lovász, L. (1972-06-01). 「正規ハイパーグラフとパーフェクトグラフ予想」.離散数学. 2 (3): 253– 267. doi :10.1016/0012-365X(72)90006-4. ISSN  0012-365X.
  6. ^ Dahlhaus, Elias; Kratochvíl, Jan; Manuel, Paul D.; Miller, Mirka (1997-11-27). 「バランスのとれたハイパーグラフにおける横断分割」.離散応用数学. 79 (1): 75– 89. doi :10.1016/S0166-218X(97)00034-6. ISSN  0166-218X.
  7. ^ 「彩色 - 二部グラフのどの一般化がより強いか？」Mathematics Stack Exchange . 2020年6月27日閲覧。
  8. ^ ab Lehel, Jenö (1985-11-01). 「完全にバランスのとれたハイパーグラフの特徴付け」.離散数学. 57 (1): 59– 65. doi : 10.1016/0012-365X(85)90156-6 . ISSN  0012-365X.
  9. ^ Beckenbach, Isabel; Borndörfer, Ralf (2018-10-01). 「グラフとハイパーグラフにおけるホール定理とケーニッヒ定理」.離散数学. 341 (10): 2753– 2761. doi :10.1016/j.disc.2018.06.013. ISSN  0012-365X. S2CID  52067804.
「https://en.wikipedia.org/w/index.php?title=Balanced_hypergraph&oldid=1276470915」より取得