更改

超图 Hypergraph (查看源代码)

2020年4月23日 (四) 09:41的版本

添加85字节、 2020年4月23日 (四) 09:41

→‎定义

第54行：第54行： −

假定 <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

−

*'''子超图 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>

−

~~:: 一个~~'''子超图'''的'''扩展 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>。

−

*'''部分超图 partial hypergraph'''是去掉一些边的超图。给定一个边索引集的子集 <math>J \subset I_e</math> ，由 <math>J</math> 生成的部分超图就是

−

~~<math>\left(X, \lbrace e_i | i\in J \rbrace \right).</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''是部分超图:

−

<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>

−

<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>

−

~~当等式的记号被合理定义时，如下所示，对一个超图采取两次乘方~~ involution运算是就可得到<math>H</math> 的对偶：

−

<math>\left(H^*\right)^* = H.</math>

第98行：第77行： −

~~一个超图是二分（bipartite）的，当且仅当它的顶点能被分成两类~~''U'' 和 ''V'' ：每个基数至少为 2 超边包含两类中的至少一个顶点。换而言之，超图则被称为具有 B 属性 Property B。

+

一个超图是二分 bipartite的，当且仅当它的顶点能被分成两类''U'' 和 ''V'' ：每个基数至少为 2 超边包含两类中的至少一个顶点。换而言之，超图则被称为具有 B 属性 Property B。

乐多多

763

个编辑