三个顶点上有多少个无向图？

Question

无向图包含 3 个顶点。可以组成多少个无向图？我尝试了组合公式，但答案是错误的。

Answer 1

My answer 8 Graphs : 对于无向图，任意两个节点不超过 1 个边。具有 N 个顶点的图最多可以有 nC2 条边。 3C2 是 (3!)/((2!)*(3-2)!) => 3。因此，您可以计算具有 0 条边、1 条边、2 条边和 3 条边的图的数量。

最多 N 个节点的边数 = N*(N-1)/2 来自 nC2 并且对于每个边缘你可以选择在你的图表中选择它或者不选择它并且每个选项你都会得到一个独特的图表并且它给出了公式：2 ^（N *（N-1）/ 2）可能的图表。

如果节点名为 a、b 和 c，则

所有断开连接的节点：0 条边

a  b  c

= 1 个图形

只有 2 个节点连接：1 条边

a--b  c
b--c  a
c--a  b

=3张图

连接的所有 3 个节点：2 条边

a--b--c (c--b--a will be same)
a--c--b ( b--c--a will be same)
b--a--c (c--a--b will be same)

=3个节点

连接的所有 3 个节点：3 条边

a--b--c--a

= 1 个图形

总共 8 个图表。 另一种看待它的方式是，对于每条边，您有 2 个选项，要么有它，要么没有它，方法是使 2 上升到次方3（2 个选择和 3 个边）使 8 作为答案。

对于有向图，我们将有更多的情况需要考虑，我在下面尝试找到有向图的图的数量（注意下面是针对这种情况我们在 2 个节点之间没有超过 1 个边缘，如果我们在 2 个节点之间有超过 1 个边缘，那么答案会有所不同）

0 边

a b c = 1 图

1条边

a-->b c
a<--b c
b-->c a
b<--c a
c-->a b
c<--a b

= 6 个图表

2条边

a-->b-->c
a-->b<--c
a<--b-->c
a<--b<--c
b-->a-->c
b-->a<--c
b<--a-->c
b<--a<--c
a-->c-->b
a-->c<--b
a<--c-->b
a<--c<--b

= 12 个图表

3 条边

a-->b-->c-->a
a-->b-->c<--a
a-->b<--c-->a
a-->b<--c<--a
a<--b-->c-->a
a<--b-->c<--a
a<--b<--c-->a
a<--b<--c<--a

= 8 个图表

总计 = 1 + 6 + 12 + 8 = 27 张图

Answer 2

具有 N 个顶点的图最多可以有 C(N,2) = (N choose 2) = N*(N-1)/2 条边（如果不允许循环）。

因此可能的图形总数为 2^(N*(N-1)/2)。

Answer 3

您应该首先决定是否要计算 已标记 或 未标记 对象。假设您的图形很简单，即：没有循环或多条边。

如果您计算标记的对象，那么您计算的是对角线为 0 的对称 0-1 矩阵（即图的邻接矩阵）。有 2^(1+2...+n-1)=2^(n(n-1)/2) 个这样的矩阵，因此，有相同数量的无向简单图。对于 n=3，这会为您提供 2^3=8 个图表。

如果您计算的是未标记的对象，那么您计算的是图的数量直至图同构。这是一个更难的问题。 Online Encyclopedia of Integer Sequences (OEIS) 网站的一些计算数据可用于更大的 n：https://oeis.org/A000088。从这个网站我们推断在 3 个顶点上有 4 个未标记的图（实际上：空图、边、樱桃和三角形）。

Answer 4

对于有向图的情况，图的个数难道不是按照与无向图的情况相同的逻辑由等式2^(n^2)给出的吗（假设允许自循环）？特别是，所有顶点都可以有 n 个出边（同样，包括自环）。因此 n ^ 2（或 n * n）表示图形可能的最大边数。由于我们为每条边选择是否包含它，因此图的最大数量由 2 ^ (n ^ 2) 给出。谁能证实这一点？

三个顶点上有多少个无向图？

How many undirected graphs are there on 3 vertices?

algorithm

combinations

analysis

combinatorics