763
个编辑
更改
跳到导航
跳到搜索
第181行：
第181行： − + − 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>. − − + +
→Incidence matrix
计算横截面超图在组合优化 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==
==关联矩阵==
分别设 <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>。