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