准备考试 我对以下练习有疑问：
存在多少个正好有 10 个节点和 2 条边的无向图？
我的方法：
我需要 3 或 4 个节点来绘制 2 条边。
所以我有
10 选择 3 = 120
和 10 选择 4 = 210
= 330 种可能性？！
这是正确的还是我错过了什么？
编辑：允许孤立节点
问问题
319 次
2 回答
0
我看到它的方式可能完全偏离基础，您有两个选择：
A---B
|
C
和
A---B
C---D
在这两种情况下，都有 90A---B种组合 (10 * 9)。
在第一种情况下，C 有 8 个选项，它可以连接到 A 或 B，所以你有10 * 9 * 8 * 2 = 1440图表。
在第二种情况下，C 有 8 个选项，D 有 7 个选项，所以你有10 * 9 * 8 * 7 = 5040图表。这些总和是 6480 个图。
这不处理两条边都连接相同节点 ( A==B) 的情况。
于 2012-07-30T15:43:42.977 回答
0
你不远了。
案例 #1：3 个节点连接在一起。选择 3 个节点后，您必须选择哪个节点位于中间
案例 #2：连接了 2 对不同的节点。选择 4 个节点后，您仍然必须选择它们的连接方式。
不过，更简单的方法是计算可能边的总数：10 选择 2。然后，在这些可能性中，选择其中的两个。
于 2012-07-30T16:02:50.030 回答