回溯法解决最大团与图m着色问题

1、最大团问题

** 问题描述**

我们考虑一个非空的无向图G=(V, E)，其中V代表顶点集而E则由所有由V中不同元素组成的无序对构成。对于任意U属于V的情况而言，在满足任意两个顶点u和v都属于U时（即u,v∈U），若对应的(u, v)边都存在于E中，则我们称这样的子集U为一个完全子图；特别地，在这种情况下（即当任何两个顶点之间都有连接时），我们可以将这样的完全子图表视为一个"团"（clique）。在这种情况下（即当不存在更大的包含该团的新团时），我们称该团是一个最大的"最大团"（maximal clique），其特性即在于包含尽可能多数量的顶点。

如果U \subseteq V并且对于任意u,v \in U满足(u, v) \notin E，则称U为图G的一个完全不含边的子图。这个完全不含边的子图U成为图G的一个独立顶点集合当且仅当不存在任何比其大的完全不含边的子图包含它。而称这样的一个独立顶点集合为该图的最大独立顶点集合是因为它包含了所有可能存在的更大独立顶点集合中最多的元素数量。

对于任意给定的一个无向图 G = (V, E)，我们称其补图为 G’ = (V’, E’) ，其中 V’ 定义为 V’ = V；边集满足关系 (u, v) ∈ E’ 当且仅当 (u, v) ∉ E 。
若 U 为 G 中的一个完全子图，则在补图中它对应的是一