763
个编辑
更改
跳到导航
跳到搜索
第143行：
第143行： + − + + + + + − 第170行：
第174行： + − 约束建模理论关注由'''偏序 partial order'''关联的有向图族。在这些应用中，图是按特异性排序的，这意味着更具体并因此包含更多信息的约束图被更一般的图所包含。 图之间的运算包括计算两个图（如果有的话）之间包容关系的方向，以及计算图的统一性。两个参数图的统一定义为与输入一致（即包含所有信息）的最一般的图（或其计算）（如果存在的话）；有效的统一算法是已知的。 + 第185行：
第190行： + + − 第196行：
第202行： + − * '''博物馆保安问题 Museum guard problem''' − 第207行：
第212行： + − 分解 Decomposition，被定义为对图的边集进行划分（在划分的每个部分的边上有必要的多个顶点），有各类问题。通常，需要将图分解为与给定图同构的子图; 例如，将一个'''完全图 complete graph'''分解为'''哈密顿圈 Hamiltonian cycle'''。其他问题指定一个图族，其中一个给定的图应该被分解，例如，一个圈族，或将一个完全图<math>K_n</math>分解为分别分别有<math>1,2,3,...,n-1</math>条边的<math>n-1</math>棵指定树。 第215行：
第220行： + −
→图论问题
=== 图枚举 ===
=== 图枚举 ===
图形枚举 graph enumeration是满足特定条件的图的计数问题，相关文献很多。
图形枚举 graph enumeration是满足特定条件的图的计数问题，相关文献很多。
=== 子图相关问题 ===
=== 子图相关问题 ===
'''子图同构问题 subgraph isomorphism problem'''：给定两个图<math> G </math>和<math> H </math>，问<math> G </math>中是否存在一个子图与<math> H </math>同构。这是一个NP完全问题。
'''子图同构问题 subgraph isomorphism problem'''：给定两个图<math> G </math>和<math> H </math>，问<math> G </math>中是否存在一个子图与<math> H </math>同构。这是一个NP完全问题。
* 哈密顿回路问题可视为一个子图同构问题，即给定一个<math> n </math>个顶点的图，问是否存在一个子图与具有<math> n </math>个顶点的圈同构。
* 哈密顿回路问题可视为一个子图同构问题，即给定一个<math> n </math>个顶点的图，问是否存在一个子图与具有<math> n </math>个顶点的圈同构。
一类相关的常见问题要求在给定图中寻找符合某些条件的最大子图，其中有很多是NP完全的，如：
一类相关的常见问题要求在给定图中寻找符合某些条件的最大子图，其中有很多是NP完全的，如：
* '''分团问题 clique problem'''：在给定图中寻找最大的团（NP完全）。
* '''分团问题 clique problem'''：在给定图中寻找最大的团（NP完全）。
类似地，有些问题要求寻找符合某些条件的最大'''导出子图 induced subgraphs'''，如：
类似地，有些问题要求寻找符合某些条件的最大'''导出子图 induced subgraphs'''，如：
* 最大'''独立集问题 independent set problem'''：在给定图中寻找最大的无边的导出子图，亦即'''独立集 independent set'''（NP完全）。
* 最大'''独立集问题 independent set problem'''：在给定图中寻找最大的无边的导出子图，亦即'''独立集 independent set'''（NP完全）。
平面图判定：判定给定的图是否是平面图
平面图判定：判定给定的图是否是平面图
一个尚未解决的与子图相关的猜想，'''重构猜想 Reconstruction conjecture'''：一个<math> n </math>阶图是否能够由其所有<math>n-1</math>阶导出子图唯一确定？
一个尚未解决的与子图相关的猜想，'''重构猜想 Reconstruction conjecture'''：一个<math> n </math>阶图是否能够由其所有<math>n-1</math>阶导出子图唯一确定？
=== 染色 ===
=== 染色 ===
图论中的许多问题和定理都与图的着色有关。通常，染色需使任意两个相邻顶点不同色或任意邻接边不同色。有关图染色的著名结果和猜想如下:
图论中的许多问题和定理都与图的着色有关。通常，染色需使任意两个相邻顶点不同色或任意邻接边不同色。有关图染色的著名结果和猜想如下:
* '''四色问题 Four-color theorem'''
* '''四色问题 Four-color theorem'''
=== 包容与统一 ===
=== 包容与统一 ===
约束建模理论关注由'''偏序 partial order'''关联的有向图族。在这些应用中，图是按特异性排序的，这意味着更具体并因此包含更多信息的约束图被更一般的图所包含。 图之间的运算包括计算两个图（如果有的话）之间包容关系的方向，以及计算图的统一性。两个参数图的统一定义为与输入一致（即包含所有信息）的最一般的图（或其计算）（如果存在的话）；有效的统一算法是已知的。
对于严格组合 compositional的约束框架，图的统一是充分可满足性和组合函数。 著名的应用包括'''定理自动证明 automatic theorem proving'''和语言结构的精化建模。
对于严格组合 compositional的约束框架，图的统一是充分可满足性和组合函数。 著名的应用包括'''定理自动证明 automatic theorem proving'''和语言结构的精化建模。
=== 路径问题 ===
=== 路径问题 ===
* 三间小屋问题 Three-cottage problem
* 三间小屋问题 Three-cottage problem
* 旅行商问题 Traveling salesman problem（NP难）
* 旅行商问题 Traveling salesman problem（NP难）
=== 网络流与匹配 ===
=== 网络流与匹配 ===
在与网络流 network flow概念有关的应用中出现了许多问题，例如：
在与网络流 network flow概念有关的应用中出现了许多问题，例如：
* '''最大流最小割定理 Max flow min cut theorem'''
* '''最大流最小割定理 Max flow min cut theorem'''
* 最小费用最大流问题
* 最小费用最大流问题
=== 可见性问题 ===
=== 可见性问题 ===
* '''博物馆保安问题 Museum guard problem'''
=== 覆盖问题 ===
=== 覆盖问题 ===
图的'''覆盖问题 Covering problems'''可能涉及到顶点/子图子集上的各种'''集合覆盖问题 set cover problem(SCP)'''。
图的'''覆盖问题 Covering problems'''可能涉及到顶点/子图子集上的各种'''集合覆盖问题 set cover problem(SCP)'''。
* '''控制集 Dominating set'''问题是集合覆盖问题的特例，其中集是封闭邻域 neighborhoods
* '''控制集 Dominating set'''问题是集合覆盖问题的特例，其中集是封闭邻域 neighborhoods
=== 分解问题 ===
=== 分解问题 ===
分解 Decomposition，被定义为对图的边集进行划分（在划分的每个部分的边上有必要的多个顶点），有各类问题。通常，需要将图分解为与给定图同构的子图; 例如，将一个'''完全图 complete graph'''分解为'''哈密顿圈 Hamiltonian cycle'''。其他问题指定一个图族，其中一个给定的图应该被分解，例如，一个圈族，或将一个完全图<math>K_n</math>分解为分别分别有<math>1,2,3,...,n-1</math>条边的<math>n-1</math>棵指定树。
已经研究的一些具体分解问题包括：
已经研究的一些具体分解问题包括：
* '''边染色 Edge coloring'''
* '''边染色 Edge coloring'''
* '''图因子分解 Graph factorization'''
* '''图因子分解 Graph factorization'''
===图形类===
===图形类===
许多问题涉及到对各类图的成员进行刻画。举例如下：
许多问题涉及到对各类图的成员进行刻画。举例如下：
* 枚举某类的成员
* 枚举某类的成员