algorithm - 图的最大子图数

Question

任何人都可以告诉我一个图的最大子图有多少个。如果你能给我一些关于如何计算的答案的解释，那就太好了。谢谢

Answer 1

这听起来像是家庭作业，所以这里有一些提示:子图的定义是它由图节点的子集以及原始图中选定节点之间的边的子集组成. (编辑:我原来的回复是错误的，因为“的一个子集”被遗漏了。)节点”，这与“给定一个集合 V，V 有多少个子集”本质上是同一个问题？ 编辑:因此，作为@ andrew cooke指出，虽然表达有多少可能的节点子集很简单，但每个节点子集可能的边子集的数量取决于图的结构，因此没有简单的公式。