Content deleted Content added
add categories and remove maintenance tag |
Sweetabena (talk | contribs) mNo edit summary |
||
Line 8:
A [[hypergraph]] is a generalization of a [[graph]]. Formally, a hypergraph <math>H = (V, E)</math> consists of a set of [[vertex (graph theory)|vertices]] ''V'', and of a set ''E'' of [[hyperedge]]s, each of which is a subset of the vertices ''V''. Given a hypergraph, we can define its ''primal graph'' as the undirected graph defined on the same set of vertices, in which we put an edge between any two vertices which occur together in some hyperedge.
A hypergraph ''H'' is '''α-acyclic''' if it satisfies two conditions: being chordal and being conformal. More precisely, we say that ''H'' is chordal if its primal graph is a [[chordal graph]]. We say that ''H'' is conformal if, for every [[clique (graph theory)|clique]] of the primal graph, there is a hyperedge of ''H'' containing all the vertices of the clique.
The GYO algorithm takes as input a hypergraph and determines if it is α-acyclic in this sense.
Line 14:
== Principle of the algorithm ==
The algorithm iteratively removes the so-called ''ears'' of the hypergraph, until the hypergraph is fully decomposed.
Formally, an ''ear'' of the hypergraph ''H'' is a hyperedge ''e'' which is "almost covered" by another hyperedge ''f'', in the sense that the vertices of ''e'' can be split into two groups:
| |||