图中的团

---

最近，基于图的表示在模拟现实世界数据方面获得了极大的普及。团是图论中的一个关键问题，用于解决许多数学问题和创建图形。团在计算机科学领域得到了广泛的研究，其中团问题评估图中是否存在一定大小的团，这是一个 NP 完全问题。然而，尽管存在所有复杂性，但人们一直在研究几种查找团的技术。

什么是团？

在所有无向图 G = (N, E) 中，团是“节点的子集”，使得所有成对的不同节点都是相邻的。指定图的完全子图是无向图中的团。完全子图具有所有与图中所有其他顶点连接的顶点。独立集是在补图中团的对立面，因为每个团都类似于一个独立集。在考虑图的所有顶点的情况下，找到图的最小团被称为团覆盖问题。

最大团是指不能通过添加另一个相邻节点进一步扩大的团。

在图中，最大团是指没有其他团具有更多顶点的团。此外，具有最大团的图中节点的总数称为团数。

因此，最大团也是最大团（但反之不一定成立）。

什么是 K-团？

大小为 k 的团称为“k-团”（但是，这个词有时也用于指代距离不超过 k 的最大顶点组）。0-团表示空集（没有顶点的集合），“1-团”表示节点，2-团表示边，“3-循环”由 3-团表示。

关于团有哪些定理？

根据 Ramsey 定理，任何图或其补图中都存在至少具有对数数量节点的团。

“Turán 定理”限制了稠密图中团的大小。如果图包含足够的边，则存在一个巨大的团。例如，任何具有 m 个节点且大于 [m/2][m/2] 条边的图中都必须存在一个三顶点团。

Moon 和 Moser 证明，在具有 3n 个节点的图中，最多只能有 3n3 个最大团。Moon-Moser 图满足此限制。

基于团的图分类

可以使用它们的团来描述或分类各种主要类型的图 -

图	特征
“聚类图”	团是其连通分量的图
“块图”	团是其双连通分量的图。
“分裂图”	图中每条边的至少一个顶点都属于团。
“无三角形图”	除了其边和顶点之外，没有其他团的图
“线图”	图的边可以用“边不相交的团”覆盖，这意味着覆盖中的每个顶点都恰好是两个团的成员。

团问题

团问题是一个计算任务，您必须在其中找到图中的团。它包括许多基于必须识别团的位置以及必须获得关于它们的哪种类型的信息的公式。

识别“最大团”、为加权图找到“最大权重团”、识别最大团以及确定任何图是否包含大于某个大小的团构成了构建团问题的核心方法。

解决大多数团问题都是具有挑战性的。团选择问题是“Karp 的 21 个 NP 完全问题”之一。找到最大的团在具有集合参数且难以量化的情况下很复杂。此外，由于存在许多具有指数级最大团的图，因此识别每个最大团可能需要指数级时间。

识别单个最大团

一个简单的贪婪算法可以确定最大的团。通过迭代图的所有顶点，从任何团（只有一个节点或可能是整个集合）开始，我们一次添加一个节点来增长当前团。对于此迭代检查的每个顶点，如果特定顶点与每个其他顶点都相邻，则将顶点添加到团中，否则忽略它。该算法在时间上是线性的。由于最大团很容易发现，并且它们可能具有最小的大小，因此人们更多地关注寻找大团这个更困难的计算过程，而不是寻找单个最大团的难度。

使用“蛮力”算法，可以确定图是否包含“k-顶点团”并识别其中包含的每个这样的团。此方法检查每个具有 k 个节点的子图以查看它是否是团的一部分。在大的 O 表示法中，它需要 O(nkk2) 时间。这是因为存在 O(nk) 个子图需要检查，所有这些子图都有 O(k2) 条边需要验证。因此，当 k 是一个给定的常数时，问题在时间上是多项式的。当 k 没有固定值并且作为问题输入的一部分发生变化时，时间变得呈指数级。

固定大小的团

识别所有最大团

“Bron-Kerbosch”方法用于在每个团的多项式时间内以及最坏情况下的最优时间内识别每个最大团。根据 Moon 和 Moser，每个 n-顶点网络最多可以有 3n3 个最大团，并且“Bron-Kerbosch”方法（通过一种关键方法减少每个阶段执行的递归调用次数）的最坏情况执行时间为 O(3n3)，这与该限制相匹配。

团的应用有哪些？

假设一个在线社区，其中图的节点表示人员，边表示互惠的联系。术语“团”是指一群彼此都认识的人。可以使用用于检测团的算法来找到这些朋友网络。

Kuhl、Crippen 和 Friesen 在计算化学中使用团来表示两个分子键合的点。

为部分指定的布尔函数创建高效电路。

结论

团在图分析中至关重要，并且通常用于解决数学问题和创建图形。尽管“团问题是 NP 完全的”，但人们正在研究各种用于检测团的算法。K-团是指大小为 k 的团，并且存在关于团的各种定理。它们在计算机科学、生物信息学和图论中有多种应用。