763
个编辑
更改
跳到导航
跳到搜索
第164行：
第164行： − + − 类似地，有些问题要求寻找符合某些条件的最大'''导出子图 induced subgraphs'''，如：+ − + 第175行：
第175行： −
→子图相关问题
一类相关的常见问题要求在给定图中寻找符合某些条件的最大子图，其中有很多是NP完全的，如：
一类相关的常见问题要求在给定图中寻找符合某些条件的最大子图，其中有很多是NP完全的，如：
* '''分团问题 clique problem'''：在给定图中寻找最大的团（NP完全）。
* 分团问题 clique problem：在给定图中寻找最大的团（NP完全）。
类似地，有些问题要求寻找符合某些条件的最大导出子图 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>阶导出子图唯一确定？
=== 染色 ===
=== 染色 ===