algorithm - 我应该使用多少个 bool 变量来表示一个图形？

Question

如果我被要求确定图 G 所需的 bool 变量的数量。如果我使用 bool 公式来表示 G，我应该如何计算变量的数量？

Answer 1

这取决于您选择如何表示图表。有两种常见的图表示:邻接矩阵和邻接表。

• 邻接矩阵

  如果一个图有 V 个顶点，那么邻接矩阵表示本质上是一个大小为 V x V 的二维数组，以便捕获所有可能的边组合。以下面的无向图为例，由于顶点 A 具有与顶点 B、C 和 D 关联的边，因此 matrix[A][B]、matrix[A][C] 和 matrix[A][D] 中存在值 1 或真值。虽然顶点 A 没有到它自己和顶点 E 的边，但是对于那些缺少边的变量，我们仍然有由 matrix[A][A] 和 matrix[A][E] 中的 0 或 false 值表示的变量。因此，使用的空间/变量的数量总是。

• 邻接表

  另一方面，邻接表是列表的数组。如果一个图有 V 个顶点，则数组的大小为 V。并且此数组中的每个顶点都由一个列表表示，该列表的大小取决于该顶点具有的边数。例如，这是使用邻接表表示上图的方式，

  A -> B, C, D
  B -> A, D, E
  C -> A, D
  D -> A, B, C, D, E
  E -> B, D
  

  请注意与邻接矩阵的不同之处在于，我们不使用任何边缺失的空间。唯一使用的空间或变量用于存在的边缘。然而，这不能简单地说为使用的“ bool 变量”的数量，因为需要不同类型的数据结构来表示两个顶点之间的边。也许是一个整数或一个字符串变量来表示顶点的 id，因此每个列表都将包含这些顶点 id。这些变量的数量将由 E 表示，即图中的边数。并且数组的每个索引都将映射到一个唯一的顶点 ID。数组中的列表数始终为 V，即图中的顶点数。