Content deleted Content added
Added illustration and description. |
m v2.05b - Bot T5 CW#2 - Fix errors for CW project (Tag with incorrect syntax) |
||
| (One intermediate revision by one other user 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 4 ⟶ 10:
== Definition by 2-colorability ==
▲[[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.
▲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.
▲Any ''singletons'', or edges with only 1 vertex, are disregarded, as these obviously cannot be 2-colored.]]
A hypergraph ''H'' = (''V'', ''E'') is called '''2-colorable''' if its vertices can be 2-colored so that no hyperedge is monochromatic. Every bipartite graph ''G'' = (''X''+''Y'', ''E'') is 2-colorable: each edge contains exactly one vertex of ''X'' and one vertex of ''Y'', so e.g. ''X'' can be colored blue and ''Y'' can be colored yellow and no edge is monochromatic.
| |||