Content deleted Content added
Erel Segal (talk | contribs) |
m v2.05b - Bot T5 CW#2 - Fix errors for CW project (Tag with incorrect syntax) |
||
| (11 intermediate revisions by 5 users not shown) | |||
Line 1:
[[File:Balanced hypergraph, first definition.svg|thumb|300px|The initial graph is '''2-colorable''', as the vertices can be colored such that each edge has one of each color.
<br /><br />
Any number of any vertices (here, 1 vertex, vertex "v2") can be deleted from the initial graph, as shown in the next graph. After re-coloring the vertices, it is shown the graph is still 2-colorable.
<br /><br />
Any ''singletons'', or edges with only 1 vertex, are disregarded, as these obviously cannot be 2-colored.]]
In [[graph theory]], a '''balanced hypergraph''' is a [[hypergraph]] that has several properties analogous to that of a [[bipartite graph]].
Balanced hypergraphs were introduced by [[Claude Berge|Berge]]<ref name=":0">{{Cite journal|last=Berge|first=Claude|date=1970|title=Sur certains hypergraphes généralisant les graphes bipartites
== Definition by 2-colorability ==
Line 13 ⟶ 19:
A '''cycle''' (or a '''circuit''') in a hypergraph is a cyclic alternating sequence of distinct vertices and hyperedges: (''v''<sub>1</sub>, ''e''<sub>1</sub>, ''v''<sub>2</sub>, ''e''<sub>2</sub>, ..., ''v<sub>k</sub>'', ''e<sub>k</sub>'', ''v<sub>k</sub>''<sub>+1</sub>=''v''<sub>1</sub>), where every vertex ''v<sub>i</sub>'' is contained in both ''e<sub>i</sub>''<sub>−1</sub> and ''e<sub>i</sub>''. The number ''k'' is called the ''length'' of the cycle.
A hypergraph is '''balanced''' iff every odd-length cycle ''C'' in ''H'' has an edge containing at least three vertices of ''C''.<ref name=":1">{{Cite journal|
Note that in a simple graph all edges contain only two vertices. Hence, a simple graph is balanced iff it contains no odd-length cycles at all, which holds iff it is bipartite.
Line 20 ⟶ 26:
== Properties ==
Some theorems on bipartite graphs have been generalized to balanced hypergraphs.<ref>{{Cite journal|
* In every balanced hypergraph, the minimum [[Vertex cover in hypergraphs|vertex-cover]] has the same size as its maximum [[Matching in hypergraphs|matching]]. This generalizes the [[Kőnig's theorem (graph theory)|Kőnig-Egervary theorem]] on bipartite graphs.
* In every balanced hypergraph, the [[Degree (graph theory)|degree]] (= the maximum number of hyperedges containing some one vertex) equals the [[Edge coloring|chromatic index]] (= the least number of colors required for coloring the hyperedges such that no two hyperedges with the same color have a vertex in common).<ref>{{Cite journal|last=Lovász|first=L.|date=1972-06-01|title=Normal hypergraphs and the perfect graph conjecture
* Every balanced hypergraph satisfies a generalization of [[Hall's marriage theorem]]:<ref name=":1" /> it admits a perfect matching iff for all disjoint vertex-sets ''V''<sub>1</sub>, ''V''<sub>2</sub>, if <math>|e\cap V_2| \geq |e\cap V_1|</math> for all edges ''e'' in ''E'', then |''V''<sub>2</sub>| ≥ |''V''<sub>1</sub>|. See [[Hall-type theorems for hypergraphs]].
* Every balanced hypergraph with maximum degree ''D'', can be partitioned into ''D'' edge-disjoint matchings.<ref name=":0" />{{Rp|Chapter 5}}<ref name=":1" />{{Rp|Corollary 3}}
A ''k''-fold transversal of a balanced hypergraph can be expressed as a union of ''k'' pairwise-disjoint transversals, and such partition can be obtained in polynomial time.<ref>{{Cite journal|
== Comparison with other notions of bipartiteness ==
Line 45 ⟶ 51:
=== Totally balanced hypergraphs ===
A hypergraph is called '''totally balanced''' if every cycle ''C'' in ''H'' of length at least 3 (not necessarily odd-length) has an edge containing at least three vertices of ''C''.<ref name=":2">{{Cite journal|last=Lehel|first=Jenö|date=1985-11-01|title=A characterization of totally balanced hypergraphs
A hypergraph H is totally balanced iff every subhypergraph of H is a tree-hypergraph.<ref name=":2" />
Line 54 ⟶ 60:
The balanced hypergraphs are exactly the hypergraphs H such that every ''partial subhypergraph'' of ''H'' has the Konig property (i.e., H has the Konig property even upon deleting any number of hyperedges and vertices).
If every ''partial'' hypergraph of H has the Konig property (i.e., H has the Konig property even upon deleting any number of hyperedges - but not vertices), then H is called a '''normal hypergraph'''.<ref name=":02">{{Cite journal|
Thus, totally-balanced implies balanced, which implies normal.
| |||