一种表示有向图的表方法及其应用  

A Table Method for Representing Digraph and its Application

作　　者：谢深泉[1,2] 

机构地区：[1]广东培正学院计算机科学与工程系,广州510830 [2]湘潭大学信息工程学院,湖南湘潭411105

出　　处：《小型微型计算机系统》2011年第6期1211-1217,共7页Journal of Chinese Computer Systems

基　　金：国家自然科学基金项目(60673193)资助;湖南省重点学科建设项目资助;湖南省教育厅重点项目(07A067)资助

摘　　要：图的表示方法很多,各有其优缺点.采用不同的表示方法,可获得图的不同的时空性能.本文阐述了图的一种新表示方法,该方法用一种命名规则将有向图表示为节点标签表,给出了由节点标签表产生节点链的算法.并用这种称为表方法研究了有向图的回路性质,特别地将它应用于研究de Bruijn回路、欧拉回路和哈密顿回路,给出了计算欧拉回路和哈密顿回路的新方法.本研究表明该方法具有较好的理论和实用价值.There are many methods for representing graphs,each method has their advantages.Deferent time-space property about graphs are obtained by using deferent method to represent graphs.A new method for representing a digraph as a node-label table by using naming rules is described and an algorithm for generating node chains from a node-label table is given in this paper.Some properties of digraph circuits are researched by using the new method,called table method.Especially,applying the table method to generate circuits of de Bruijn graph,Eulerian graph and Hamiltonian graph some new algorithms for generating circuits are successfully given.It is shown that the table method has preferable theory and application value by this research.

关 键 词：命名规则 表方法 节点标签表 deBruijn序列 欧拉回路 哈密顿回路 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]