第172行: |
第172行: |
| 无环性的四个概念具有可比性: 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== | + | ==同构和相等 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. | | A hypergraph [[homomorphism]] is a map from the vertex set of one hypergraph to another such that each edge maps to one other edge. |
| | | |
− | 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]] | + | 超图同态 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>\phi:X \to Y</math> | | :<math>\phi:X \to Y</math> |
第186行: |
第188行: |
| | | |
| :<math>H \simeq G</math> if and only if <math>H^* \simeq G^*</math>. | | :<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> |
| + | |
| + | 那么这个双射被称为图的同构 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 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. |
第200行: |
第210行: |
| | | |
| :<math>H\equiv G</math> if and only if <math>H^* \cong G^*</math> | | :<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: | | 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: |
第207行: |
第218行: |
| 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''). | | 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''). |
| | | |
− | ===Examples=== | + | |
| + | 当超图的边被明确标记时,就有了'''“强同构 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> |
| + | |
| + | 而且: |
| + | |
| + | <math>\phi(e_i) = f_{\pi(i)}</math> |
| + | |
| + | 记作: |
| + | <math>H\equiv G</math> 当且仅当 <math>H^* \cong G^*</math> |
| + | |
| + | 超图'''自同构 automorphism'''是从顶点集到自身的同构,也就是顶点的重标号。 超图“ <math>{H }</math>”(= (''X'', ''E''))的自同构集合是超图的群 group,称为超图的'''自同构群 automorphism group''',并写成 <math>{Aut(''H'')}</math>。 |
| + | |
| + | ===例子 Examples=== |
| Consider the hypergraph <math>H</math> with edges | | Consider the hypergraph <math>H</math> with edges |
| :<math>H = \lbrace | | :<math>H = \lbrace |
第236行: |
第263行: |
| | | |
| 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>. | | 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 |
| + | 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> |
| + | |
| + | 和超图<math>G</math>: |
| + | |
| + | <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> |
| + | |
| + | 很明显 <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>H</math> 和 <math>G</math>是等价的, <math>H\equiv G</math>,而且两者强同构的:<math>H^*\cong G^*</math> |
| | | |
| ==Symmetric hypergraphs== | | ==Symmetric hypergraphs== |