Orderly Algorithm to Enumerate Central Groupoids and Their Graphs  

作　　者：Tim BOYKETT 

机构地区：[1]Time's Up Research Department and Department of Mathematics,Johannes-Kepler University

出　　处：《Acta Mathematica Sinica,English Series》2007年第2期249-264,共16页数学学报（英文版）

基　　金：supported in part by Project P15691 from the Austrian Federal FWF,the national science finding body,as well as by several ongoing grants from Stadt Linz,Land Obersterreich and the Austrian Federal BKA.Kunst

摘　　要：A graph has the unique path property UPPn if there is a unique path of length n between any ordered pair of nodes. This paper reiterates Royle and MacKay＇s technique for constructing orderly algorithms. We wish to use this technique to enumerate all UPP2 graphs of small orders 3^2 and 4^2. We attempt to use the direct graph formalism and find that the algorithm is inefficient. We introduce a generalised problem and derive algebraic and combinatoric structures with appropriate structure. Then we are able to design an orderly algorithm to determine all UPP2 graphs of order 3^2, which runs fast enough. We hope to be able to determine the UPP2 graphs of order 4^2 in the near future.A graph has the unique path property UPPn if there is a unique path of length n between any ordered pair of nodes. This paper reiterates Royle and MacKay＇s technique for constructing orderly algorithms. We wish to use this technique to enumerate all UPP2 graphs of small orders 3^2 and 4^2. We attempt to use the direct graph formalism and find that the algorithm is inefficient. We introduce a generalised problem and derive algebraic and combinatoric structures with appropriate structure. Then we are able to design an orderly algorithm to determine all UPP2 graphs of order 3^2, which runs fast enough. We hope to be able to determine the UPP2 graphs of order 4^2 in the near future.

关 键 词：orderly algorithms paths in directed graphs ENUMERATION 

分 类 号：O157.5[理学—数学]