图同构的判断方法

图同构的判断方法

图同构的判断方法
 
摘要

图论是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

【包括：毕业论文、开题报告、任务书】

【说明：论文中有些数学符号是编辑器编辑而成，网页上无法显示或者显示格式错误，给您带来不便请谅解。】

【图同构的判断方法】