| 第291行： |
第291行： |
| | ==超图语法 == | | ==超图语法 == |
| | 通过扩充一组替换规则于超图，'''图语法 graph grammar'''可以被推广到超边上。 | | 通过扩充一组替换规则于超图，'''图语法 graph grammar'''可以被推广到超边上。 |
| − |
| |
| − | == Generalizations ==
| |
| − | One possible generalization of a hypergraph is to allow edges to point at other edges. There are two variations of this generalization. In one, the edges consist not only of a set of vertices, but may also contain subsets of vertices, subsets of subsets of vertices and so on ''ad infinitum''. In essence, every edge is just an internal node of a tree or [[directed acyclic graph]], and vertices are the leaf nodes. A hypergraph is then just a collection of trees with common, shared nodes (that is, a given internal node or leaf may occur in several different trees). Conversely, every collection of trees can be understood as this generalized hypergraph. Since trees are widely used throughout [[computer science]] and many other branches of mathematics, one could say that hypergraphs appear naturally as well. So, for example, this generalization arises naturally as a model of [[term algebra]]; edges correspond to [[term (logic)|terms]] and vertices correspond to constants or variables.
| |
| − |
| |
| − | For such a hypergraph, set membership then provides an ordering, but the ordering is neither a [[partial order]] nor a [[preorder]], since it is not transitive. The graph corresponding to the Levi graph of this generalization is a [[directed acyclic graph]]. Consider, for example, the generalized hypergraph whose vertex set is <math>V= \{a,b\}</math> and whose edges are <math>e_1=\{a,b\}</math> and <math>e_2=\{a,e_1\}</math>. Then, although <math>b\in e_1</math> and <math>e_1\in e_2</math>, it is not true that <math>b\in e_2</math>. However, the [[transitive closure]] of set membership for such hypergraphs does induce a [[partial order]], and "flattens" the hypergraph into a [[partially ordered set]].
| |
| − |
| |
| − | Alternately, edges can be allowed to point at other edges, irrespective of the requirement that the edges be ordered as directed, acyclic graphs. This allows graphs with edge-loops, which need not contain vertices at all. For example, consider the generalized hypergraph consisting of two edges <math>e_1</math> and <math>e_2</math>, and zero vertices, so that <math>e_1 = \{e_2\}</math> and <math>e_2 = \{e_1\}</math>. As this loop is infinitely recursive, sets that are the edges violate the [[axiom of foundation]]. In particular, there is no transitive closure of set membership for such hypergraphs. Although such structures may seem strange at first, they can be readily understood by noting that the equivalent generalization of their Levi graph is no longer [[Bipartite graph|bipartite]], but is rather just some general [[directed graph]].
| |
| − |
| |
| − | The generalized incidence matrix for such hypergraphs is, by definition, a square matrix, of a rank equal to the total number of vertices plus edges. Thus, for the above example, the [[incidence matrix]] is simply
| |
| − |
| |
| − | :<math>\left[ \begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix} \right].</math>
| |
| − |
| |
| | | | |
| | ==超图概念的延伸== | | ==超图概念的延伸== |