763
个编辑
更改
跳到导航
跳到搜索
第106行：
第106行： − + − 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是指从一个超图的顶点集到另一个超图的顶点集的映射，如此使得每条边映射到另一条边。 − 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> − − 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> − − − 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''). − 当超图的顶点被明确标记时，就有了'''“等价 equivalence”'''和'''“相等 equality”'''的概念。 我们称<math>H</math>和<math>G</math>等价记作：<math>H\equiv G</math> 如果同构<math>\phi</math> 满足: − + − − − − + − + + − Consider the hypergraph <math>H</math> with edges+ − :<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>. − − − 第222行：
第153行： − 很明显 <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>
→同构和相等 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==
===同构和相等===
超图'''同态 homomorphism'''是指从一个超图的顶点集到另一个超图的顶点集的映射，如此使得每条边映射到另一条边。
如果一个超图 <math>H=(X,E)</math>与另外一个超图<math>G=(Y,F)</math>'''同构 isomorphic '''，则存在一个双射：<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>。
当超图的边被明确标记时，就有了'''“强同构 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>。 注意，所有强同构图都是同构的，但反过来就不成立。
<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的图]]
考虑超图<math>H</math>，它的边为：
考虑超图<math>H</math>，他的边为：
<math>H = \lbrace
<math>H = \lbrace
\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>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>。