algorithm - 计算所有未形成禁止组合的子集

Question

我正在尝试用组合数学和图形来解决相当复杂的问题:

给定一个无向图，有n(n<=30)个节点和m(m< =50) 条边，每条边以a, b 的格式表示，其中a, b 都是图中的节点。

现在在这个图中我们必须计算节点的所有子集，显然有 2^n 个子集，但是我们在每个子集组合中都有一个限制，我们不应该有节点的三元组正在形成三角形的，我们不应该计算这些组合，换句话说，我们不应该计算包含具有长度为 3 的循环的节点的组合。

示例

n=3, m=3 我们有图 2-1, 3-1, 2-3 ，这个例子的答案是 7，我们可以形成的所有子集是:{}、{1}、{2}、{3}、{1,2}、{1,3}、 {2,3}，但是我们不应该计算子集 {1,2,3}，因为节点 1,2,3 正在形成三角形，换句话说，它们正在形成长度为 3 的循环

我尝试过的

我用正确的答案解决了这个问题，但它只在 n<=22 时有效，实际上我正在用 O(2^n) 生成所有可能的位掩码复杂性，但这种复杂性对于 n=30 来说太大了。我应该向我的算法添加什么以使其适用于所有测试用例？

Answer 1

有效解决这个问题的关键当然是只计算有多少个有三角形或没有三角形的子集，而不是实际生成任何子集来检查它们。

如您所说，具有 n 个节点的图有 2ⁿ 个可能的子集，每个可能的 n 大小位模式代表这些子集之一。请注意，我们不需要生成这些子集来计算有多少。

现在，想象一下，在检查完边后，我们找到了一个三角形。 2ⁿ 子集中有多少包含构成这个三角形的所有三个节点？三个相应位始终设置为 111 的所有 n 大小的位模式表示包含这三个节点的所有子集。这些位模式的数量显然是2^n-3。所以如果我们有 n 个节点和 1 个三角形，我们有 2ⁿ-2^n-3 个不包含三角形的子集。

如果有 2 个或更多三角形，问题是:我们应该从总数中减去多少个额外的子集？假设有 2 个三角形，并且它们不共享任何节点。那么一个三角形排除了 2^n-3 个子集，包含第二个三角形但不包含第一个(我们不想两次排除任何子集)的子集的数量是 7/8 × 2 ^n-3，因为它们对应于所有 n 大小的位模式，其中 3 位始终设置为 111，另外 3 位设置为 000、001、010、011、100、101、110，但是不是 111。所以如果我们有 n 个节点和 2 个独立的三角形，我们有 2ⁿ-2^n-3-7/8×2^n-3 不包含三角形的子集。

如果有第三个三角形不与前两个三角形共享任何节点，我们排除额外的 49/64×2^n-3 子集，因为有两组 3不得为 111 的位，因此有 7/8 × 7/8 × 2^n-3。

那么如果两个三角形共享一个节点会怎样呢？第二个三角形对应的 3 位一定是 111，而第一个三角形对应的 3 位一定不是 111，所以算 00111、01111、10111 而不是 11111。所以得到 2ⁿ- 2^n-3-3/4×2^n-3。

如果两个三角形共享两个节点，我们计算 0111 而不是 1111，所以得到 2ⁿ-2^n-3-1/2×2 ^n-3。

如您所见，通过找出有多少个三角形以及它们共享多少个节点，您可以计算出有多少个没有三角形的子集，而无需实际生成子集并检查它们是否存在三角形。

---

例子

我们有 50 个节点和 30 条边。检查边缘后，我们发现这些三角形:

A.        B.        C.  D.        E.        G.  H.

  N         N         N   N         N         N - N
 / \       / \       / \ / \       / \       / \ /
N - N     N - N     N - N - N     N - N     N - N
                                   \ /       \ /
                                    N         N

                                  F.        I.

子集总数为2⁵⁰。
包含三角形A的子集数为2⁴⁷。
包含 B 但不包含 A 的子集数为 7/8 × 2⁴⁷。
包含 C 但不包含 A 或 B 的子集数为 7/8 × 7/8 × 2⁴⁷。
包含 D 但不包含 A 到 C 的子集数为 7/8 × 7/8 × 3/4 × 2⁴⁷。
包含E但不包含A到D的子集数量为7/8 × 7/8 × 25/32 × 2⁴⁷。
包含F但不包含A到E的子集数为7/8 × 7/8 × 25/32 × 1/2 × 2⁴⁷。
包含G但不包含A到F的子集数为7/8 × 7/8 × 25/32 × 3/16 × 2⁴⁷。
包含H但不包含A到G的子集数量为7/8 × 7/8 × 25/32 × 3/16 × 1/2 × 2⁴⁷。
包含 I 但不包含 A 到 H 的子集数为 7/8 × 7/8 × 25/32 × 3/16 × 1/2 × 1/2 × 2⁴⁷。

2⁵⁰ - (1 + 7/8 + 49/64 + 147/256 + 1225/2048 + 1225/4096 + 3675/32768 + 3675/65536 + 3675/131072) × 2 ⁴⁷ = 1,125,899,906,842,624 - 606,343,081,754,624 = 519,556,825,088,000