| 第106行： |
第106行： |
| | 无环性的四个概念具有可比性: berge-无环性意味着 <math> {\gamma}</math>- 无环性， <math> {\gamma}</math>- 无环性又意味着 <math> {\beta}</math>- 无环性， <math> {\beta}</math>- 无环性又可以推出 <math> {\alpha}</math> 无环性。 然而，反之均不成立。<ref name="fagin1983degrees" /> | | 无环性的四个概念具有可比性: berge-无环性意味着 <math> {\gamma}</math>- 无环性， <math> {\gamma}</math>- 无环性又意味着 <math> {\beta}</math>- 无环性， <math> {\beta}</math>- 无环性又可以推出 <math> {\alpha}</math> 无环性。 然而，反之均不成立。<ref name="fagin1983degrees" /> |
| | | | |
| − | ==同构和相等 Isomorphism and equality== | + | ===同构和相等=== |
| − | A hypergraph [[homomorphism]] is a map from the vertex set of one hypergraph to another such that each edge maps to one other edge.
| + | 超图'''同态 homomorphism'''是指从一个超图的顶点集到另一个超图的顶点集的映射，如此使得每条边映射到另一条边。 |
| | | | |
| − | 超图同态 homomorphism是指从一个超图的顶点集到另一个超图的顶点集的映射，如此使得每条边映射到另一条边。
| |
| | | | |
| − | A hypergraph <math>H=(X,E)</math> is ''isomorphic'' to a hypergraph <math>G=(Y,F)</math>, written as <math>H \simeq G</math> if there exists a [[bijection]]
| + | 如果一个超图 <math>H=(X,E)</math>与另外一个超图<math>G=(Y,F)</math>'''同构 isomorphic '''，则存在一个双射：<math>H \simeq G</math> :<math>\phi:X \to Y</math> |
| − | | |
| − | :<math>\phi:X \to Y</math>
| |
| − | | |
| − | and a [[permutation]] <math>\pi</math> of <math>I</math> such that
| |
| − | | |
| − | :<math>\phi(e_i) = f_{\pi(i)}</math>
| |
| − | | |
| − | The bijection <math>\phi</math> is then called the [[isomorphism]] of the graphs. Note that
| |
| − | | |
| − | :<math>H \simeq G</math> if and only if <math>H^* \simeq G^*</math>.
| |
| − | | |
| − | | |
| − | 如果一个超图 <math>H=(X,E)</math>同构 isomorphic 与另外一个超图<math>G=(Y,F)</math>，则存在一个双射：<math>H \simeq G</math> :<math>\phi:X \to Y</math>
| |
| | | | |
| | 和 关于<math>I</math>的置换 permutation 使得： :<math>\phi(e_i) = f_{\pi(i)}</math> | | 和 关于<math>I</math>的置换 permutation 使得： :<math>\phi(e_i) = f_{\pi(i)}</math> |
| | | | |
| | 那么这个双射被称为图的同构 isomorphism，记作：<math>H \simeq G</math>但且仅当<math>H^* \simeq G^*</math>。 | | 那么这个双射被称为图的同构 isomorphism，记作：<math>H \simeq G</math>但且仅当<math>H^* \simeq G^*</math>。 |
| − |
| |
| − |
| |
| − | When the edges of a hypergraph are explicitly labeled, one has the additional notion of ''strong isomorphism''. One says that <math>H</math> is ''strongly isomorphic'' to <math>G</math> if the permutation is the identity. One then writes <math>H \cong G</math>. Note that all strongly isomorphic graphs are isomorphic, but not vice versa.
| |
| − |
| |
| − | When the vertices of a hypergraph are explicitly labeled, one has the notions of ''equivalence'', and also of ''equality''. One says that <math>H</math> is ''equivalent'' to <math>G</math>, and writes <math>H\equiv G</math> if the isomorphism <math>\phi</math> has
| |
| − |
| |
| − | :<math>\phi(x_n) = y_n</math>
| |
| − |
| |
| − | and
| |
| − |
| |
| − | :<math>\phi(e_i) = f_{\pi(i)}</math>
| |
| − |
| |
| − | Note that
| |
| − |
| |
| − | :<math>H\equiv G</math> if and only if <math>H^* \cong G^*</math>
| |
| − |
| |
| − |
| |
| − | If, in addition, the permutation <math>\pi</math> is the identity, one says that <math>H</math> equals <math>G</math>, and writes <math>H=G</math>. Note that, with this definition of equality, graphs are self-dual:
| |
| − |
| |
| − | :<math>\left(H^*\right) ^* = H</math>
| |
| − |
| |
| − | A hypergraph [[automorphism]] is an isomorphism from a vertex set into itself, that is a relabeling of vertices. The set of automorphisms of a hypergraph ''H'' (= (''X'', ''E'')) is a [[group (mathematics)|group]] under composition, called the [[automorphism group]] of the hypergraph and written Aut(''H'').
| |
| | | | |
| | | | |
| | 当超图的边被明确标记时，就有了'''“强同构 strong isomorphism ”'''这个新的概念。 当前面提及的置换是唯一的，则称<math>H</math> 强同构于 <math>G</math> 。 记作<math>H \cong G</math>。 注意，所有强同构图都是同构的，但反过来就不成立。 | | 当超图的边被明确标记时，就有了'''“强同构 strong isomorphism ”'''这个新的概念。 当前面提及的置换是唯一的，则称<math>H</math> 强同构于 <math>G</math> 。 记作<math>H \cong G</math>。 注意，所有强同构图都是同构的，但反过来就不成立。 |
| | | | |
| − | 当超图的顶点被明确标记时，就有了'''“等价 equivalence”'''和'''“相等 equality”'''的概念。 我们称<math>H</math>和<math>G</math>等价记作：<math>H\equiv G</math> 如果同构<math>\phi</math> 满足:
| |
| | | | |
| − | <math>\phi(x_n) = y_n</math> | + | 当超图的顶点被明确标记时，就有了'''“等价 equivalence”'''和'''“相等 equality”'''的概念。 我们称<math>H</math>和<math>G</math>等价，记作：<math>H\equiv G</math> 。如果同构<math>\phi</math> 满足:<math>\phi(x_n) = y_n</math>而且:<math>\phi(e_i) = f_{\pi(i)}</math> |
| − | | |
| − | 而且: | |
| − | | |
| − | <math>\phi(e_i) = f_{\pi(i)}</math> | |
| | | | |
| | 记作: | | 记作: |
| | <math>H\equiv G</math> 当且仅当 <math>H^* \cong G^*</math> | | <math>H\equiv G</math> 当且仅当 <math>H^* \cong G^*</math> |
| | + | |
| | | | |
| | 超图'''自同构 automorphism'''是从顶点集到自身的同构，也就是顶点的重标号。 超图 <math>{H }</math>(= (''<math>X </math>'', ''<math>E</math>''))的自同构集合是超图的群 group，称为超图的'''自同构群 automorphism group'''，并写成 <math>{Aut(H)}</math>。 | | 超图'''自同构 automorphism'''是从顶点集到自身的同构，也就是顶点的重标号。 超图 <math>{H }</math>(= (''<math>X </math>'', ''<math>E</math>''))的自同构集合是超图的群 group，称为超图的'''自同构群 automorphism group'''，并写成 <math>{Aut(H)}</math>。 |
| | | | |
| − | ===例子 Examples=== | + | |
| | + | ====例子==== |
| | [[File:hg.png|300px|缩略图|右|H、G的图]] | | [[File:hg.png|300px|缩略图|右|H、G的图]] |
| − | Consider the hypergraph <math>H</math> with edges
| + | 考虑超图<math>H</math>，它的边为： |
| − | :<math>H = \lbrace
| |
| − | e_1 = \lbrace a,b \rbrace,
| |
| − | e_2 = \lbrace b,c \rbrace,
| |
| − | e_3 = \lbrace c,d \rbrace,
| |
| − | e_4 = \lbrace d,a \rbrace,
| |
| − | e_5 = \lbrace b,d \rbrace,
| |
| − | e_6 = \lbrace a,c \rbrace
| |
| − | \rbrace</math>
| |
| − | and
| |
| − | :<math>G = \lbrace
| |
| − | f_1 = \lbrace \alpha,\beta \rbrace,
| |
| − | f_2 = \lbrace \beta,\gamma \rbrace,
| |
| − | f_3 = \lbrace \gamma,\delta \rbrace,
| |
| − | f_4 = \lbrace \delta,\alpha \rbrace,
| |
| − | f_5 = \lbrace \alpha,\gamma \rbrace,
| |
| − | f_6 = \lbrace \beta,\delta \rbrace
| |
| − | \rbrace</math>
| |
| − | | |
| − | Then clearly <math>H</math> and <math>G</math> are isomorphic (with <math>\phi(a)=\alpha</math>, ''etc.''), but they are not strongly isomorphic. So, for example, in <math>H</math>, vertex <math>a</math> meets edges 1, 4 and 6, so that,
| |
| − | | |
| − | :<math>e_1 \cap e_4 \cap e_6 = \lbrace a\rbrace</math>
| |
| − | | |
| − | In graph <math>G</math>, there does not exist any vertex that meets edges 1, 4 and 6:
| |
| − | | |
| − | :<math>f_1 \cap f_4 \cap f_6 = \varnothing</math>
| |
| − | | |
| − | In this example, <math>H</math> and <math>G</math> are equivalent, <math>H\equiv G</math>, and the duals are strongly isomorphic: <math>H^*\cong G^*</math>.
| |
| − | | |
| − | | |
| − | 考虑超图<math>H</math>，他的边为： | |
| | | | |
| | <math>H = \lbrace | | <math>H = \lbrace |
| 第222行： |
第153行： |
| | \rbrace</math> | | \rbrace</math> |
| | | | |
| − | 很明显 <math>H</math> 和 <math>G</math> 同构（有<math>\phi(a)=\alpha</math>等），但是他们不是强同构，因为比如在超图<math>H</math>中，<math>a</math> 顶点连接1，4，6三条边，所以：
| |
| − |
| |
| − | <math>e_1 \cap e_4 \cap e_6 = \lbrace a\rbrace</math>
| |
| | | | |
| − | 在图<math>G</math>，不存在连接边1，4，6的顶点：
| + | 很明显 <math>H</math> 和 <math>G</math> 同构（有<math>\phi(a)=\alpha</math>等），但是它们不是强同构，因为比如在超图<math>H</math>中，<math>a</math> 顶点连接1，4，6三条边，所以：<math>e_1 \cap e_4 \cap e_6 = \lbrace a\rbrace</math>。在图<math>G</math>，不存在连接边1，4，6的顶点：<math>f_1 \cap f_4 \cap f_6 = \varnothing</math> |
| | | | |
| − | <math>f_1 \cap f_4 \cap f_6 = \varnothing</math>
| |
| | | | |
| | 在这个例子，<math>H</math> 和 <math>G</math>是等价的， <math>H\equiv G</math>，而且两者的对偶图是强同构的：<math>H^*\cong G^*</math>。 | | 在这个例子，<math>H</math> 和 <math>G</math>是等价的， <math>H\equiv G</math>，而且两者的对偶图是强同构的：<math>H^*\cong G^*</math>。 |