更改

跳到导航 跳到搜索
删除2,889字节 、 2020年4月23日 (四) 09:29
第50行: 第50行:  
* 无环超图 Acyclic hypergraph:不包含任何环的超图。
 
* 无环超图 Acyclic hypergraph:不包含任何环的超图。
   −
  −
Because hypergraph links can have any cardinality, there are several notions of the concept of a subgraph, called ''subhypergraphs'', ''partial hypergraphs'' and ''section hypergraphs''.
      
因为超图中的连接可以有任意基数,所以有好几种关于子图的概念,分别是'''子超图 subhypergraphs'''、'''部分超图 partial hypergraphs'''和'''分段超图 section hypergraphs'''。
 
因为超图中的连接可以有任意基数,所以有好几种关于子图的概念,分别是'''子超图 subhypergraphs'''、'''部分超图 partial hypergraphs'''和'''分段超图 section hypergraphs'''。
  −
  −
Let <math>H=(X,E)</math> be the hypergraph consisting of vertices
  −
  −
:<math>X = \lbrace x_i | i \in I_v \rbrace,</math>
  −
  −
and having ''edge set''
  −
  −
:<math>E = \lbrace e_i | i\in I_e \land e_i \subseteq X \land e_i \neq \emptyset \rbrace,</math>
  −
  −
where <math>I_v</math> and <math>I_e</math> are the [[index set]]s of the vertices and edges respectively.
        第73行: 第60行:  
和 “边集”:
 
和 “边集”:
   −
<math>E = \lbrace e_i | i\in I_e \land e_i \subseteq X \land e_i \neq \emptyset \rbrace,</math>
      
其中 <math>I_v</math> 和 <math>I_e</math> 分别是顶点和边集的索引集 index set
 
其中 <math>I_v</math> 和 <math>I_e</math> 分别是顶点和边集的索引集 index set
   −
A ''subhypergraph'' is a hypergraph with some vertices removed.  Formally, the subhypergraph <math>H_A</math> induced by <math>A \subseteq X </math> is defined as
  −
  −
:<math>H_A=\left(A, \lbrace e \cap A | e \in E \land
  −
e \cap A \neq \emptyset \rbrace \right).</math>
      
*'''子超图 subhypergraph''' 是去掉某些顶点的超图。在形式上,若 <math>A \subseteq X </math> 是顶点子集,则子超图 <math>H_A</math> 被定义为:
 
*'''子超图 subhypergraph''' 是去掉某些顶点的超图。在形式上,若 <math>A \subseteq X </math> 是顶点子集,则子超图 <math>H_A</math> 被定义为:
第87行: 第69行:  
e \cap A \neq \emptyset \rbrace \right).</math>
 
e \cap A \neq \emptyset \rbrace \right).</math>
   −
An ''extension'' of a ''subhypergraph'' is a hypergraph where each
  −
hyperedge of <math>H</math> which is partially contained in the subhypergraph <math>H_A</math> and is fully contained in the extension <math>Ex(H_A)</math>.
  −
Formally
      
:: 一个'''子超图'''的'''扩展 extension'''是一个超图,其中每个属于 <math>H</math> 的超边都部分包含在子超图的 <math>H_A</math>中,并且完全包含在扩展的 <math>Ex(H_A)</math> 中。即在形式上:
 
:: 一个'''子超图'''的'''扩展 extension'''是一个超图,其中每个属于 <math>H</math> 的超边都部分包含在子超图的 <math>H_A</math>中,并且完全包含在扩展的 <math>Ex(H_A)</math> 中。即在形式上:
 
:<math>Ex(H_A) = (A \cup A', E' )</math>和 <math>A' = \bigcup_{e \in E} e \setminus A</math> 和<math>E' = \lbrace e \in E | e \subseteq (A \cup A') \rbrace</math>。
 
:<math>Ex(H_A) = (A \cup A', E' )</math>和 <math>A' = \bigcup_{e \in E} e \setminus A</math> 和<math>E' = \lbrace e \in E | e \subseteq (A \cup A') \rbrace</math>。
   −
  −
The ''partial hypergraph'' is a hypergraph with some edges removed. Given a subset <math>J \subset I_e</math> of the edge index set, the partial hypergraph generated by <math>J</math> is the hypergraph
      
*'''部分超图 partial hypergraph'''是去掉一些边的超图。给定一个边索引集的子集 <math>J \subset I_e</math> ,由 <math>J</math> 生成的部分超图就是
 
*'''部分超图 partial hypergraph'''是去掉一些边的超图。给定一个边索引集的子集 <math>J \subset I_e</math> ,由 <math>J</math> 生成的部分超图就是
第101行: 第78行:  
<math>\left(X, \lbrace e_i | i\in J \rbrace \right).</math>
 
<math>\left(X, \lbrace e_i | i\in J \rbrace \right).</math>
   −
  −
Given a subset <math>A\subseteq X</math>, the ''section hypergraph'' is the partial hypergraph
      
*而给定一个子集  <math>A\subseteq X</math>,则''section hypergraph''是部分超图:
 
*而给定一个子集  <math>A\subseteq X</math>,则''section hypergraph''是部分超图:
第108行: 第83行:  
<math>H \times A = \left(A, \lbrace e_i |  
 
<math>H \times A = \left(A, \lbrace e_i |  
 
i\in I_e \land e_i \subseteq A  \rbrace \right).</math>
 
i\in I_e \land e_i \subseteq A  \rbrace \right).</math>
  −
The '''dual''' <math>H^*</math> of <math>H</math> is a hypergraph whose vertices and edges are interchanged, so that the vertices are given by <math>\lbrace e_i \rbrace</math> and whose edges are given by <math>\lbrace X_m \rbrace</math> where
        第116行: 第89行:  
<math>X_m = \lbrace e_i | x_m \in e_i \rbrace. </math>
 
<math>X_m = \lbrace e_i | x_m \in e_i \rbrace. </math>
   −
When a notion of equality is properly defined, as done below, the operation of taking the dual of a hypergraph is an [[involution (mathematics)|involution]], i.e.,
      
当等式的记号被合理定义时,如下所示,对一个超图采取两次乘方 involution运算是就可得到<math>H</math> 的对偶:
 
当等式的记号被合理定义时,如下所示,对一个超图采取两次乘方 involution运算是就可得到<math>H</math> 的对偶:
 
<math>\left(H^*\right)^* = H.</math>
 
<math>\left(H^*\right)^* = H.</math>
   −
A [[connected graph]] ''G'' with the same vertex set as a connected hypergraph ''H'' is a '''host graph''' for ''H'' if every hyperedge of ''H'' [[induced subgraph|induces]] a connected subgraph in  ''G''. For a disconnected hypergraph ''H'', ''G'' is a host graph if there is a bijection between the [[connected component (graph theory)|connected components]] of ''G'' and of ''H'', such that each connected component ''G<nowiki>'</nowiki>'' of ''G'' is a host of the corresponding ''H<nowiki>'</nowiki>''.
      
对于连通的超图'' G'' 和具有相同顶点连通的超图 ''H'',如果 ''H'' 的每个超边都由 ''G'' 中一个子图导出 induce,则 ''G'' 是一个主图 host graph;
 
对于连通的超图'' G'' 和具有相同顶点连通的超图 ''H'',如果 ''H'' 的每个超边都由 ''G'' 中一个子图导出 induce,则 ''G'' 是一个主图 host graph;
 
对于不连通的超图 H,如果 ''G'' 和 ''H'' 的连通部分之间存在一个双射,使得 G 的每个连通部分 ''G'' 都是对应的 ''H'' 的主图,则 ''G'' 是一个主图。
 
对于不连通的超图 H,如果 ''G'' 和 ''H'' 的连通部分之间存在一个双射,使得 G 的每个连通部分 ''G'' 都是对应的 ''H'' 的主图,则 ''G'' 是一个主图。
   −
A hypergraph is ''bipartite'' if and only if its vertices can be partitioned into two classes ''U'' and ''V'' in such a way that each hyperedge with cardinality at least 2 contains at least one vertex from both classes. Alternatively, such a hypergraph is said to have [[Property B]].
      
一个超图是二分(bipartite)的,当且仅当它的顶点能被分成两类''U'' 和 ''V''  :每个基数至少为 2 超边包含两类中的至少一个顶点。换而言之,超图则被称为具有 B 属性 Property B。
 
一个超图是二分(bipartite)的,当且仅当它的顶点能被分成两类''U'' 和 ''V''  :每个基数至少为 2 超边包含两类中的至少一个顶点。换而言之,超图则被称为具有 B 属性 Property B。
   −
The '''2-section''' (or '''clique graph''', '''representing graph''', '''primal graph''', '''Gaifman graph''') of a hypergraph is the graph with the same vertices of the hypergraph, and edges between all pairs of vertices contained in the same hyperedge.
      
2-段 2-section 超图(或团图 clique graph,表示图 representing graph,原始图 primal graph、盖夫曼图 Gaifman graph)是具有相同顶点的图,并且所有顶点对之间的边包含在相同的超边中。
 
2-段 2-section 超图(或团图 clique graph,表示图 representing graph,原始图 primal graph、盖夫曼图 Gaifman graph)是具有相同顶点的图,并且所有顶点对之间的边包含在相同的超边中。
763

个编辑

导航菜单