Content deleted Content added
Citation bot (talk | contribs) Add: s2cid. Removed proxy/dead URL that duplicated identifier. | Use this bot. Report bugs. | Suggested by SemperIocundus | #UCB_webform 620/2500 |
m v2.05b - Bot T5 CW#2 - Fix errors for CW project (Tag with incorrect syntax) |
||
| (5 intermediate revisions by 3 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 22 ⟶ 28:
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=
* 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|journal=Discrete Applied Mathematics|language=en|volume=79|issue=1|pages=75–89|doi=10.1016/S0166-218X(97)00034-6|issn=0166-218X|doi-access=
== 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.
| |||