更改

跳到导航 跳到搜索
删除38字节 、 2020年4月22日 (三) 13:26
第175行: 第175行:     
一个尚未解决的与子图相关的猜想,'''重构猜想 Reconstruction conjecture''':一个<math> n </math>阶图是否能够由其所有<math>n-1</math>阶导出子图唯一确定?
 
一个尚未解决的与子图相关的猜想,'''重构猜想 Reconstruction conjecture''':一个<math> n </math>阶图是否能够由其所有<math>n-1</math>阶导出子图唯一确定?
 +
    
=== 染色 ===
 
=== 染色 ===
第190行: 第191行:       −
对于严格组合 compositional的约束框架,图的统一是充分可满足性和组合函数。 著名的应用包括'''定理自动证明 automatic theorem proving'''和语言结构的精化建模。
+
对于严格组合 compositional的约束框架,图的统一是充分可满足性和组合函数。 著名的应用包括定理自动证明 automatic theorem proving和语言结构的精化建模。
 +
 
    
=== 路径问题 ===
 
=== 路径问题 ===
第210行: 第212行:  
* 二分图及任意图上的最大匹配
 
* 二分图及任意图上的最大匹配
 
* 带权二分图的最大权匹配
 
* 带权二分图的最大权匹配
 +
    
=== 可见性问题 ===
 
=== 可见性问题 ===
第216行: 第219行:     
=== 覆盖问题 ===
 
=== 覆盖问题 ===
图的'''覆盖问题 Covering problems'''可能涉及到顶点/子图子集上的各种'''集合覆盖问题 set cover problem(SCP)'''
+
图的覆盖问题 Covering problems可能涉及到顶点/子图子集上的各种集合覆盖问题 set cover problem(SCP)。
* '''控制集 Dominating set'''问题是集合覆盖问题的特例,其中集是封闭邻域 neighborhoods
+
* 控制集 Dominating set问题是集合覆盖问题的特例,其中集是封闭邻域 neighborhoods
* '''顶点覆盖问题 Vertex cover problem'''是集合覆盖问题的特例
+
* 顶点覆盖问题 Vertex cover problem是集合覆盖问题的特例
* 初始集合覆盖问题,也称'''碰集 hitting set''',可以描述为'''超图 hypergraph'''中的顶点覆盖
+
* 初始集合覆盖问题,也称碰集 hitting set,可以描述为超图 hypergraph中的顶点覆盖
      第231行: 第234行:  
*边染色 Edge coloring
 
*边染色 Edge coloring
 
*图因子分解 Graph factorization
 
*图因子分解 Graph factorization
 +
    
===图形类===
 
===图形类===
763

个编辑

导航菜单