图的子图最大数量

Question

有没有人能告诉我一个图可能有多少个子图？ 如果你能给我一些关于如何计算的解释，那就太好了。 谢谢。

- Abdul Samad

---

我可以问一下这与算法有什么关系吗？这只是一点数学。 - harold

@harold 我不同意，这里可能有一个递归算法 :) - nicolaskruchten

@nicolaskruchten，我不同意你的不同意。根据OP的陈述，他正在寻找完全图中有效子图的数量（因为与所有其他具有相同节点数的图相比，该数量最大），而那里没有算法。 - harold

@harold，我想知道在您的观点中，哪种过程和/或公式可以同时回答这个问题而不被视为“算法” :) - nicolaskruchten

@nicolaskruchten 任何公式，公式不是算法，它们比算法更抽象，不定义如何评估它们。 - harold

我认为这应该属于http://math.stackexchange.com/。 - ypercubeᵀᴹ

Answer 1

这听起来像是一道作业题，以下是一些提示：子图的定义是由原图中选定的节点子集和连接这些节点的边子集组成。（编辑：我的原始回复有误，缺少了“节点子集”）换句话说，“有多少个子图”与“我们以多少种方式选择节点的子集”具有相同的答案，这本质上是“给定一个集合V，有多少个V的子集”的问题。因此，正如@andrew cooke所指出的那样，虽然可以简单地表达出可能的节点子集数量，但每个节点子集的可能边子集数量取决于图的结构，因此没有简单的公式可用于计算。

- Aasmund Eldhuset

---

@nicolaskruchten：他没有说这些都是子图。你在说什么？ - Karoly Horvath

@nicolaskruchten：你的观察是正确的，但正如yi_H所说，那不是我说的。我说要选择一个子集的_nodes_，然后选择_selected subset_中两个端点都在其中的所有边。 - Aasmund Eldhuset

@nicolaskruchten：这确实是我的错误。我已经纠正了它，谢谢。 - Aasmund Eldhuset

你的连接仍然不正确，因为你在暗示（我认为）子图完全由节点集定义。但是你也可以（如nicoalskrutchen所说）选择不同的边子集。这也意味着没有简单的组合数学解答（那是一个词吗？没有涉及图的大小的简单算术表达式）（除非你考虑，比如，完全图的所有完全子图）。 - andrew cooke

@andrew cooke：啊，我今天显然还没醒过来——你完全正确。我再次编辑了答案（现在基本上变得毫无用处……） - Aasmund Eldhuset

Answer 2

假设边的数量为E，顶点的数量为V。 子图的数量： 2^V + C(E,1)*2^(V-2) + C(E,2)*2^(剩余顶点数) + .... 一直持续到所有边都被覆盖。

- spd_25