更改

超图 Hypergraph (查看源代码)

2020年4月23日 (四) 10:05的版本

删除756字节、 2020年4月23日 (四) 10:05

第181行：第181行：

计算横截面超图在组合优化 Combinatorial Optimization、[[博弈论 Game Theory]]和计算机科学 Computer Science的一些领域（例如机器学习 Machine Learning、数据库索引 Indexing of Databases、可满足性问题 the Satisfiability Problem、数据挖掘 Data Mining和计算机程序优化 Program Optimization）都有应用。

−

==~~Incidence matrix~~==

+

==关联矩阵==

−

Let <math>V = \{v_1, v_2, ~\ldots, ~ v_n\}</math> and <math>E = \{e_1, e_2, ~ \ldots ~ e_m\}</math>. Every hypergraph has an <math>n \times m</math> [[incidence matrix]] <math>A = (a_{ij})</math> where

−

~~:<math>a_{ij} = \left\{ \begin{matrix} 1 & \mathrm{if} ~ v_i \in e_j \\ 0 & \mathrm{otherwise}. \end{matrix} \right.</math>~~

−

The [[transpose]] <math>A^t</math> of the [[incidence (geometry)|incidence]] matrix defines a hypergraph <math>H^* = (V^*,\ E^*)</math> called the '''dual''' of <math>H</math>, where <math>V^*</math> is an ''m''-element set and <math>E^*</math> is an ''n''-element set of subsets of <math>V^*</math>. For <math>v^*_j \in V^*</math> and <math>e^*_i \in E^*, ~ v^*_j \in e^*_i</math> [[if and only if]] <math>a_{ij} = 1</math>.

−

分别设 <math>V = \{v_1, v_2, ~\ldots, ~ v_n\}</math>， <math>E = \{e_1, e_2, ~ \ldots ~ e_m\}</math>。

每一个超图都有一个 <math>n \times m</math> '''关联矩阵 incidence matrix'''<math>A = (a_{ij})</math>，其为：<math>a_{ij} = \left\{ \begin{matrix} 1 & \mathrm{if} ~ v_i \in e_j \\ 0 & \mathrm{otherwise}. \end{matrix} \right.</math>。

+

其关联矩阵的转置 transpose <math>A^t</math>定义了 <math>H^* = (V^*,\ E^*)</math>称为<math>H</math>的'''对偶'''，其中<math>V^*</math>是一个''m''元集合， <math>E^*</math>是<math>V^*</math>的一个''n''元子集。

+

对于<math>v^*_j \in V^*</math> 和 <math>e^*_i \in E^*, ~ v^*_j \in e^*_i</math> 当且仅当 <math>a_{ij} = 1</math>。

乐多多

763

个编辑