摘要：图的同构问题一直以来在计算机和离散数学中受到普遍关注，由于图的结构复杂，类型多样，表示方法也充满了不确定性，其同构问题在算法中被认为是一个NP-完全问题。尽管图的概念很早被提出来，但对其算法的探讨一直困扰着各界学者。然而图的应用领域又是十分广泛的，图是非线性的数据结构，可以作为计算机存储数据和遍历数据的模型；在遗传学领域中，图可以表达DNA中含氮碱基的排列方式等等。树作为图的一种特殊类型，具有结构简单，存储、表达更为方便的优点。

文章主要探讨了图和树的同构判定方法，以及不同构树的类似度计算方法。树又分为有向树和无向树，无向树可根据一定的算法计算出其根结点，从而转化为有向树，简化算法。除了遍历、邻接矩阵这样的传统同构判定方法外，我也会引用国内外学者提出的一些经典算法。在树的同构判定这一章节中，部分算法是从国内外相关论文中收集的，通过案例具体、详细地阐述算法的每一个步骤，并比较它们各自的优缺点和适用范围。对于树的类似度计算方法，我们着重探讨最大公共子树的问题，关于如何求出最大公共子树，并提出了其它几种计算树类似度的方法。

论文的第一章介绍图、树同构问题研究在信息时代背景下的意义和国内外对于该问题的研究现状概括。第二章介绍了数据挖掘的概念，图和树的概念及相关基本术语，以及两部图及其匹配的概念。第三章研究图的同构判定和具体的算法，除了邻接矩阵外还有针对有向图的同构判定算法。第四章具体探讨了树的同构判定算法，包括邻接矩阵，遍历及其前提条件和国内外学者提出的一些算法，在此基础之上，本文对遍历方法作出了改进。第五章探讨树的类似度问题，以及有关无向树转化为有向树的研究。由于树的相似度有着不同的评判标准，因此该部分将从不同角度来分析树的相似性；树的类似度可以从计算最大公共子树、同构子树和编辑距离三种角度来评价。第六章是对算法的总结性讨论，以及对算法改善提出的一些设想。

关键词： 树;同构 ;类似度;最大公公共共子树

目录

摘要

Abstract

第一章绪论      1

1.1研究目的和意义·   ·1

1.2国内外研究现状·   ·1

第二章基本概念与定义     ·4

2.1数据挖掘·   ·4

2.2图的概念及分类·   ·4

2.2.1图的概念及其表示·   ·4

2.2.2两部图及匹配·   ·6

2.2.3树以及分类·   ·6

2.2.4树的存储方式·   ·7

第三章图的同构算法     ·  ·9

3.1图的同构·   ·9

3.2图的同构算法·   ·9

第四章树同构算法现状11

4.1树的归类11

4.2有向无序树的同构判定方法11

4.2.1遍历12

4.2.2邻接矩阵12

4.2.3AHU算法13

4.2.4无序树遍历方法的改进15

4.3时间复杂度分析16

第五章树的相似度计算方法17

5.1最大公共子树算法17

5.2同构子树算法18

5.3编辑距离算法21

5.4时间复杂度分析23

结论24

参考文献27

致谢29