查找具有由集合定义的顶点的图中的边数的算法

Question

我有一个这样定义的图表：

有一组数字{1,2,3,4,5}

图中的每个顶点都可以由原集合中的任意3个数组合而成，不重复。因此，例如，一个有效的顶点将是 {1,2,3}。

任何两个恰好相差 1 个数的顶点之间存在一条边。因此，{1,2,3} 和 {1,2,4} 之间会有一条边，但 {1,2,3} 和 {2,4,5} 之间没有边。

如何编写算法来查找此图中的边数？我在我的算法中对一些边缘进行了两次计数。我不确定解决这个问题的正确方法是什么。我知道有 5 个选择 3 个顶点数。

Answer 1

C(5,3)只需要10个，所以计算边不是很难。

更简单的方法：获取任意组合并找到边数：

combination
1  2  3 
subcombinations:
1  2         paired 1 2 4; 1 2 5
1     3      paired 1 3 4; 1 3 5
   2  3      paired 2 3 4; 2 3 5

所以我们从这个组合顶点有六个边。但从对称性来看，每个顶点都有 6 条边。这样的图称为6正则图。

所以边的总数是（除以 2 以消除每条边的重复计数）

10 * 6 / 2 = 30

如果您确实需要 C(n,k) 组合的通用解决方案：

p = C(n,k) = n!/(k!*(n-k!)) 
NumEdges = p*k*(n-k)/2

Algorithm to find the number of edges in a graph with vertices defined by a set