763
个编辑
更改
跳到导航
跳到搜索
第50行：
第50行： − − Because hypergraph links can have any cardinality, there are several notions of the concept of a subgraph, called ''subhypergraphs'', ''partial hypergraphs'' and ''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> − 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> 第87行：
第69行： − 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 − − 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 第101行：
第78行： − − Given a subset <math>A\subseteq X</math>, the ''section hypergraph'' is the partial hypergraph 第108行：
第83行： − − 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行： − 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., − 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>''. − 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]]. − 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.
→术语
* 无环超图 Acyclic hypergraph：不包含任何环的超图。
* 无环超图 Acyclic hypergraph：不包含任何环的超图。
因为超图中的连接可以有任意基数，所以有好几种关于子图的概念，分别是'''子超图 subhypergraphs'''、'''部分超图 partial hypergraphs'''和'''分段超图 section hypergraphs'''。
因为超图中的连接可以有任意基数，所以有好几种关于子图的概念，分别是'''子超图 subhypergraphs'''、'''部分超图 partial hypergraphs'''和'''分段超图 section hypergraphs'''。
和 “边集”：
和 “边集”：
其中 <math>I_v</math> 和 <math>I_e</math> 分别是顶点和边集的索引集 index set
其中 <math>I_v</math> 和 <math>I_e</math> 分别是顶点和边集的索引集 index set
*'''子超图 subhypergraph''' 是去掉某些顶点的超图。在形式上，若 <math>A \subseteq X </math> 是顶点子集，则子超图 <math>H_A</math> 被定义为：
*'''子超图 subhypergraph''' 是去掉某些顶点的超图。在形式上，若 <math>A \subseteq X </math> 是顶点子集，则子超图 <math>H_A</math> 被定义为：
e \cap A \neq \emptyset \rbrace \right).</math>
e \cap A \neq \emptyset \rbrace \right).</math>
:: 一个'''子超图'''的'''扩展 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>。
*'''部分超图 partial hypergraph'''是去掉一些边的超图。给定一个边索引集的子集 <math>J \subset I_e</math> ，由 <math>J</math> 生成的部分超图就是
*'''部分超图 partial hypergraph'''是去掉一些边的超图。给定一个边索引集的子集 <math>J \subset I_e</math> ，由 <math>J</math> 生成的部分超图就是
<math>\left(X, \lbrace e_i | i\in J \rbrace \right).</math>
<math>\left(X, \lbrace e_i | i\in J \rbrace \right).</math>
*而给定一个子集 <math>A\subseteq X</math>，则''section hypergraph''是部分超图:
*而给定一个子集 <math>A\subseteq X</math>，则''section hypergraph''是部分超图:
<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>
<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>
当等式的记号被合理定义时，如下所示，对一个超图采取两次乘方 involution运算是就可得到<math>H</math> 的对偶：
当等式的记号被合理定义时，如下所示，对一个超图采取两次乘方 involution运算是就可得到<math>H</math> 的对偶：
<math>\left(H^*\right)^* = H.</math>
<math>\left(H^*\right)^* = H.</math>
对于连通的超图'' 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'' 是一个主图。
一个超图是二分（bipartite）的，当且仅当它的顶点能被分成两类''U'' 和 ''V'' ：每个基数至少为 2 超边包含两类中的至少一个顶点。换而言之，超图则被称为具有 B 属性 Property B。
一个超图是二分（bipartite）的，当且仅当它的顶点能被分成两类''U'' 和 ''V'' ：每个基数至少为 2 超边包含两类中的至少一个顶点。换而言之，超图则被称为具有 B 属性 Property B。
2-段 2-section 超图（或团图 clique graph，表示图 representing graph，原始图 primal graph、盖夫曼图 Gaifman graph）是具有相同顶点的图，并且所有顶点对之间的边包含在相同的超边中。
2-段 2-section 超图（或团图 clique graph，表示图 representing graph，原始图 primal graph、盖夫曼图 Gaifman graph）是具有相同顶点的图，并且所有顶点对之间的边包含在相同的超边中。