准备考试 我对以下练习有疑问:
存在多少个正好有 10 个节点和 2 条边的无向图?
我的方法:
我需要 3 或 4 个节点来绘制 2 条边。
所以我有
10 选择 3 = 120
和 10 选择 4 = 210
= 330 种可能性?!
这是正确的还是我错过了什么?
编辑:允许孤立节点
准备考试 我对以下练习有疑问:
存在多少个正好有 10 个节点和 2 条边的无向图?
我的方法:
我需要 3 或 4 个节点来绘制 2 条边。
所以我有
10 选择 3 = 120
和 10 选择 4 = 210
= 330 种可能性?!
这是正确的还是我错过了什么?
编辑:允许孤立节点
我看到它的方式可能完全偏离基础,您有两个选择:
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
) 的情况。
你不远了。
案例 #1:3 个节点连接在一起。选择 3 个节点后,您必须选择哪个节点位于中间
案例 #2:连接了 2 对不同的节点。选择 4 个节点后,您仍然必须选择它们的连接方式。
不过,更简单的方法是计算可能边的总数:10 选择 2。然后,在这些可能性中,选择其中的两个。