河北工业大学 硕士学位论文 元图特性及其应用 姓名：纪宗旨 申请学位级别：硕士 专业：计算数学 指导教师：米洪海 20071201 ? ? ? ? ? ? ? ? ? ?Dijkstra?Floyd? ? ? ? ? ? i ? THE PROPERTIES OF METAGRAPH AND ITS APPLICATION ABSTRACT Graph and Hypergraph are unsuitable for the analysis of the directed relationships between sets of elements.So a new graphthe Metagraph is discussed in this paper,which describes the relationships between sets of elements,but not single element, and which off ers some distinct advantages both of graphical visualization of systems as well as for formal analysis of system structure.The paper emphasizes on analyzing the properties of the metagraph, especially in the properties of its adjacency matrix and its closure matrix, which are the basis of researches and applications of metagraphs.Here with regard to ranking probleming on shortest paths and shortest metapaths, the methods of multifactorial decision-making of ASM fun is given.In addition ,Dijkstras algorithm and Floyds algorithm are genelized to fi nding shortest paths in metagraph,and some applica- tion of metagraphs are discussed in fuzzy rule management, system mod- eling,workfl ow modeling and analysis and so on. KEY WORDS: metagraph; adjacency matrix; closure of adjacency matrix; metapath; multifactorial decision-making of ASM- func. ii 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行研究工作所取得的成 果除文中已经注明引用的内容外，本学位论文的研究成果不包含任何他人创作的、已公开 发表或者没有公开发表的作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均已在文中以明确方式标明本学位论文原创性声明的法律责任由率人承担。 一繇歹乙孛 日期：2 。7 关于学位论文版权使用授权的说明 。| 本人完全了解河北工业大学关于收集、保存、使用学位论文的规定。同意如下各项内 容：按照学校要求提交学位论文的印刷本和电子版本，学校有权保存学位论文的印刷本和电 子版，并采用影印、缩印、扫描，数字化或其它手段保存论文；学校有权提供目录检索以及 提供本学位论文全文或者部分的阅监服务，学校有权按有关规定向国家有关部门或者机构 进交论文的复印件和电子版；在不以赢利为目的的前提下，学校可以适当复制论文的部分或 全部内容用于学术活动。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名 导师签名 ；础，话 劳1 尘荡 a 瓿z o0 7 f2 B 鼽叫、r 2i - 话 ? ?1? ? ?Konigsberg?2? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?3, 4, 5?6 ? ? ? ? ? ?Vanderbilt?Amit Basu?Robert W. Blanning? 3, 17? ? ?MBMS? ? ?21? ? ?22? ?8? ?24? ? 1 ? ? ? ? ? ? ? ? ?Dijkstra?Floyd? ? ? ? ? 2 ? ?Amit Basu ,Robert W.Blanning?3, 4? ?9, 6? ? ? 2.1? ? ? ? ? ? ?2.1.110? ?X = xi,i = 1,2,I? ? ?X?S =,E = ek,k = 1,K?E ?ek?ek= ,?Vk,Wk X,?Vk S Wk6= , Vk X?ek?Wk X?ek? ?1?X = x1,x2,x3,x4,x5,x6,x7?E = e1,e2,e3,e4? e1=,e2=,e3=, e4=. ?1? ?1?ek?Vk?Wk? ? ? ?1? 3 ? ?e2?x6?x3?x2?x6? ?x5? x2?x3?e2?x5?x6?e2? ? ? ? ? ? ?2.1.210?S =? a X?b X? a?b?p(a,b) =?el= ? (1)a V 1,b W L; (2)W l T V l+1 6= ,l = 1,L 1; (3)el,l = 1,2,L E. ? a?p(a,b)?b?p(a,b)?L? ?p(a,b)a?coin(a)? L S l=1 V l L S l=1 W l a ?p(a,b)b? ?(?coout(b)? L S l=1 W l b. ? ?p(a,a)? ? ? ? ? ? ? ? ? ?Set()? ?Set() = e1,e2,.? ?2.1.310?