763
个编辑
更改
跳到导航
跳到搜索
第54行：
第54行： − + − + − − − − − − + − + − − − − − :: 一个'''子超图'''的'''扩展 extension'''是一个超图，其中每个属于 <math>H</math> 的超边都部分包含在子超图的 <math>H_A</math>中，并且完全包含在扩展的 <math>Ex(H_A)</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>A\subseteq X</math>，则''section hypergraph''是部分超图: − + − + − − − − − 当等式的记号被合理定义时，如下所示，对一个超图采取两次乘方 involution运算是就可得到<math>H</math> 的对偶： − 第98行：
第77行： − 一个超图是二分（bipartite）的，当且仅当它的顶点能被分成两类''U'' 和 ''V'' ：每个基数至少为 2 超边包含两类中的至少一个顶点。换而言之，超图则被称为具有 B 属性 Property B。+
→定义
假定 <math>H=(X,E)</math> 是一个超图，包含顶点集：
假定 <math>H=(X,E)</math> 是一个超图，包含顶点集：<math>X = \lbrace x_i | i \in I_v \rbrace,</math>和 “边集”：
<math>E = \lbrace e_i | i\in I_e \land e_i \subseteq X \land e_i \neq \emptyset \rbrace,</math>
<math>X = \lbrace x_i | i \in I_v \rbrace,</math>
和 “边集”：
其中 <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> 被定义为：<math>H_A=\left(A, \lbrace e \cap A | e \in E \land
e \cap A \neq \emptyset \rbrace \right).</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>H_A=\left(A, \lbrace e \cap A | e \in E \land
e \cap A \neq \emptyset \rbrace \right).</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> 生成的部分超图就是<math>\left(X, \lbrace e_i | i\in J \rbrace \right).</math>
<math>H \times A = \left(A, \lbrace e_i |
*而给定一个子集 <math>A\subseteq X</math>，则'''分段超图 section hypergraphs'''是部分超图:<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>H</math> 的对偶 <math>H^*</math> 则是一个顶点和边互换的超图，因此顶点由 <math>\lbrace e_i \rbrace</math> 给出，边由 <math>\lbrace X_m \rbrace</math> 给出，其中:
<math>H</math> 的对偶 <math>H^*</math> 则是一个顶点和边互换的超图，因此顶点由 <math>\lbrace e_i \rbrace</math> 给出，边由 <math>\lbrace X_m \rbrace</math> 给出，其中:<math>X_m = \lbrace e_i | x_m \in e_i \rbrace. </math>。当等式的记号被合理定义时，如下所示，对一个超图采取两次乘方 involution运算是就可得到<math>H</math> 的对偶：<math>\left(H^*\right)^* = H.</math>
<math>X_m = \lbrace e_i | x_m \in e_i \rbrace. </math>
<math>\left(H^*\right)^* = H.</math>
一个超图是二分 bipartite的，当且仅当它的顶点能被分成两类''U'' 和 ''V'' ：每个基数至少为 2 超边包含两类中的至少一个顶点。换而言之，超图则被称为具有 B 属性 Property B。