在图论和理论计算机科学中有很多关于路径的问题，例如最长(短)路径问题是指在给定的图中找出一条最长(短)的简单路径．k-path问题是指在给定的图中找出一条长度为k的简单路径，是最长路径问题的一种特殊情况．在无向图中求解最长路径问题是著名的NP难问题[1]，目前主要有多项式时间近似算法[2]、参数化算法[3]、特殊图的多项式时间算法[4]和其他一些优化算法[5]．哈密顿回路是指图中存在经过所有顶点一次的回路．哈密顿回路是NP完全问题，目前无法得到一个图含有哈密顿回路的充要条件，也还没有求哈密顿回路的简洁有效的算法[6]．现有对于哈密顿回路问题的研究主要集中在对图作限制后，研究哈密顿回路的存在性或在图中找一条哈密顿回路[7]，虽然其中一些是对有向图的研究，但也都是指数级时间复杂度[8-9]．目前这些算法及改进算法主要集中在算法程序设计的实现及计算程序的时间复杂度上．一个简单图对应一个邻接矩阵或关联矩阵．文献[10]通过邻接矩阵和马尔科夫链的方法来求最短路径；文献[11]通过矩阵乘法给出了路径查询的方法；文献[12]通过平行矩阵算法解决了大数据环境下最短路径问题；文献[13]利用矩阵的循环移位变换，构造集合的笛卡儿积来求最短路线和最短距离；文献[14]基于对图的关联矩阵分析，给出了哈密顿图的充分条件而且可以找出所有哈密顿回路；文献[15]定义了图的赋权路径矩阵并用于解决最短路径问题，但不能解决其他路径问题．本研究引入初始路径运算矩阵和一般路径运算矩阵的概念并定义加法与乘法运算来解决以上有关路径问题，只须经过矩阵运算，结果就显示在最终的一般路径运算矩阵上，这种纯数学方法使计算结果更直观且便于运算．1 图的路径运算矩阵及加法运算设简单图G=V,E，其中V和E分别为图G的点集与边集的集合，|V|=n，矩阵A=(aij)n×n为简单图G的邻接矩阵，其中aij=1    (eij∈E);0    (eij∉E).定义1 设简单图G的邻接矩阵为A=(aij)n×n，定义一个n阶矩阵P=(pij)n×n，pij=ij    (aij=1);0    (aij=0),则称矩阵P为简单图G的初始路径运算矩阵．定义2 称矩阵Q=(qij)m×n为简单图的一般路径运算矩阵，其中qij为在某约定条件下第i个顶点与第j个顶点之间的某一条或几条路径，如果此条件下第i个顶点与第j个顶点之间没有路径，则记qij=0．一般路径运算矩阵不一定是方阵，当m=1或n=1时也称行向量或者列向量．初始路径运算矩阵是一般路径运算矩阵的特殊情况，简称为路径运算矩阵，qij为路径运算矩阵Q的元素或路径元素．这里的路径又称初级通路(简单通路)，即简单图中满足通路上所有顶点(除起点、终点外)各异的通路．当qij表示多条路径时，用符号⊕表示具有相同起点与终点的不同路径的加法运算(实际为并运算)．定义3 设矩阵Q为简单图的路径运算矩阵，其中qij对应的所有路径最大长度称为qij的长度，元素0的长度为0，矩阵Q中所有元素长度的最大值称为矩阵Q的长度．特别地，初始路径矩阵长度为1．规定路径运算矩阵中具有相同起点与终点的不同路径的书写顺序按长度从小到大排列，具有相同长度的按数字的字典顺序排列．定义4 路径运算矩阵中某路径元素的反向排列路径称为该元素的一个逆序，起点与终点相同的一对逆序表示两个不同的路径，当它们相加表示同一元素时(无向图情形)，按字典顺序排列，用前一个元素表示．定义5 若一个路径运算矩阵Q中每个元素都为0，则称这个路径运算矩阵为长度为0的路径运算矩阵，记为Θ．定义6 设F=(fij)与G=(gij)为m×n路径运算矩阵，定义两个矩阵的加法为F⊕G=(fij⊕gij)，特别地，fij⊕0=fij，0⊕gij=gij，fij⊕fij=fij，0⊕0=0.以上定义的两个路径运算矩阵之间的加法可以推广到多个路径运算矩阵，并且容易推出这样定义的加法满足交换律与结合律．2 路径运算矩阵的乘法运算定义7 设F为m×s路径运算矩阵，G为s×n路径运算矩阵，定义两路径fik与gkj的乘积为连接顶点i，k，j之间的两路径的拼接(不含重复顶点)，记为hij=fik⊗gkj．若hij对应的两路径拼接通路中含有两个相同的顶点(首尾两个顶点相同的除外)，则去掉这个路径(或记为0)，选择不含有重复顶点的路径，若都是含有重复顶点的路径，则hij=0．例如，若fik=iqk，gkj=kj，则当i，q，k，j互不相同时，fik⊗gkj=iqk⊗kj=iqkj；当i，q，k，j至少有两个数字相同时，fik⊗gkj=0．规定对任意fik和gkj，fik⊗0=0⊗gkj=0⊗0=0．定义8(路径加法对乘法的分配率) 规定：(fik⊕gik)⊗hkj=(fik⊗hkj)⊕(gik⊗hkj)；fik⊗(gkj⊕hkj)=(fik⊗gkj)⊕(fik⊗hkj).定义9(路径运算矩阵乘法) 设F为m×s路径运算矩阵，G为s×n路径运算矩阵，那么规定矩阵F与G的乘法运算为m×n路径运算矩阵H=(hij)，即F⊗G=H，其中hij=(fi1⊗g1j)⊕(fi2⊗g2j)⊕…⊕(fis⊗gsj)(i=1，2，…，m；j=1，2，…，n)，当F=G且为方阵时，记F2=F⊗F．易证明该定义的路径矩阵乘法满足结合律．性质1(路径运算矩阵乘法的结合率) 设F，G和R为3个路径运算矩阵，假设路径运算矩阵的乘法运算可行，则有(F⊗G)⊗R=F⊗(G⊗R)．定义10 设F为路径运算方阵，对于任意正整数k(k1)，规定Fk=Fk-1⊗F．当F=P时，相应地有P2和Pk．由定义7得到fii⊗gij=fij⊗gjj=0，所以定义9可以改进为以下定义．定义11(路径运算矩阵快速乘法) 设F为m×s路径运算矩阵，G为s×n路径运算矩阵，规定矩阵F与G的乘法运算为m×n路径矩阵H=F⊗G=(hij)，其中：h1j=(f12⊗g2j)⊕(f13⊗g3j)⊕…⊕(f1s⊗gsj)(j=1，2，…，n)；hi1=(fi2⊗g21)⊕(fi3⊗g31)⊕…⊕(fis⊗gs1)(i=1，2，…，m)；hij=(fi1⊗g1j)⊕(fi2⊗g2j)⊕…⊕(fi(i-1)⊗g(i-1)j)⊕(fi(i+1)⊗g(i+1)j)⊕…⊕(fis⊗gsj)(i=2，3，…，m；j=2，3，…，n).3 简单图有关路径问题算法3.1　简单图最长路径问题算法定理1 若矩阵P=(pij)n×n为简单图的初始路径运算矩阵，则P是长度为1的矩阵，P2是长度为2的路径运算矩阵或者是Θ矩阵，以此类推，存在最小正整数m(m1)，使得Pm≠Θ，而Pm+1=Pm+2=…=Θ．此时矩阵Pm的长度为m，即一定存在长度为m的最长路径．证明 若矩阵P为简单图的初始路径矩阵，则由定义3可知，P是长度为1的矩阵，由定义7～9可知，矩阵P2中元素的路径长度只能是0或者2，若所有元素的路径长度为0，则P2=Θ，此时m=1，否则P2是长度为2的路径矩阵．类似地，若P2≠Θ，则P3中元素的路径长度只能是0或者3，若所有元素的路径长度为0，则P3=Θ，此时m=2，否则P3是长度为3的路径矩阵．以此类推，随着幂次的增加，两点之间的路径长度在单调增加，由于这是一个简单图，任意两点之间联通的路径长度是有限的，因此存在最小正整数m，使Pm≠Θ，而Pm+1=Pm+2=…=Θ，即存在最小正整数m，使Pm是长度为m的路径运算矩阵，而Pm+1是长度为0的路径运算矩阵，从而这个简单图存在长度为m的最长路径．定义12 设矩阵P为简单图的初始路径运算矩阵，若存在最小正整数m(m1)，使Pm≠Θ，Pm+1=Θ，则称m为矩阵P的幂长．由定义12和定理1可知，简单图的初始路径运算矩阵P的幂长即为其最长路径的长度，矩阵Pm中每个元素的长度不为0即为m，长度为m的元素所对应的路径即为这两点之间的最长路径．若给定第i个顶点与第j个顶点，求这两点之间的最长路径，则记矩阵P的第i行为向量Pi，若将其与P连续相乘直到第j列的元素不为0，而与P再乘一次第j列的元素即为0，则之前不为0的元素对应的路径即为从第i点与第j个点之间最长路径．由定理1可知，当初始路径运算矩阵P的幂长m=n-1时，最长路径为哈密顿路径；当P的幂长m=n时，最长路径为哈密顿回路．3.2　简单图最短路径问题算法设矩阵P为简单图的初始路径运算矩阵，若给定第i个顶点与第j个顶点，求两点之间最短路径，则当pij≠0时，第i个顶点与第j个顶点之间的最短路径为pij；当pij=0时，记矩阵P的第i行为向量Pi，若将其与P连续相乘直到第j列的元素刚好不为0，则此时不为0的元素对应的路径即为从第i个顶点与第j个顶点之间的所有最短路径．3.3　简单图具有长度约束的路径问题推论1 若简单图的初始路径运算矩阵P的幂长为m，则对任意正整数k(1≤k≤m)，Pk的长度为k，即矩阵Pk存在长度为k的路径k-path．利用推论1可以解决简单图的k-path问题，即可求长度为k的所有路径，它是矩阵Pk中长度为k的元素所对应的所有路径．要求任意两顶点i与j之间具有长度为k约束的所有路径，记矩阵P的第i行为向量Pi，将其与P连续k-1次相乘，若最后这个行向量中第j个元素为0，则不存在长度为k约束的路径；若不为0，则其对应的路径即为第i个顶点到第j个顶点的长度为k约束的所有路径．3.4　简单图任意两点间的简单通路问题利用简单图的邻接矩阵可以判断该图是否联通，但是在联通的条件下却不能直接得出联通的所有路径．利用推论1得出如下推论．推论2 若简单图的初始路径运算矩阵P的幂长为m，则和矩阵∑k=1mPk=P⊕P2⊕⋯⊕Pm中第i行与第j列元素为0表示第i点与第j点之间是不联通的或不存在简单通路，第i行与第j列元素不为0表示第i点与第j点之间是联通的且存在相应长度的简单通路．若除对角线元素以外的所有元素都不为0，则该图是联通图．3.5　简单图的回路和哈密顿回路问题推论3 若简单图的初始路径运算矩阵为P，则这个简单图存在路径长度为k的回路的充要条件是矩阵Pk的对角线元素中有k个长度为k的元素．由推论3可知，设矩阵P为简单图的初始路径运算矩阵，若求长度为k的回路，则只须计算矩阵Pk的对角线元素，若求所有不同长度的回路，则根据推论2，计算矩阵∑k=2mPk的对角线元素．推论4 设简单图G的初始路径运算矩阵为P，这个简单图存在哈密顿回路的充要条件是矩阵Pn的对角线元素是n个路径长度为n的元素．定义13 若两路径fij与gji(i≠j)的乘积hii=fij⊗gji表示一条哈密顿回路，则称fij与gji为一对逆元．定理2 若简单图G的初始路径运算矩阵为P，|V|=n，则这个简单图存在哈密顿回路的充要条件是矩阵P(n-1)/2与P(n+1)/2(n是奇数)或Pn/2自身(n是偶数)除对角线元素外至少有一对元素互为逆元．证明 这个简单图存在一条哈密顿回路，不妨设为1 j2j3…jn1(这里j2j3…jn是2，3，…，n的排列)．若n为奇数，则有1 j2j3…jn1=1 j2j3…j(n+1)/2⊗ j(n+1)/2j(n+3)/2…jn1，其中路径1 j2j3…j(n+1)/2的长度为(n-1)/2，是矩阵P(n-1)/2中第一行第j(n+1)/2列的元素，而路径j(n+1)/2j(n+3)/2…jn1的长度为(n+1)/2，是矩阵P(n+1)/2中第j(n+1)/2行第一列的元素，它们互为逆元．若n为偶数，则有1 j2j3…jn1=1 j2j3…jn/2+1⊗ jn/2+1jn/2+2…jn1，其中路径1 j2j3…jn/2+1的长度为n/2，是矩阵Pn/2中第一行第jn/2+1列的元素，而路径jn/2+1jn/2+2…jn1的长度为n/2，是矩阵Pn/2中第jn/2+1行第一列的元素，它们互为逆元．反过来，若这两个矩阵除对角线元素外至少有一对元素互为逆元，则这两个元素对应的路径乘积表示一条哈密顿回路，由性质1可得Pn=P(n-1)/2⊗P(n+1)/2    (n为奇数);Pn/2⊗Pn/2    (n为偶数),即这个简单图存在哈密顿回路．推论5 设简单图G的初始路径运算矩阵为P，若路径矩阵Pk(当n为奇数时，1≤k≤(n+1)/2；当n为偶数时，1≤k≤n/2)除对角线元素外有一行或一列元素为0，则这个简单图不存在哈密顿回路．记P的第一行为P11，定义P1k=P1k-1⊗P(k1)，P1k为矩阵Pk的第一行，Q1k为矩阵Pk的第一列，由性质1可知，Q1k=P⊗Q1k-1=Pk-1⊗Q11．推论6 设简单图G的初始路径运算矩阵为P，如果这个简单图存在哈密顿回路，那么矩阵P1(n-1)/2⊗Q1(n+1)/2或P1(n+1)/2⊗Q1(n-1)/2(n为奇数)或P1n/2⊗Q1n/2(n为偶数)表示所有哈密顿回路．对于无向图，路径运算矩阵中第1行第j(j1)列的元素与第j行第1列的元素互为逆序，所以向量Q1(n+1)/2和Q1n/2的结果可以通过向量P1(n+1)/2和P1n/2得到，从而简化计算．3.6　简单图哈密顿回路的计算时间复杂度分析以简单无向图为例，假设有n个顶点，且n为大于4的偶数．步骤1 计算P12，根据P12=P11⊗P，由定义11，须将P11中的n-1个元素(第一个元素除外)与P中每一列做n-1次乘法运算，P有n列，所以总运算次数为n(n-1)．步骤2 计算P13，根据P13=P12⊗P，须将P12中的n-1个元素对P中每一列做n-1次乘法运算，这时P12中每一个元素长度为2，最多有An-21种可能，所以最多运算次数为An-21n(n-1)．步骤3 计算P14，根据P14=P13⊗P，须将P13中的n-1个元素对P中每一列做n-1次乘法运算，这时P13中每一个元素长度为3，最多有An-22种可能，所以最多运算次数为An-22n(n-1)．以此类推，第n/2-1步计算P1n/2，根据P1n/2=P1n/2-1⊗P，须将P1n/2-1中的n-1个元素对P中每一列做n-1次乘法运算，这时P1n/2-1中每一个元素长度为n/2-1，有An-2n/2-2种可能，所以最多运算次数为An-2n/2-2n(n-1)．第n/2步由P1n/2得到Q1n/2，根据P1n/2⊗Q1n/2，须将P1n/2中的n-1个元素对Q1n/2中n-1个元素做乘法运算，这时P1n/2中每一个元素长度为n/2，有An-2n/2-1种可能，所以最多有运算次数为An-2n/2-1(n-1)．矩阵乘法运算的总时间复杂度为n(n-1)+An-21n(n-1)+An-22n(n-1)+⋯+An-2n/2-2n(n-1)+An-2n/2-1(n-1)n(n-1)n/2An-2n/2-2+(n-1)An-2n/2-1(n+1)(n-1)!/(n/2-1)!(n-1)(n-1)!≤n!-(n-1)!.上述分析中计算复杂度没有超过文献[6]中的计算复杂度．对于简单无向图，当n为偶数时只须经过n/2-1步向量与方阵的乘法运算和一步向量与向量的运算即可得到所有哈密顿回路．类似可以得出：当n为奇数时只须经过(n-1)/2步向量与方阵的乘法运算和一步向量与向量的运算即可得到所有哈密顿回路，计算量是Pn计算量的1/(2n)．对于简单有向图，当n为偶数时要计算P1n/2和Q1n/2，当n为奇数时要计算P1(n+1)/2和Q1(n-1)/2，计算量是Pn计算量的1/n．矩阵P1k和Q1k中每个元素可能个数比无向图的情形要少很多，所以实际计算量会大大减少．本算法计算量约为其他矩阵方法计算量的1/n．4 结语给出了简单图的初始路径运算矩阵和一般路径运算矩阵的定义，并定义了一般路径运算矩阵的加法与乘法运算，利用路径运算矩阵的乘法可以求简单图的最长路、最短路、任意两点之间的通路及具有长度约束的路径问题．本算法还可以检测简单图哈密顿回路及计算所有哈密顿回路，结果均显示在最后的路径运算矩阵上，为图论相关路径问题研究提供了一个新的方法，且计算量大大减少．