摘要
从超图的强同构引出保持超图顶点间超邻接性的点同构,定义超图的邻接矩阵和赋权超图的权矩阵,并在此基础上得到了求解超图任意顶点间最短路径和求解超图直径的推广Floyd算法.最后通过实例验证了算法的可行性,并与李春明在1994年得到的结果进行比较,得出算法的复杂度为O(n3),该算法是一个有效算法.
Based on strong isomorphism for hypergraphs, vertex isomorphism is defined, which preserves hyper-adjacency property between vertices. Adjacency-matrixes of hypergraphs and weighted hypergraphs are presented respectively. The Floyd＇ s algorithm is generalized to finding shortest paths between all pairs of vertices in a hypergraph. The publication provides an instance which verifies the practicability of the modified algorithm and whose results have been compared with those Of the method given by LI Chun-ming. Time complexity of the presented algorithm is obtained to be O（n^3）.
出处
《重庆大学学报（自然科学版）》
EI
CAS
CSCD
北大核心
2005年第11期106-109,共4页
Journal of Chongqing University
关键词
超图
点同构
邻接矩阵
FLOYD算法
hypergraph
vertex isomorphism
adjacency matrix
Floyd＇ s algorithm
