图同构的判断方法

上传者：网友
|

翻新时间：2013-12-18

收藏到账号

全屏

图同构的判断方法

摘要

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