Content deleted Content added
m Task 18 (cosmetic): eval 8 templates: del empty params (2×); |
m v2.05b - Bot T5 CW#2 - Fix errors for CW project (Tag with incorrect syntax) |
||
| (8 intermediate revisions by 4 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]].
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|last1=Conforti|first1=Michele|last2=Cornuéjols|first2=Gérard|last3=Kapoor|first3=Ajai|last4=Vušković|first4=Kristina|author4-link= Kristina Vušković |date=1996-09-01|title=Perfect matchings in balanced hypergraphs|journal=Combinatorica|language=en|volume=16|issue=3|pages=325–329|doi=10.1007/BF01261318|s2cid=206792822|issn=1439-6912}}</ref>
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|last1=Berge|first1=Claude|last2=Vergnas|first2=Michel LAS|date=1970|title=Sur Un Theorems Du Type König Pour Hypergraphes|journal=Annals of the New York Academy of Sciences|language=en|volume=175|issue=1|pages=32–40|doi=10.1111/j.1749-6632.1970.tb56451.x|s2cid=84670737 |issn=1749-6632}}</ref><ref name="lp" />{{Rp|468–470}}
* 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|journal=Discrete Mathematics|language=en|volume=2|issue=3|pages=253–267|doi=10.1016/0012-365X(72)90006-4|issn=0012-365X|doi-access=}}</ref> This generalizes a theorem of Konig on bipartite graphs.
* 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|last1=Dahlhaus|first1=Elias|last2=Kratochvíl|first2=Jan|last3=Manuel|first3=Paul D.|last4=Miller|first4=Mirka|date=1997-11-27|title=Transversal partitioning in balanced hypergraphs
== Comparison with other notions of bipartiteness ==
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|last1=Beckenbach|first1=Isabel|last2=Borndörfer|first2=Ralf|date=2018-10-01|title=Hall's and Kőnig's theorem in graphs and hypergraphs
Thus, totally-balanced implies balanced, which implies normal.
| |||