图同构的判断方法论文

　　在学习、工作中，说到论文，大家肯定都不陌生吧，通过论文写作可以培养我们独立思考和创新的能力。那么一般论文是怎么写的呢？下面是小编帮大家整理的图同构的判断方法论文，供大家参考借鉴，希望可以帮助到有需要的朋友。

　　摘要

　　图论是1个应用10分广泛而非常有趣的的分支，物理学、化学、生物学、科学管理、计算机等都要用到图论的内容.图论与数学的其他分支，如群论、矩阵论、概率论、拓扑、数值分析、组合数学等有着密切的`关系.图的同构是图论学科中的基本问题之1，属于图论中多个NP—完全问题之1.所谓图的同构，简单的说，就是两个表示的关联关系完全相同.“同构”的概念看似简单，但是，判定两个图同构却不是1件简单的事情.本文旨在研究图同构的判定方法，提出了几种判定两个图同构的方法，以及两个图同构的必要条件.

　　关键词：图的同构；判定方法；邻接矩阵；度序列

　　The Methods of Judging Isomorphism of Graphs

　　Abstract

　　The graph theory is a useful and interesting branch witch can be widely used in the physics, the chemistry, the biology, the scientific management, the computer, etc. And it has close relationships with the other branch of mathematics .For example the group theory, the theory of matrices, the theory of probability, the numerical analysis, the combinatorics and so on. Graph’s isomorphism is one of the basic problems and NP problems in graph theory. Graphs’ isomorphism means that the graphs’ architectures are the same. The concept is simple but it’s not so easy to determine whether two graphs are isomorphism or not. This paper is meant to do a research on judging graphs’ isomorphism. The author puts forward several methods on judging graphs’ isomorphism and the necessary conditions of graphs’ isomorphism.

　　Keywords: graph isomorphism; determination method; adjacency matrix; degree sequence

　　目 录

　　中文标题……1

　　中文摘要、关键词……1

　　英文标题……1

　　英文摘要、关键词……1

　　正文

　　1.引言………2

　　2.基本概念……3

　　3.主要结论……7

　　3.1由定义，直接找出两个图的同构映射……8

　　3.2用邻接矩阵判定……9

　　3.3关联度序列法……9

　　3.4有向图的同构：出入度序列法……10

　　3.5判定两图不同构的方法……13

　　4.结束语……15

　　参考文献 ……16

　　致谢 ………17