763
个编辑
更改
跳到导航
跳到搜索
第35行：
第35行： − ====定义====+ 第81行：
第81行： + + 第103行：
第105行： + 第156行：
第159行： + 第174行：
第178行： + 第180行：
第185行： + 第192行：
第198行： + 第201行：
第208行： +
→术语
==术语==
==术语==
===定义===
超图有不同的类型，如：
超图有不同的类型，如：
2-段 2-section 超图（或团图 clique graph，表示图 representing graph，原始图 primal graph、盖夫曼图 Gaifman graph）是具有相同顶点的图，并且所有顶点对之间的边包含在相同的超边中。
2-段 2-section 超图（或团图 clique graph，表示图 representing graph，原始图 primal graph、盖夫曼图 Gaifman graph）是具有相同顶点的图，并且所有顶点对之间的边包含在相同的超边中。
===二分图模型===
===二分图模型===
[[File:bipartie graph.jpeg|200px|缩略图|右| 设<math>G=(V,E)</math>是一个无向图，如果顶点V可分割为两个互不相交的子集<math> {(group1, group2)}</math>，并且图中的每条边<math>{（i，j）}</math>所关联的两个顶点<math>{i}</math>和<math>{j}</math>分别属于这两个不同的部分<math>{(i \in group1,j \in group2)}</math>，则称图<math>{G}</math>为一个二分图。]]
[[File:bipartie graph.jpeg|200px|缩略图|右| 设<math>G=(V,E)</math>是一个无向图，如果顶点V可分割为两个互不相交的子集<math> {(group1, group2)}</math>，并且图中的每条边<math>{（i，j）}</math>所关联的两个顶点<math>{i}</math>和<math>{j}</math>分别属于这两个不同的部分<math>{(i \in group1,j \in group2)}</math>，则称图<math>{G}</math>为一个二分图。]]
一个'''超图 <math>{H} </math>'''可以用二分图<math>{BG} </math>表示，其构成如下: 集合<math>X</math>和<math> E </math>是<math>BG</math>的分割，而且 ("x<sub>1</sub>", "e<sub>1</sub>") 与边连通当且仅当顶点"x<sub>1</sub>"包含在<math>H </math>的边" e<sub>1</sub>"中。 反之，任何具有固定的'''部分 part'''且在第二部分中没有不连通节点的二分图也代表具有上述性质的部分超图。 这个二分图也称为'''关联图'''。
一个'''超图 <math>{H} </math>'''可以用二分图<math>{BG} </math>表示，其构成如下: 集合<math>X</math>和<math> E </math>是<math>BG</math>的分割，而且 ("x<sub>1</sub>", "e<sub>1</sub>") 与边连通当且仅当顶点"x<sub>1</sub>"包含在<math>H </math>的边" e<sub>1</sub>"中。 反之，任何具有固定的'''部分 part'''且在第二部分中没有不连通节点的二分图也代表具有上述性质的部分超图。 这个二分图也称为'''关联图'''。
===无环性===
===无环性===
无环性的四个概念具有可比性: berge-无环性意味着 <math> {\gamma}</math>- 无环性， <math> {\gamma}</math>- 无环性又意味着 <math> {\beta}</math>- 无环性， <math> {\beta}</math>- 无环性又可以推出 <math> {\alpha}</math> 无环性。 然而，反之均不成立。<ref name="fagin1983degrees" />
无环性的四个概念具有可比性: berge-无环性意味着 <math> {\gamma}</math>- 无环性， <math> {\gamma}</math>- 无环性又意味着 <math> {\beta}</math>- 无环性， <math> {\beta}</math>- 无环性又可以推出 <math> {\alpha}</math> 无环性。 然而，反之均不成立。<ref name="fagin1983degrees" />
===同构和相等===
===同构和相等===
在这个例子，<math>H</math> 和 <math>G</math>是等价的， <math>H\equiv G</math>，而且两者的对偶图是强同构的：<math>H^*\cong G^*</math>。
在这个例子，<math>H</math> 和 <math>G</math>是等价的， <math>H\equiv G</math>，而且两者的对偶图是强同构的：<math>H^*\cong G^*</math>。
===对称超图 ===
===对称超图 ===
由于超图的对偶性，边传递性的研究与顶点传递性的研究是相似的。
由于超图的对偶性，边传递性的研究与顶点传递性的研究是相似的。
===横截面 ===
===横截面 ===
计算横截面超图在组合优化 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）都有应用。
===关联矩阵===
===关联矩阵===
对于<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>。
===超图着色===
===超图着色===
经典超图着色有许多推广。在允许单色边情况下，混合超图着色是其中之一。一些混合超图对于任意数量的颜色都是不可着色的。同时不可着色性的内在标准是未知的。当一个混合超图是可着色时，其所使用的最小和最大颜色数分别称为下色数和上色数。详情请参阅 http://spectrum.troy.edu/voloshin/mh.html。
经典超图着色有许多推广。在允许单色边情况下，混合超图着色是其中之一。一些混合超图对于任意数量的颜色都是不可着色的。同时不可着色性的内在标准是未知的。当一个混合超图是可着色时，其所使用的最小和最大颜色数分别称为下色数和上色数。详情请参阅 http://spectrum.troy.edu/voloshin/mh.html。
===划分===
===划分===