1,526
个编辑
更改
跳到导航
跳到搜索
第172行：
第172行： − + − + + + 第186行：
第188行： + + + + + + + + 第200行：
第210行： + 第207行：
第218行： − + + + + + + + + + + + + + + + + + 第236行：
第263行： + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
→Isomorphism and equality
无环性的四个概念具有可比性: 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>
:<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.
:<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:
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
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==