图的分数团 首先，我们来理解“团”的基本概念。在图论中，一个“团”是指图中的一个顶点子集，其中任意两个不同的顶点都是相邻的（即由一条边直接连接）。一个团的“大小”就是它所包含的顶点数目。例如，一个三角形（三个顶点两两相连）就是一个大小为3的团。 现在，我们引入“分数团”的概念。分数团是团概念的一种推广，它允许顶点以“分数”的形式属于一个团。更具体地说，我们为图中的每个顶点分配一个非负的权值，要求对于图中的每一条边，其两个端点的权值之和不超过1。一个分数团就是满足这个条件的一组顶点权值分配。分数团的大小则定义为所有顶点权值的总和。 为了让你更直观地理解，我们来看一个简单的例子。考虑一个由三个顶点组成的路径图（P₃），顶点记为v₁, v₂, v₃，边是v₁-v₂和v₂-v₃。在这个图中，最大的团（传统意义上的团）大小是2（例如 {v₁, v₂} 或 {v₂, v₃}）。然而，我们可以构造一个分数团：给v₁和v₃分配权值1，给v₂分配权值0。这样，对于边v₁-v₂，权值和为1+0=1≤1；对于边v₂-v₃，权值和为0+1=1≤1。这个分数团的大小是1+0+1=2。我们还可以尝试另一种分配：给v₁, v₂, v₃都分配权值0.5。那么对于每条边，端点的权值和都是0.5+0.5=1≤1。这个分数团的大小是0.5+0.5+0.5=1.5。通过线性规划可以证明，对于这个图，最大的分数团大小就是2。 接下来，我们探讨分数团与线性规划的联系。寻找一个图的最大分数团大小，可以表述为一个线性规划问题。设变量xᵢ表示顶点i的权值，目标函数是最大化∑xᵢ，约束条件是对于每条边(i, j)，有xᵢ + xⱼ ≤ 1，并且所有xᵢ ≥ 0。这个线性规划问题的最优值就是图的最大分数团大小。值得注意的是，这个线性规划的对偶问题恰好对应于图的“分数边覆盖”问题。一个边覆盖是一个边集，使得每个顶点都至少与其中一条边关联。分数边覆盖则是给每条边分配一个非负权值，使得每个顶点的关联边权值之和至少为1。其目标是最小化所有边的权值之和。根据线性规划的对偶定理，最大分数团的大小等于最小分数边覆盖的大小。 然后，我们讨论分数团与图着色的关系，这涉及到“分数色数”的概念。图的色数是指对图进行正常顶点着色所需的最少颜色数，使得相邻顶点颜色不同。分数色数是色数概念的分数化推广。一个重要的结论是：一个图的分数团大小（记为ω_ f(G)）等于其分数色数（记为χ_ f(G)）。这个等式是图论中分数理论的基石之一，它揭示了团与着色在分数世界中的对偶关系。这与整数情况下的ω(G) ≤ χ(G)（团数不超过色数）形成了对比，在整数情况下等号不一定成立，但在分数情况下总是成立。 最后，我们来看分数团的计算复杂性和应用。虽然寻找一个图的最大团（整数团）是NP难问题，但计算最大分数团大小（即求解上述线性规划问题）可以在多项式时间内完成，例如使用内点法。这使得分数团成为一个有用的工具，它可以为整数团的大小提供一个上界（因为任何整数团都对应一个分数团，所以整数团大小≤分数团大小）。分数团在图论、组合优化以及编码理论等领域都有应用，例如在计算Shannon容量和研究图的完美性时，分数团都是一个重要的参数。