Java Program to Find the Largest Clique in a Planar Graph

图的独立集的一个先决条件是顶点集，其中没有两个顶点是相邻的。仅仅从定义上看，它是一个团的反面，所以理解图的补集对于继续前进至关重要。本质上，平面网络的概念并不特别重要，但它是一个有用的概念。为了回答上面的问题，我们将利用这三个概念。

在提供的平面图中，我们必须识别最大的团。任何两个顶点都相邻的顶点子集都称为平面图的团；换句话说，顶点集合形成一个完全图，它是给定平面图的子图。被称为最大团的是最大的顶点集合，当它们组合在一起时形成给定图的完全子图，并且不能再添加任何顶点。如果我们熟悉独立集的概念，就有可能发现团和独立集之间的含糊不清的联系。

因此，正如将在下面讨论的，关系和区别是并存的。

1. 无向图或平面图的团是顶点集合，其中每对唯一的顶点都彼此相邻。
2. 如果一组顶点没有两个相邻，则称该组顶点是独立的。
3. 对于两个集合，最大值的概念是相同的。

从图的独立集和团集的定义可以明显看出，它们之间存在某种互补关系。根据定义，最大独立集是在实际图中彼此不相邻的最大顶点集。如果我们补全提供的图，则情况就是如此，因为我们正在确定补图中独立集。因此，给定图中的最大团是所提供图的补图的最大独立集。

方法：贪婪算法

提供的代码使用贪婪算法和图着色来查找最大独立集（MIS）或补图中的最大团。邻接表和邻接矩阵都用于表示图。该算法使用贪婪移除技术（remove_all 和 can_remove 方法），通过迭代移除不允许作为独立集一部分的顶点。然后，为了优化其大小，它会进行局部更改（Util2）来细化独立集。该方法通过以下方式间接解决了最大团问题：补图中的一个团对应于原始图中的一个独立集。图论思想，如邻接表和着色，用于此方法，以有效地提取最大的独立集。

因此，在给定图的补图中，该图的最大团可以被视为最大的独立集。即使它们是 NP 难问题，也可以使用许多确定给定平面图最大独立集的现有方法来找到团。只需要对提供的现有方法进行少量修改，即输入图的补图。以下是确定上面图中哪个团是最大的。（带有绿色边的子图就是那个。）

下面实现了确定图的补图的独立集（间接就是图的团）的概念。

算法

步骤 1：读取顶点数 n。

步骤 2：创建显示图的邻接矩阵。

步骤 3：为了更有效的遍历，将邻接矩阵转换为邻接表。

步骤 4：为了跟踪发现的最小独立集，将 minSetSize 设置为 n。

步骤 5：最佳独立集应存储在名为 bestSet 的空列表中。

步骤 6：每个顶点都应被假定为独立集的一部分（从 0 到 n-1）。

步骤 7：创建一个大小为 n 的 数组 color，初始值为 1（表示所有节点都可以立即访问）。

步骤 8：设置 color[start] = 0，表示当前顶点属于独立集。

步骤 9：多次验证每个顶点。

步骤 10：如果一个顶点可以被删除，即它的所有邻居仍然可以访问，则设置 color[i] = 0。

步骤 11：重复上述过程，直到没有更多顶点可以删除为止。

步骤 12：将 color[i] == 0 的所有顶点存储在 independentSet 中。

步骤 13：如果 minSetSize 大于现有的独立集，则更新 bestSet。

步骤 14：使用每个顶点作为起点并重复该过程。

步骤 15：跟踪我们可以找到的最大独立集。

实施

输出

 
The number of vertices in the graph is taken as 5
The maximal independent set's size to be find is 6
Searching for the set
Independent set of size 4 found
1 2 3 4   

解释

从输出可以看出，有五个顶点被选中。然后找到大小为四的独立集，并返回构成原始图中独立集的顶点集。由于我们之前已经讨论过补图的独立集就是原始图中的团，因此这些集就是原始图中的团。

复杂度分析

上述代码的时间复杂度为 O(N³)，空间复杂度为 O(N²)，其中“N”表示图的顶点数。