# 基于邻接点求解最大团问题Solving Maximum Clique Problem Based on Adjacent Points

DOI: 10.12677/CSA.2020.109175, PDF, HTML, XML, 下载: 176  浏览: 1,382  科研立项经费支持

Abstract: The maximum clique problem (MCP) is a significant problem in computer science field because of its complexity, challenging and extensive applications in data mining and other fields. This paper first briefly introduces the maximum clique problem and its research significance, then describes the research status of the maximum clique problem, and points out the deficiencies of the current deterministic algorithm and heuristic algorithm to solve the maximum clique problem. An algorithm for solving maximum clique based on adjacent points is presented according to the nature of edge connection between two nodes in the maximum clique. Based on the nature of edge connection between two nodes in the maximum clique, an algorithm for solving the maximum clique based on adjacent points is proposed, and its correctness and integrity are demonstrated. Finally, the algorithm is applied to the problem of finding the maximum clique containing any node.

1. 引言

2. 研究现状

3. 最大团问题及基于邻接点求解最大团算法

3.1. 最大团问题描述

Table 1. Symbolic representation required for maximum clique problem

3.2. 基于邻接点求解最大团问题算法基本思想

1. 对利用邻接矩阵对图G中的节点及边信息进行存储。

2. 将节点vi与其邻接点集合N(vi)中的各节点分别组成C1，此时Maximal-Clique[k] = C1 (k = 2)。

3. 若N(vi)与其中各节点邻接点集的交集IN(vi) ≠ ∅，则将IN(vi)内各节点与对应C1分别组成C2，此时Maximal-Clique[k] = C2 (k = 3)，并删除原先较小的Maximal-Clique[2]。

4. 重复步骤3，直到交集IN(vi) = ∅。

5. 此时Maximum-Clique(G) = Maximal-Clique[k]。

3.3. 算法示例

Figure 1. Solving undirected graph required

C1 = {(1, 2), (1, 3), (2, 3), (2, 12), (3, 4), (3, 9), (3, 11), (3, 12), (4, 5), (4, 6), (4, 7), (5, 6), (5, 7), (5, 8), (6, 7), (7, 8), (8, 9), (8, 10), (9, 10), (9, 12)}。

Figure 2. Maximum clique with 3 nodes

Figure 3. Maximum clique with 4 nodes

4. 算法的正确性和完整性

2) 假设当子图G的结果图Maximal-Clique为团，根据算法后续递归Maximal-Clique[k]中的节点都是图G中的节点，并且Maximal-Clique[k]一定为完全子图。

5. 求包含任意节点的最大团

1) 得到指定节点v的邻接链表N(v)；

2) 求v邻接链表的各节点的邻接表N(vi)；

3) v与其N(v)的各节点组成Maximal-Clique[v-2]；

4) 判断 $N\left(v\right)\cap N\left({v}_{i}\right)\ne \varnothing$ 是否成立，若成立则将交集中的节点加入得到Maximal-Clique[v-3]；

5) 重复4)直到 $N\left(v\right)\cap N\left({v}_{i}\right)=\varnothing$

6) 此时包含节点数最多的极大团即是所要求的包含指定节点v的最大团。

1) 节点5的邻接链表N(5) = {4, 6, 7, 8}；

2) 得到N(4) = {3, 5, 6, 7}，N(6) = {5, 6, 7}，N(7) = {4, 5, 6, 8}，N(8) = {5, 7, 9, 10}；

3) 得到包含节点5的Maximal-Clique[5-2] = {(5, 4), (5, 6), (5, 7), (5, 8)}；

4) N(5)∩N(4) = {6, 7}，N(5)∩N(6) = {4, 7}，N(5)∩N(7) = {4, 6, 8}，N(5)∩N(8) = {7}。将交集中的节点加入对应的Maximal-Clique[5-2]得到新的Maximal-Clique[5-3]，如图4所示。

Figure 4. 3-Maximal-clique with node 5

5) 递归最终求得所需的包含节点5的最大团，结果为图5

Figure 5. Maximum clique containing node 5

6. 总结和未来工作

 [1] 贾晓峰, 朱必文. 一类图中的最大团[J]. 系统科学与数学, 1998, 8(3): 226-233. [2] 马红平, 贾晓峰. 一类循环图中的最大团[J]. 华北工学院学报, 2001, 22(5): 384-386. [3] 黄培铣, 邓国勋, 王化等. 一类循环图的最大团与最大独立集[J]. 广西师范大学(自然科学版), 1992, 10(1): 12-15. [4] 戎文晋, 贾晓峰. 关于无爪图最大团数的一个估计[J]. 太原理工大学学报(自然科学版), 2002, 33(6): 676-677. [5] Adleman, L.M. (1994) Molecular Computa-tion of Solution to Combinatorial Optimization. Science, 226, 1021-1024. https://doi.org/10.1126/science.7973651 [6] Loukakis, E. and Tsouros, C. (1981) A Depth First Search Algorithm to Generate the Family of Maximal Independent Sets of a Graph Lexicographically. Computing, 27, 349-366. https://doi.org/10.1007/BF02277184 [7] Enet, S. and Solnon, C. (2003) Searching for Maximum Cliques with Ant Colony Optimization. Applications of Evolutionary Computing. Springer, Berlin Heidelberg, 236-245. https://doi.org/10.1007/3-540-36605-9_22 [8] Furtado, P. and Madeira, H. (2000) Vmhist: Efficient Multidimen-sional Histograms with improved Accuracy. Proceedings of the 2nd International Conference on Data Warehousing and Knowledge Discovery (DaWak 2000), London, 4-6 September 2000, 431-436. https://doi.org/10.1007/3-540-44466-1_44 [9] Srinivas, M.A., Gardner, P.C. and Ballard, D.H. (1987) Graph Problems and Connectionist Architectures. Technical Report TR 167, University of Rochester, Rochester. [10] Geng, X., Xu, J., Xiao, J., et al. (2007) A Simple Simulated Annealing Algorithm for the Maximum Clique Problem. Information Sciences, 177, 5064-5071. https://doi.org/10.1016/j.ins.2007.06.009 [11] Aarts, E. and Korst, J. (1989) Simulated Annealing and Boltzmann Machines, John Wiley& Sons, Chichester. [12] Tomita, E. and Seki, T. (2003) An Efficient Branch-and-Bound Algorithm for Finding a Maximum Clique. Proceedings of Discrete Mathematics and Theoretical Computer Science, 2731, 278-289. https://doi.org/10.1007/3-540-45066-1_22 [13] Tomita, E. and Kameda, T. (2007) An Efficient Branch-and-Bound Algorithm for Finding a Maximum Clique with Computational Experiments. Journal of Global Optimization, 37, 95-111. https://doi.org/10.1007/s10898-006-9039-7 [14] Konc, J. and Janezic, D. (2007) An Improved Branch and Bound Algorithm for the Maximum Clique Problem. Communications in Mathematical and in Computer Chemistry, 58, 569-590. [15] Tomita, E., Sutani, Y., Higashi, T., et al. (2010) A Simple and faster Branch-and-Bound Algorithm for Finding a Maximum Clique. Proceedings of WALCOM: Algorithms and Computation, 4th International Workshop, WALCOM 2010, Dhaka, 10-12 February 2010, 191-203. https://doi.org/10.1007/978-3-642-11440-3_18 [16] Li, C.M., Fang, Z.W. and Xu, K. (2013) Combining MaxSAT Reasoning and Incremental Upper Bound for the Maximum Clique Problem. 2013 IEEE 25th International Conference on Tools with Artificial Intelligence, Herndon, 4-6 November 2013, 939-946. https://doi.org/10.1109/ICTAI.2013.143 [17] San Segundo, P., Nikolaev, A. and Batsyn, M. (2015) Infra-Chromatic Bound for Exact Maximum Clique Search. Computers & Operations Research, 64, 293-303. https://doi.org/10.1016/j.cor.2015.06.009