7,129
个编辑
更改
跳到导航
跳到搜索
第159行：
第159行： − + − '''子图同构问题 subgraph isomorphism problem'''：给定两个图<math> G </math>和<math> H </math>，问<math> G </math>中是否存在一个子图与<math> H </math>同构。这是一个NP完全问题。+ 第176行：
第176行： −
→子图相关问题
=== 子图相关问题 ===
=== 子图相关问题 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>个顶点的圈同构。
一个尚未解决的与子图相关的猜想，'''重构猜想 Reconstruction conjecture'''：一个<math> n </math>阶图是否能够由其所有<math>n-1</math>阶导出子图唯一确定？
一个尚未解决的与子图相关的猜想，'''重构猜想 Reconstruction conjecture'''：一个<math> n </math>阶图是否能够由其所有<math>n-1</math>阶导出子图唯一确定？
=== 染色 Graph coloring===
=== 染色 Graph coloring===