有向图的同构判定算法:出入度序列法

应用科学学报 ›› 2002, Vol. 20 ›› Issue (3): 258-262.

有向图的同构判定算法:出入度序列法

李锋, 商慧亮

复旦大学电子工程系, 上海 200433

收稿日期:2001-06-09 修回日期:2001-11-12 出版日期:2002-09-30 发布日期:2002-09-30
作者简介:李锋(1946-),男,上海人,教授.

An Isomorphism Testing Algorithm for Directed Graphs: the In-degree and Out-degree Sequence Method

LI Feng, SHANG Hui-liang

Department of Electronic Engineering, Fudan University, Shanghai 200433, China

Received:2001-06-09 Revised:2001-11-12 Online:2002-09-30 Published:2002-09-30

摘要/Abstract

摘要： 提出了有向图的同构判定新算法:出入度序列法.该算法可应用于许多可用有向图描述的模式识别等实际问题中.

关键词: 图论算法, 图的同构, 入度序列, 出度序列

Abstract: In this paper, a new isomorphism testing algorithm for directed graphs——the in-degree and out-degree sequence method——is presented. The algorithm can be used in many pattern recognition problems that can be described by directed graphs.

Key words: graph isomorphism, graph theory algorithm, out-degree sequence, in-degree sequence

中图分类号:

TB126

李锋, 商慧亮. 有向图的同构判定算法:出入度序列法[J]. 应用科学学报, 2002, 20(3): 258-262.

LI Feng, SHANG Hui-liang. An Isomorphism Testing Algorithm for Directed Graphs: the In-degree and Out-degree Sequence Method[J]. Journal of Applied Sciences, 2002, 20(3): 258-262.