Balanced_hypergraph
グラフ理論、バランスハイパーグラフであるハイパーグラフのものと類似のいくつかの性質を有する二部グラフ。
バランスの取れたハイパーグラフは、2部グラフの自然な一般化としてBerge によって導入されました。彼は2つの同等の定義を提供しました。
コンテンツ
1 2色で定義
2 奇数サイクルによる定義
3 プロパティ
4 二者性の他の概念との比較
5 関連するプロパティ
5.1 完全にバランスの取れたハイパーグラフ 5.2 通常のハイパーグラフ
6 参考文献
2色で定義
ハイパーグラフH =（V、Eは）と呼ばれる2着色その頂点が全くhyperedgeが単色ではないように2は、着色することができる場合。すべての2部グラフG =（X + Y、E）は2色です。各エッジにはXの頂点が1つとYの頂点が1つだけ含まれているため、たとえばXを青に、Yを黄色に着色でき、単色のエッジはありません。
一部のハイパーエッジがシングルトン（1つの頂点のみを含む）であるハイパーグラフは、明らかに2色ではありません。2色化に対するこのような些細な障害を回避するために、本質的に2色化可能なハイパーグラフを検討するのが一般的です。つまり、すべてのシングルトンハイパーエッジを削除すると2色化可能になります。 ：468
ハイパーグラフは、本質的に2色である場合はバランスが取れていると呼ばれ、任意の数の頂点を削除しても本質的に2色のままです。正式には、VのサブセットUごとに、HからUへの制限をハイパーグラフH U =（U、E U）として定義します。ここでE U = {{ e ∩ U | e ∈ E } {E_ {U} = {e cap U | e in E }}
。次いで、Hは、ときに限りバランスと呼ばれるH Uは、すべての部分集合のための本質的に2着色であるUのV。単純なグラフは、バランスが取れていれば2色である場合は2部グラフであることに注意して
奇数サイクルによる定義
ハイパーグラフのサイクル（または回路）は、異なる頂点とハイパーエッジの周期的な交互シーケンスです：（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つの頂点を含むエッジがある場合にバランスが取られます。
単純なグラフでは、すべてのエッジに2つの頂点しか含まれていないことに注意してしたがって、単純なグラフは、奇数の長さのサイクルがまったく含まれていない場合はバランスが取れており、2部グラフの場合は保持されます。
Berge は、2つの定義が同等であることを証明しました。証明もここに ：468–469
プロパティ
2部グラフのいくつかの定理は、バランスの取れたハイパーグラフに一般化されています。 ：468–470
すべてのバランスの取れたハイパーグラフで、最小頂点被覆は最大マッチングと同じサイズになります。これは、2部グラフ上のKőnig-Egervaryの定理を一般化します。
すべてのバランスの取れたハイパーグラフで、次数（= 1つの頂点を含むハイパーエッジの最大数）は色指数（=同じ色の2つのハイパーエッジに共通の頂点がないようにハイパーエッジを色付けするために必要な最小の色数）に等しくなります。。これは、2部グラフ上のケーニヒの定理を一般化します。
すべてのバランスの取れたハイパーグラフを満たすの一般ホールの定理：は、それがすべて互いに素の頂点集合のための完全な一致IFF認めているV 1、V 2を場合は、 ∩ V 2 |
≥ | e∩ V 1 |
{| e cap V_ {2} | geq | e cap V_ {1} |}
すべてのエッジのためのEでE、その後| V 2 | ≥| V 1 |。ハイパーグラフについては、ホールタイプの定理を参照して
最大次数Dのすべてのバランスの取れたハイパーグラフは、Dエッジの互いに素なマッチングに分割できます。 ：第5章 ：結果3
Kバランスハイパーグラフの横倍は、組合のように表すことができるk個のペアワイズ・ディスジョイント同位角、及びそのようなパーティションが多項式時間で得ることができます。
二者性の他の概念との比較
バランスに加えて、2部グラフの代替の一般化がハイパーグラフは、頂点セットVをXとYの2つのセットに分割して、各ハイパーエッジにXの要素が1つだけ含まれる場合に2部グラフと呼ばれます（2部グラフを参照）。明らかに、すべての2部グラフは2色です。
二者性とバランスの特性は、お互いを意味するものではありません。
バランスは二者間を意味するものではありません。してみましょうHは：ハイパーグラフも
{{1，2}、{3，4}、{1，2，3，4}}
これは2色であり、頂点をいくつでも削除しても2色のままです。ただし、最初の2つのハイパーエッジのそれぞれに正確に1つの緑色の頂点があるため、最後のハイパーエッジに2つの緑色の頂点が必要であるため、2部グラフではありません。二者間性はバランスを意味するものではありません。たとえば、Hを頂点{1，2，3，4}とエッジを持つハイパーグラフとします。
{{1，2，3}、{1，2，4}、{1，3，4}}
これは、パーティションX = {1}、Y = {2，3，4}によって2部になります。しかし、バランスが取れたとえば、頂点1が削除されると、Hが{2，3，4}に制限されます。これには、次のハイパーエッジが
{{2，3}、{2，4}、{3，4}}
どの2色でも、同じ色の頂点が少なくとも2つあり、ハイパーエッジの少なくとも1つが単色であるため、2色ではありません。
Hのバランスが取れていないことを確認する別の方法は、奇数の長さのサイクルC =（2- {1，2，3} -3-{1，3，4} -4- {1，2，4}が含まれていることです。 – 2）、及び無端Cのすべての3つの頂点の2，3，4含まCを。
三者性はバランスを意味するものではありません。たとえば、Hを頂点{1，2}、{3，4}、{5，6}とエッジを持つ3部構成のハイパーグラフとします。
{{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のすべての3つの頂点の1，4，5-含まCを。
関連するプロパティ
完全にバランスの取れたハイパーグラフ
ハイパーグラフは、長さが3以上（必ずしも奇数の長さである必要はない）のHのすべてのサイクルCに、Cの頂点が少なくとも3つ含まれるエッジがある場合に完全平衡と呼ばれます。
ハイパーグラフHは、Hのすべてのサブハイパーグラフがツリーハイパーグラフである場合、完全にバランスが取れています。
通常のハイパーグラフ
ハイパーグラフHのKonigプロパティは、その最小頂点被覆が最大マッチングと同じサイズであるというプロパティです。ケーニッヒ-Egervary定理は、すべての二部グラフは、ケーニッヒプロパティを持っていることを言います。
バランスの取れたハイパーグラフは正確にハイパーグラフHであり、Hのすべての部分的なサブハイパーグラフはKonigプロパティを持ちます（つまり、Hは任意の数のハイパーエッジと頂点を削除してもKonigプロパティを持ちます）。
Hのすべての部分ハイパーグラフにKonigプロパティがある場合（つまり、頂点ではなく、任意の数のハイパーエッジを削除してもHにKonigプロパティがある場合）、Hは通常のハイパーグラフと呼ばれます。
したがって、完全にバランスが取れているとは、バランスが取れていることを意味し、これは正常であることを意味します。
参考文献
^ ベルジュ、クロード（1970）。「確かなハイパーグラフgénéralisantlesgraphesbipartites」。組み合わせ論とその応用。1：119–133。
^ Lovász、ラースローは、Plummer、MD（1986）、Matching Theory、Annals of Discrete Mathematics、29、North-Holland、ISBN 0-444-87916-1、MR 0859549 ^ コンフォルティ、ミケーレ; Cornuéjols、Gérard; カプール、アジャイ; Vušković、クリスティーナ（1996-09-01）。「バランスの取れたハイパーグラフの完全マッチング」。組み合わせ論。16（3）：325–329。土井：10.1007 / BF01261318。ISSN 1439から6912まで。S2CID 206792822。 ^ ベルジュ、クロード; Vergnas、Michel LAS（1970）。「SurUnTheoremsDuTypeKönigPourHypergraphes」。ニューヨーク科学アカデミーの年報。175（1）：32–40。土井：10.1111 /j.1749-6632.1970.tb56451.x。ISSN 1749から6632まで。 ^ Lovász、L。（1972-06-01）。「通常のハイパーグラフとパーフェクトグラフ予想」。離散数学。2（3）：253–267。土井：10.1016 / 0012-365X（72）90006-4。ISSN 0012-365X。 ^ ダールハウス、エリアス; Kratochvíl、1月; マヌエル、ポールD。; ミラー、ミルカ（1997-11-27）。「バランスの取れたハイパーグラフにおける横断分割」。離散応用数学。79（1）：75–89。土井：10.1016 / S0166-218X（97）00034-6。ISSN 0166-218X。 ^ 「着色-二部グラフのどの一般化がより強いですか？」。数学スタック交換。
^ Lehel、Jenö（1985-11-01）。「完全にバランスの取れたハイパーグラフの特性」。離散数学。57（1）：59–65。土井：10.1016 / 0012-365X（85）90156-6。ISSN 0012-365X。 ^ ベッケンバッハ、イザベル; Borndörfer、ラルフ（2018-10-01）。「グラフとハイパーグラフにおけるホールとケーニヒの定理」。離散数学。341（10）：2753–2761。土井：10.1016 /j.disc.2018.06.013。ISSN 0012-365X。
“