更改

删除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)都有应用。
 
计算横截面超图在组合优化 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>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>。
 
每一个超图都有一个 <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''元子集。
 
其关联矩阵的转置 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>。
 
对于<math>v^*_j \in V^*</math> 和 <math>e^*_i \in E^*, ~ v^*_j \in e^*_i</math> 当且仅当 <math>a_{ij} = 1</math>。
763

个编辑