graph-theory - 有多少个图有 10 个节点和 2 条边

Question

准备考试 我对以下练习有疑问：
存在多少个正好有 10 个节点和 2 条边的无向图？

我的方法：
我需要 3 或 4 个节点来绘制 2 条边。

所以我有

10 选择 3 = 120
和 10 选择 4 = 210
= 330 种可能性？！

这是正确的还是我错过了什么？

编辑：允许孤立节点

Answer 1

我看到它的方式可能完全偏离基础，您有两个选择：

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) 的情况。

Answer 2

你不远了。

案例 #1：3 个节点连接在一起。选择 3 个节点后，您必须选择哪个节点位于中间

案例 #2：连接了 2 对不同的节点。选择 4 个节点后，您仍然必须选择它们的连接方式。

不过，更简单的方法是计算可能边的总数：10 选择 2。然后，在这些可能性中，选择其中的两个。