algorithm - 图中的最大边数

Question

我正在阅读有关在以下位置表示图形的信息。

http://www.brpreiss.com/books/opus4/html/page532.html

考虑一个有向图 G = (V,E)。由于 E 是 V x V 的子集或等于 V x V，因此图 G 最多包含 V^2 条边。对于给定的一组顶点，有 2^(V^2) 种可能的边组。因此，在设计图形表示方案时，主要关注的是找到一种合适的方式来表示边的集合。

我的问题是作者所说的“对于给定的一组顶点，可能有 2^(V^2) 组边”是什么意思？

例如，如果我们有 2 个顶点，那么我可以理解我们可以有 4 个边，即 {(a,a), (a,b), (b,a), (b,b) }但是我们如何获得 16 组可能的边。

感谢您的宝贵时间。

Answer 1

按照我的理解，他们说有 2^(V^2) 种方法可以构建具有 V 个顶点的有向图。由于总共有 V^2 条可能的边，并且每条可能的边在给定图中可以存在或不存在，这就是组合数。

在具有 2 个顶点并使用您的符号的示例中，16 个可能图形的边集是:

{ (a,a), (a,b), (b,a), (b,b) }
{ (a,a), (a,b), (b,a) }
{ (a,a), (a,b), (b,b) }
{ (a,a), (a,b) }
{ (a,a), (b,a), (b,b) }
{ (a,a), (b,a) }
{ (a,a), (b,b) }
{ (a,a) }
{ (a,b), (b,a), (b,b) }
{ (a,b), (b,a) }
{ (a,b), (b,b) }
{ (a,b) }
{ (b,a), (b,b) }
{ (b,a) }
{ (b,b) }
{ }