摘要
组合矩阵论是组合学、图论和线性代数的有机结合体。自上世纪80年代来,它作为兴起且快速发展的一个数学分支,利用矩阵论和线性代数对组合定理进行证明及分析,描述了一些定性组合性质。同时,运用组合方法分析和证明了一些代数问题,如经典的Cayley-Hamilton定理。许多科学领域所建立的模型系统与数学模型中的很多定性性质是一致的,所以组合矩阵理论不但与众多的数学领域有密切的联系,而且在信息科学、社会学、经济学、生物学、化学、计算机科学理论和控制论等领域都有具体而实际的应用背景,因此组合矩阵理论是一个研究非常活跃且重要的领域。自Brualdi和Ryser的《组合矩阵论》问世以来,推动了组合矩阵理论深入研究和广泛的应用。
作为组合矩阵理论的重要组成部分——图论与符号模式矩阵,其研究是当前国际上组合矩阵论中一个年轻而又十分活跃的研究课题。图论主要研究图的拓扑性质,可以为任何一个包含了某种二元关系的系统提供一种分析和描述的模型。符号模式矩阵主要研究其定性类的组合结构,即研究其定性类中实矩阵的仅与其元素的符号以及零-非零结构有关而与其元素大小无关的组合性质。众所周知,智能体系统的通信结构图确定了其个体间信息交流和共享的方式,而且通信链的状态在系统稳定性方面和任务完成中具有决定性的作用,因此本文致力于以下两个问题的研究:一是在什么样的通信链条件下,网络化系统能够获得所要求的状态,例如达到智能系统的稳定状态;二是怎样设计智能体各元件之间的衔接来满足特定的实践任务中所需要的通信条件。用关联矩阵及其符号模式矩阵的一些性质作为理论基础,来说明所提出的条件与有向图中的环路之间的密切关系,且能够用来研究一些其它的网络问题,如有向网络的边一致问题等。而广义scrambling指数与广义μ-scrambling指数在通信系统中具有重要作用,因此本文应用符号模式矩阵研究了一类特殊图形的广义scrambling指数与广义μ-scrambling指数;同时研究了在什么样的条件下一个有向图可以转化为平衡图,以及符号模式矩阵的组合性质在智能系统中的应用。本文的主要研究工作如下:
(1)介绍了本文的研究背景与意义以及图论、符号模式矩阵基本概念,及图论和符号模式矩阵在机械器件、智能系统中的应用。
(2)研究了图理论在机械器件中的应用,利用图形的拓扑与几何特性,运用定性与定量的分析方法,设计出变节距滚子链,从而达到对多边形效应的补偿作用。正是新方法解决旧问题,是对学科融合的完美诠释。
(3)将智能系统各元件之间的相互联系,以及它们之间的影响程度用边连接起来,正相关元件之间的边用“1”或“+”标识,负相关元件之间的边用“-1”或“-”号标识,就组成了一个定号图。将智能系统与通信系统中的各元件之间的相互联系与影响程度抽象为图模型。利用图论与符号模式矩阵的相关知识对图形进行研究,计算出相关的指数与参数从而使系统达到稳定平衡的运行,如计算证明特殊图形的本原指数。然后再根据各元件之间影响程度列出函数,根据其相关性与系统运行时间的关系来判断元件按以上序列排列是否能够达到智能系统的稳定性。
(4)阐述了本原定号有向图的广义scrambling指数与广义μ-scrambling指数的研究进展,研究了一类本原定号有向图的广义μ-scrambling指数,分别得到了这一类图的重下μ-scrambling指数和重上μ-scrambling指数的界。同时给出了两个特殊图的广义scrambling指数与广义μ-scrambling指数。
(5)运用图理论中的加权图及其它知识,对Dijkstra算法进行优化。解决了几乎无不同权值的单源最短路径的Dijkstra算法的实现,以及混合权值的Dijkstra算法的实现。提出了基于Dijkstra算法考虑多个权值来计算最短路径,即基于Dijkstra算法混合权图的最短路径动态搜索数学模型。
The Combinatorial Matrix Theory is an organic combination of the combinatorialmathematics, graph theory and linear algebra. Over the recent20years, as a newly arising andfast developing branch of the mathematics, it uses the theory of matrices and linear algebra toapprove the combinatorial theorem, analyze and describe the combinatorial properties ofsome qualitative combinations; and it also applies the combinatorial methods to analyze andapprove some algebraic problems (such as the classic Theorem—Cayley-Hamilton). Themodels and systems developed in many fields of the science is consistent with the mostqualitative properties in the mathematical model, thus the combinatorial matrix theory is notonly closely connected with many mathematical fields, but also it frequently appears and hasparticular and practical application backgrounds in many other research fields includinginformation science, sociology, economics, biology, chemistry, theoretical computer scienceand control theory et al., therefore, Combinatorial Matrix Theory is a very active andimportant research field. Since the emergence of Combination Matrix Theory developed byBrualdi and Ryser, it has largely driven the study and application of the combinatorial matrixtheory.
As important components of the combinatorial matrix theory–the study of graph theoryand sign pattern matrix, it is currently one very young and active research subject among theinternational combinatorial matrix theories. Graph theory mainly studies Topologicalproperties of graph, provides the model for any system which includes some kind of binaryrelation to analyse and describe. The sign pattern matrix mainly studies the qualitativecomposite structures, namely not considering the value of its elements. As is well-known, themode of information exchanging and sharing is determined by the communication topology ofan agent system. Thus the status of communication links is crucial for system stability andtask achievement. As a result, great effort has been devoted to investigation of the following two problems. One is under what communication link conditions can the networked systemobtain the desired status, such as achieving a steady state. The other is how to design theconnection pattern between each element for agents to meet these conditions required by thespecific practical tasks.We use incidence matrix and some properities of sign pattern matrix astheoretical basis to state the close relationship between the proposed condition and loopcircuit in directed graph and be used to study some other network problems, such as Edgeconsistency of directed network. And as the important roles in communication system are thegeneralized scrambling index and the generalized μ-scrambling index of the special primitiveno-powerful signed digraphs, in this paper we study them.In the meanwhile studying underwhat conditions can a digraph be balanced; the combinatorial properties of Sign patternmatrix and the application on the intelligent system.The main research contents are asfollowing:
(1) The basic concepts of graph theory and sign pattern matrix were introduced. Theresearch progress of sign pattern matrix, generalized scrambling index and generalizedμ-scrambling index, the application of the sign pattern matrix in intelligent system weredescribed.
(2) We studied the application of graph theory in mechanical devices. Compensation ofVariable Pitch Roller Chains for the Polygon Effect was researched by use of the graph.The roller chain with variable pitches to abate and reduce polygon effect was designed.
(3) We linked the relationship between each component of intelligent system to the degreeof influence between them by edges,the sign graph was composed of edges between positiveelement which were identified by “1” or “-1” and edges between negative element whichwere also identified by “1” or “-1”.It made the system achieved balance by converting digraphinto equilibrium diagram.We judged the element arranged in the following order aboutwhether can achieve the stability of the intelligent system based on the influence degreebetween each element showing the relationships between function and its correlation andsystem uptime.
(4) The generalized μ-scrambling index of a class of primitive signed digraph was studied, some exact th lower and upper bounds of the μ-scrambling indices of this class of primitivedigraph were given respectively. We provided the generalized scrambling indices and thegeneralized μ-scrambling indices for the two special primitive digraphs at the same time.
(5) By use of weighted graph and other knowledge, an effective Dijkstra algorithm ofsingle-source shortest paths was presented to implement the Dijkstra algorithm for the singlesource shortest path problem with few distinct positive lengths. The method to calculate theshortest path considering mixed weights based on the Dijkstra algorithm was presented in thispaper, which was based on Dijkstra algorithm mixing with shortest path of weighted graph tosearch mathematical model dynamically.
引文
[1]邵嘉裕.组合数学.上海:同济大学出版社,1991.
[2]卢开橙,卢华明.组合数学.北京:清华大学出版社.2006.
[3]陈景润.组合数学.上海:上海科学技术出版社,1985.
[4]卜月华.图论及其应用.东南大学出版社,2000.
[5] M.Akelbek, S.Fital, J.Shen.Abound on the scrambling index of a primitive matrix of aprimitive matrix using Boolean rank, Linear Algebra Appl.,2009,431:1923-1931.
[6] Yufei Huang, Bolian Liu. Generalized scrambling indices of a primitive digraph.LinearAlgebra and its Applications,2010,433:1798-1808.
[7] Bolian Liu, Yufei Huang. The scrambling index of primitive digraphs. Computers and M-athematics with Application.2010,60:706-721.
[8] M. Akelbek, Steve Kirkland. Primitive digraphs with the largest scrambling index. LinearAlgebra and its Applications,2009,430:1099-1110.
[9] S.Chen, B. Liu. The scrambling index of symmetric primitive matrices. Linear Algebraand its Applications,2010,433:1110-1126.
[10] Hwa Kyung Kim. Generalized competition index of a primitive digraph. Linear Algebraand its Applications,2010,433:72-79.
[11] Hwa Kyung Kim, Sung Gi Park. A bound of generalized competition index of aprimitive digraph. Linear Algebra and its Applications,2012,436:86-98.
[12] S.-R.Kim. Competition graphs and scientific laws for food webs and other systems,Ph.D. Thesis, Rutgers University,1988.
[13] Hwa Kyung Kim. A bound on the generalized competition index of a primitive matrixusing Boolean rank. Linear Algebra and its Applications,2011,435:2166-2174.
[14] H.K.Kim. Competition indices of tournaments, Bull Korean Math.Soc.,2008,45(2):385-396
[15] H.H.Cho, H.K.Kim. Competition indices of digraphs, in: Proc. of Workshop in Comb.,2004, pp.99-107.
[16] H.H.Cho, S.-R.Kim, Y.Nam. The m-step competition graph of a digraph, DiscreteAppl.Math.2000,105:115-127.
[17] Min Soo Sim, Hwa Kyung Kim. On generalized competition index of a primitive Tourn-ament. Discrete Mathematics,2011,311:2657-2662.
[18] Hwa Kyung Kim, Sang Hoon Lee. Generalized competition indices of symmetric primi-tive digraphs. Discrete Applied Mathematics.2010,160:1583-1590.
[19] Mahmud Akelbek, Steve Kirkland.Primitive digraphs with the largest scramblingindex.Linear Algebra and its Applications.2009,.430:1111-1130.
[20] Hwa Kyung Kim, Generalized competition index of an irreducible Boolean matrix.Linear Algebra and its Applications,2013,438:2747-2756.
[21]高玉斌,符号模式矩阵与线性方程组的符号可解性,华北工学院学报,3(2000):274-279.
[22] Yubin Gao, Jiongsheng Li.Stroagly potential stability of double star sign patterns,Submission to Linear Algebra Appl.
[23] Yanling Shao, Yubin Gao. The kth upper generalized exponend set for primitivematrices, Australas. J.Combin,23(2001):19—26.
[24] Yubin Gan and Jiongsheng Li. On the potential stability of star sign pattern matrices, Linear Algebra Appl.,327(2001):61—68.
[25]邵燕灵.组合矩阵论中若干专题的研究.北京理工大学博士论文.2004.
[26] R.M. May. Stability and Complexity in Model Ecosystems, Princeton UniversityPress,1973.
[27] R.M.May. Qualitative stability in model ecosystems, Ecology,54(1973):638-641.
[28] C.Jefffies. Qualitative stability and digraphs in model ecosystems,Ecology,55(1974),1415-1419.
[29] Yu M.Svirezev and D.O. Logofet. Stability of Biological Relations (in Russian),“Nauka”, Moscow,1978.
[30] B.L. Clarke. Theorems on chemical network stability. Chemical Physics,62(197-5):773—775.
[31] B.L. Clarke. Stability of topologically similar chemical networks. Chemical Physics,62(1975):3726-3738.
[32] J.J. Tyson. Classification of instabilities in chemical reaction systems. Chemical Physics,62(1975):1010-1015.
[33] Y.Shirakura. Jeffries’ colour point method and Simons-Homan model (in Japanese)Sociological Theory and Methods,1(1986):57-70.
[34] T.Ando and R.A.Brualdi. Sign-central matrices, Linear Algebra Appl.,208/209(1994):283—295.
[35] R.A.Brualdi, K.L.Chavey and B.L.Shader. Rectangular L-matrices, Linear AlgebraAppl.,196(1994):37-61.
[36] R.A.Brualdi and B.L.Shader. Matrices of Sign-solvable Linear Systems,CambridgeUniversity Press, Cambridge,1995.
[37] V.Klee.Recursive structure of S*-matrices, and on an O(m2) algorithm for recogn-izing strong sign-solvability, Linear Algebra Appl.,96(1987):233-247.
[38] V.Klee, R.Ladner and R.Member. Signsolvability revisited, Linear Atyebra Appl.,59(1984),131—157.
[39] V.Klee,B.Von Hohenbalken and T.Lewis. On the recognition of s-systems, LinearAlgebra Appl.,192(1993):187-204.
[40] V.Klee and P.van den Driessche. Linear agorithms for testing the sign-solvabilityof a matrix and for finding Z-maximum matchings in acyclic graphs,Numer.Mat-h.,28(1977):273-285.
[41] C.R.Johnson, J.S.Maybee, D.D.Olesky and P.van den Driessche. Nested sequencesof principal minors and potentially stability, Linear Algebra Appl.,262(1997),243-257.
[42] C.R.Johnson, G.R.Johnson and T.A.Summers.The potentially stable tree sign patterns for dimensions less than five, Linear Algebra Appl.,126(1989):1-13.
[43] C.R.Jobnson, S.A.Lewis and D.Y.Yau, Possible line sums for a qualitative matrix,Linear Algebra Appl.,327(2001):53-60.
[44] J.S.Maybee. Sign solvability, in Computer-Assisted Analysis and Model SimplicationAcademic Press, New Yoek,1981:201-257.
[45] J.S.Maybee, Qualitatively stable matrices and convergent matrices, IMA Vol.Math.Appl.,17, New York,1989:245-258.
[46] Jiayu Shao. On the exponent of a primitive digraph.[J]. Linear Algebra and itsApplications.1985,64:21-31.
[47] Lihua You, Jiayu Shao.Bounds on the bases of irreducible generalized sign patternmatrices. Linear Algebra and its Applications.2007,427:285-300.
[48] Jiayu Shao, Qiao Li. On the indices of convergence of irreducible Boolean matrices.Linear Algebra and its Applications.1987,97:185-210.
[49] JiaYu Shao, SukGeun Hwang, Generalized exponents of non-primitive graphs. LinearAlgebra and its Applications,1998,279:207-225.
[50] JiaYu Shao, Bin Li, The set of generalized exponents of primitive simple graphs.LinearAlgebra and its Applications,1997,258:95-127.
[51] Xiao-jun Wu, Jiayu Shao, Zhi-ming Jiang, Xi-zhao Zhou. On the exponents of primitiveministrong digraphs with shortest elementary circuit lengths. Linear Algebra and itsApplications,1995,222:41-61.
[52] Shao Jiayu, on a conjecture about the exponent set of primitive matrices. LinearAlgeb-ra and its Applications,1985,65:91-123.
[53] R.A.Brualdi, J.Shao, Generalized exponents of a primitive symmetric digraph, DiscreteAppl. Math.1997,74:275-293.
[54] R. A. Brualdi, Bolian Liu. Generalized exponents of primitive directed graphs.[J].Graph Theory.1990,14:483-499.
[55] B.Liu, H.J.Lai, Matrices in Combinatorics and Graph Theory, Kluwer AcademicPublishers,2000.
[56] B.Liu, On exponent of indecomposability for primitive Boolean matrices, LinearAlgebra Appl.,1999,298:1-8.
[57] B.Liu. On fully indecomposable exponent for primitive Boolean matrices withsymmetric ones, Linear Multilinear Algebra,1992,31:131-138.
[58] B.Liu. Generalized exponents of Boolean matrices, Linear Algebra Appl.2003,373:169-182.
[59] B.Liu. Generalized exponents of tournament matrices,Ars Combin.1994,38:243-250.
[60] S. Chen, B. Liu. Matrices with maximum k th local exponent in the class of doubly sy-mmetric primitive matrices, Discrete Math.2008,308:3386-3392.
[61] S.Chen, B. Liu. Thek th local exponent of doubly symmetric primitive matrices,Appl.Math.Lett.2006,19:392-397.
[62] R.A.Brualdi, B.L.Liu.Generalized exponents of primitive directed graphs. Graph Theory.1990,14:483-499.
[63]B.L.Liu, L.H.You. Bound on the base of primitive nearly reducible sign pattern matrices.Linear Algebra and its Applications.2006,418:863-881.
[64] Bolian Liu. The period and base of a reducible sign pattern matrix. Discrete Math.2007,307:3031–3039.
[65]柳柏濂.组合矩阵论(第二版).科学出版社,2005.
[66] Bolian Liu, Lihua You, Gexin Yu, On extremal matrices of second largest exponent byBoolean rank. Linear Algebra and its Applications,2007,422:186-197.
[67] Bolian Liu, Brendan D. McKay, Nicholas C. Wormald, Zhang Ke Min, The exponent setof symmetric primitive (0,1) matrices with zero trace. Linear Algebra and its Applicati-ons,1990,133:121-131.
[68] Bolian Liu.Anote on the exponents of primitive (0,1) matrices.LinearAlgebra and itsApplications,1990,140:45-51.
[69]李乔.矩阵论八讲.上海科学技术出版社,1988.
[70] Yubin Gao, Yanling Shao, Jian Shen. Bounds on the local bases of primitivenon-powerful nearly reducible sign patterns. Linear and Multilinear Algebra.2009,2:205-215.
[71] YanlingShao, YubinGao. The local bases of primitive non-powerful signed symmetricdigraphs with loops. Ars Combinatoria.2009,90:357-369.
[72] Yubin Gao, Yanling Shao. The number of negative entries in a sign pattern allowingorthogonality. Graphs and Combinatorics.2004,20:311-317.
[73]邵燕灵,高玉斌.两类特殊的符号模式矩阵.中北大学学报.2000,2:98-101.
[74]胡红萍,王建中,高玉斌,白艳萍.某类本原不可幂定号有向图局部基的界.中北大学学报(自然科学版),2009,30:401-404.
[75] Yubin Gao, Yanling Shao. Generalized exponents of primitive two-colored digraphs.Linear Algebra and its Applications,2009,430:1550-1565.
[76] Bo Cheng, Bolian Liu.The base sets of primitive zero-symmetric sign pattern matrices.Linear Algebra Appl.2008,428:715-731.
[77] Qian Lian, Bolian Liu, Bounds on the kth multi-g base index of nearly reducible signpattern matrices. Discrete Mathematics.2008,308:4846-4860.
[78]邵嘉裕,尤利华,单海英. Powerful符号矩阵的基指数.同济大学学报.2003,12:1490-1494.
[79] Hongping Ma.Bounds on the local bases of primitive non-powerful,minimally strongsigned digraphs. Linear Algebra and its Applications.2009,430:718-731.
[80] Z.Li, F.Hall, C.Eschenbach. On the period and base of a sign pattern matrix. LinearAlgebra and its Applications.1994,212/213:101-120.
[81]尤利华.非本原符号矩阵的广义基指数的一个最好上界.广东技术师范学院学报.2006,3:34-38.
[82] Yubin Gao,Yihua Huang,Yanling Shao. Bases of primitive non-powerful signedsymmetric digraphs with loops. Ars Combinatoria.2009,90:383-388.
[83] Yanling Shao, Jian Shen, Yubin Gao. The kth upper basesof primitive non-powerfulsigned digraphs. Discrete Mathematics.2009,309(9):2682-2686.
[84] Yanting Liang,Bolian Liu,Hong-Jian Lai.Multi-g base index of primitive anti-symmetricsign pattern matrices, Linear Algebra Appl.2009,57:535-546.
[85] F. S. Roberts. Graph Theory and ItsApplication to Problems of Society. England.1978.
[86] J.A. Bondy and U.S.R. Murty. Graph theory with applications. The Macmillan Press.1976.
[87] C.R.Johnson. Some outstanding problems in the theory of matrics. Linear andMultilinear Algebra.1982,12:99-108.
[88] R.A. Brualdi, H. J. Ryser. Combinatorial Matrix Theory. Cambridge: Cambridge Unive-rsity Press,1991.
[89] R.A.Brualdi, Chaveykl, B.L.Shader. Rectangular L-Matrices. Linear Algebra Appl,1994,196:37-61.
[90]严寒冰,刘迎春.基于GIS的城市道路网最短路径算法探讨.计算报,2000,23(2):210-215.
[91]熊熙,高飞.基于Dijkstra的PKI交叉认证路径搜索算法.计算机工程,2009,35(5):168-170.
[92]王华.基于GIS城市道路最短路径算法研究.测绘科学,2011,36(3):160-161.
[93]张渭军,王华.城市道路最短路径的Dijkstra算法优化.长安大学学报(自然科学版),2005,25(6):62-65.
[94]于德新,杨薇,杨兆升.重大灾害条件下基于GIS的最短路径改进算法.交通运输工程学报,2011,11(4):123-126.
[95]詹云,孙涌,房鹏.改进Dijkstra算法在GGIS中的应用.计算机工程,2011,34(13):193-195.
[96]刘建美,马寿峰,马帅奇.基于改进的Dijkstra算法的动态最短路径计算方法.系统工程理论与实践,2011,31(6):1153-1157.
[97]范巍巍,程琳.随机路网的最短路径问题研究.公路交通科技,2007,24(9):112-115.
[98] Xu M H, Liu Y Q,eta1,An improved Dijkstra’s shortest path algorithm for sparsenetwork.Applied Mathematics and Computation,2007,185(1):247-254.
[99] Guoxin Yang, Naiqing Lin, Yujing Sun.Analysis on polygon-effect of chain-transmissi-on. Agriculture and technology.1996,92(4):p46-48.
[100] Runfang Li, Jianjun Wang. gear system dynamics-Vibration. Shock. Noise. Science P-ress,1996:8-9.
[101] Bangchun Wen, Shuying Liu, Zhaobo Chen, He Li. Mechanical vibration theory andapplication. Higher Education Press,2008:25-27.
[102] Jianxing Zhou, Xingming Qi, Jinyi Jiao, Chunteng Chang. MATLAB From approachesto master. Posts&Telecom press,2008:38-42.
[103] Zhifeng Zheng, Yixing Wang, Bangheng Cai. Chain transmission. Mechanic industryPress,1984:62-78.
[104] W.Ren and R.W. Beard, Distributed Consensus in Multi-vehicle Cooperative Control:Theory and Applications. London: Springer-Verlag,2008.
[105] J. A. Fax and R. M. Murray.“Information flow and cooperative control of vehicleformations,” IEEE Transactions on Automatic Control, Sep.2004,49(9):1465-1476.
[106] D. Lee and M. W. Spong,“Stable flocking of multiple inertial agents on balancedgraphs,” IEEE Transactions on Automatic Control, Aug.2007,52(8):1469–1475.
[107] L. Hooi-Tong,“On a class of directed graphs-with an application to trafficflowproblems,”Operations Research,1970,18(1):87–94,.
[108] B. Gharesifard and J. Cort′es,“Distributed strategies for making a digraphweight-balanced,” in Proceedings of the2009Allerton Conference on Communicatio-ns, Control, and Computing, Monticello, Illinois,2009.
[109] B. Gharesifard and J. Cort′es,“When does a digraph admit a doubly stochastic adjac-ency matrix?” in submitted to the2010American Control Conference,2010.
[110] B. Gharesifard and J. Cort′es,“Distributed strategies for generating weightbalancedand doubly stochastic digraphs,” submitted to SIAM Journal on Control andOptimization,2010.
[111] R..Z. Norman and F.S. Roberts, A derivation of a measure of relative balemce for socialstructures and a characterization of extensive ratio systems. Math.Psych.,9(1972):66-91.
[112] F.S. Roberts, Discrete Mathematical Model withApplications to Social, Prentice-Hall,Englewood.
[113] D. Cartwright and F. Harary, Structural balance: A generalization of Heider,s theory,Psych. Rev.,63(1956):277-293.
[114] A. L. Dulmage. Gaps in the exponent set of primitive matrices. Illinois J. Math.1964,8:642–656.
[115] Fred Buckley,Marty Lewinter.《图论简明教程》.李慧霸王凤芹译.北京:清华大学出版社.2005年
[116] Byeong Moon Kim, Byung Chul Song, Woonjae Hwang. Nonnegative primitivematrices with exponent2. Linear Algebra and its Applications,2005,407:162-168.
[117] Byeong Moon Kim, Byung Chul Song, Woonjae Hwang, Primitive graphs with givenexponents and minimum number of edges. Linear Algebra and its Applications2007,420:648-662.
[118] G. MacGillivray, S. Nasserasr, D.D. Olesky, P. van den Driessche,Primitive digraphswith smallest large exponent. Linear Algebra and its Applications,2008,428:1740-1752.
[119] Jian Shen, Stewart Neufeld, Local exponents of primitive digraphs. LinearAlgebra andits Applications,1998,268:117-129.
[120] Yang Shangjun, George P. Barker, On the exponent of a primitive, minimally strongdigraph. Linear Algebra and its Applications,1988,99:177-198.
[121] Jian Shen, Proof of a conjecture about the exponent of primitive matrices. LinearAlge-bra and its Applications,1995,216:185-203.
[122] Zhang Ke Min, On Lewin and Vitek's conjecture about the exponent set of primitivematrices.Linear Algebra and its Applications,1987,96:101-108.
[123] Zhengke Miao, Kemin Zhang. The local exponent sets of primitive digraphs.LinearAlgebra and its Applications,2000,307:15-33.
[124] Jian Shen, A problem on the exponent of primitive digraphs.Linear Algebra and itsApplications,1996,244:255-264.
[125] Mordechai Lewin and Yehoshua Vitek, A system of gaps in the exponent set ofprimitive matrices. Illinois. Math.1981,25:87-98.
[126] R.K. Ahuja, T.L. Magnanti, J.B. Orlin. Network Flows: Theory, Algorithms andApplications, Prentice-Hall,1993.
[127] R.K. Ahuja, K. Mehlhorn, J.B. Orlin, R.E. Tarjan, Faster algorithms for the shortestpath problem, J. ACM37(2)(April1990)213-223.
[128] D. Chakrabarti, Y. Zhan, C. Faloutsos, R-MAT:Arecursive model for graph mining, in:Proc.4th SIAM Intl. Conf. on Data Mining, Florida, USA, April.2004.
[129] E.W. Dijkstra, A note on two problems in connexion with graphs, Numer. Math.1959,1:269-271.
[130] T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduction to Algorithms, MITPress,2001.
[131] J.R. Driscoll, H.N. Gabow, R. Shrairman, R.E. Tarjan, Relaxed heaps:An alternative toFibonacci heaps with applications to parallel computation, Commun.ACM1988,31(11):1343-1354.
[132] A.V. Goldberg, A simple shortest path algorithm with linear average time, in:9th Ann.European Symp. on Algorithms (ESA2001), Aachen, Germany,in: Lecture Notes inComputer Science, vol.2161, Springer,2001, pp.230–241.
[133] M.L. Fredman, R.E. Tarjan, Fibonacci heaps and their uses in improved networkoptimization algorithms. ACM1987,34(3):596–615.
[134] M.L. Fredman, D.E. Willard, Trans-dichotomous algorithms for minimum spanningtrees and shortest paths. Comput. Syst. Sci.1994,48(3):533-551.
[135] H.F. Taylor, Balance in Small Groups, Van Nostrand Reinhold, New York,1976.
[136] Mahmud Akelbek,Steve Kirkland.Coefficients of ergodicity and the scrambling index.Linear Algebra and its Applications,2009,430:1111-1130.
[137] B.Zhou,J.Shen,On generalized exponents of tournaments,Taiwanese J.Math.2002,6:565-527.
[138] J. Cort′es, S. Mart′nez, and F. Bullo,“Robust rendezvous for mobile autonomousagents via proximity graph in arbitrary dimensions,” IEEE Transactions on AutomaticControl, Aug.2006,51(8):1289-1298,
[139] L. Moreau,“Stability of multi-agent systems with time-dependent communicationlinks,” IEEE Transactions on Automatic Control, Feb.2005.50(2):169–182,
[140] W. Ren and R. W. Beard,“Consensus seeking in multiagent systems under dynamicallychanging interaction topologies,” IEEE Transactions on Automatic Control, May2005,50(5):655–661,.
[141] A.L.Dulmage,N.S.Mendelsohn.Gaps in the exponent set of primitive matrices.Illinois.J.Math.1964,8:642-656.
[142] Z.Li, F.Hall, J.Stuart. Irreducible powerful ray pattern matrices Linear Algebra and itsApplications.2002,342:47-58.
[143]胡红萍.图与矩阵的组合理论及其网络应用.中北大学博士论文,2009:12-17.
[144]黄廷祝、杨传盛.特殊矩阵分析及应用.科学出版社,2007.
[145] A.L. Dulmage and N.S. Mendelsohn. Graphs and matrices, graph theory and theoretic-al physics. F. Harary. Academic Press,1967,167-277.
[146]哈拉里著;李慰萱译.图论.上海科学技术出版社,1980.01.
[147] R.K.Ahuja, K. Mehlhorn, J.B. Orlin, R.E. TarjanFaster algorithms for the shortest pathproblem J. ACM,37(2)(April1990), pp.213–223
[148]曹汝成.组合数学.华南理工大学出版社,2000.
[149] BENJAMIN F Z.Three Fastest Shortest PathAlgorithms on Real Road Networks. Jou-rnal of Geographic Information and Decision Analysis,1997(1):69-82.
[150] S Baswana,R Hariharan,S Sen.Improved decremental algorithms for transitive closureand all-pairs shortest paths[C] Proc·34th ACM Symposium Theory of Computing,2002.