数据机构课程设计报告书

目录

一、概要

二、文章结构

三、问题描述：图的同构

四、判断图同构的算法

1. 基于生成全排列序列的算法

2. 两种基于深度优先搜索与根据局部匹配进行剪枝的算法

3. 基于 canonical labelling（CL）算法的图同构匹配问题

五、算法实现

六、算法测试

七、时间复杂度与 NP

八、图同构算法的实际应用

1. 计算机视觉与模式识别

2. 蛋白质结构的研究

3. 化合物分子的识别

4. 社交网络

九、小结

十、参考文献

一、概要

图是一种重要且功能极其强大的数据结构，我们利用图上的节点与边来呈现对象与对象间的关系。通常来说，现实世界中的问题大都可以转化成图上的问题， 搜索问题或是匹配问题。图的同构是一类模式匹配算法，现已被广泛应用于图像处理、蛋白质结构分析、信息网络的构建、化学键研究、社交领域，等等。图的同构算法在各种领域体现出了其具有的独特魅力与无与伦比的价值。

关键字：图的同构、子图同构、 NP 、Ullman、VF2、Nauty

二、文章结构

本文将粗略描述几种领先且广泛使用的图同构算法，并给出其中几个算法的大致实现，然后在代码基础上进行测试。其次，我会引援现有的评测论文中的结果来呈现各种不同算法在不同类型的图上的表现。最后，我将简要分析图的同构与子图同构算法在现实生活中的应用。