您的位置：首页 > 范文大全 > 公文范文公文范文
带故障边的路和圈的笛卡尔乘积图的哈密尔顿路
2025-08-24人已围观
带故障边的路和圈的笛卡尔乘积图的哈密尔顿路
姜璎哲,李 晶
(太原科技大学 应用科学学院,太原 030024)
在并行计算机系统中并行处理的核心问题之一是如何将线性阵列和环嵌入其底层互连网络拓扑中。嵌入是一个拓扑结构到另一个拓扑结构的映射,嵌入线性阵列和环与图论中的路和圈嵌入问题密切相关[1]。哈密尔顿路和圈的嵌入研究是互连网络拓扑性质研究的热点之一。
近年来,关于互连网络的容错哈密尔顿路和圈的嵌入问题的研究,学者们已经在各种互连网络上取得了很多相关成果:Chen等[2]提出了在m×n网格中寻找哈密顿路的线性时间算法;Park等[3]证明了具有一条故障边的笛卡尔乘积图Pm×Cn中,任意两个不同部中顶点u、v之间存在一条哈密尔顿路,其中m≥2,n≥4且n是偶数。基于该结果,学者们获得了有关二维和高维路和圈的笛卡尔乘积图的哈密尔顿路圈嵌入问题的一系列结论[4-5]。在文献[3]中,作者同时也证明了无故障Pm×Cn(n≥3且是奇数)是哈密尔顿连通的。然而,对具有一条故障边的Pm×Cn却没有类似的结论。本文就这一情况进行进一步探讨,对当m≥3且n≥5是奇数时,具有一条故障边的Pm×Cn的哈密尔顿路的存在情况进行刻画。通过对故障边位置的不同,对Pm×Cn中的哈密尔顿路的存在情况进行了讨论并得到3个相关结论。本文主要结论对具有一条故障边的笛卡尔乘积图Pm×Cn的哈密尔顿路问题进行了补充。同时,这些结论可以用作讨论高维奇圈笛卡尔乘积图的容错哈密尔连通性的归纳基础。
路和圈的笛卡尔乘积图(简记为Pm×Cn)是由mn个顶点构成的。Pm×Cn的顶点集V={vij|1≤i≤m,1≤j≤n},边集E={Er∪Ec},其中,Er={(vij,vi,j+1)|1≤i≤m,1≤j≤n}∪{(vin,vi1|1≤i≤m},Ec={(vij,vi+1,j)|1≤i<m,1≤j≤n}.其中包含在Er中的边称为行边,包含在Ec中的边称为列边;将所有的行环绕边删去所生成的图记为M(m,n);将M(m,n)中的第一行和最后一行加入两条环绕边,记为M2(m,n)[6].见图1、图2.
图1 P3×C5
图2 M(3,5)和M2(3,5)
令G=Pm×Cn,定义R(i)与C(j)分别为第i行、第j列的点导出的G的子图,即R(i)=G{vij|1≤j≤n}、C(j)=G{vij|1≤i≤m}.令R(i∶i′)=G{vkj|i≤k≤i′,1≤j≤n},否则R(i∶i′)=φ.同样地,令C(j∶j′)=G{vik|1≤i≤m,j≤k≤j′},否则C(j,j′)=φ.显然,R(i∶j)与Pi-j+1×Cn同构,C(∶j)与Pj-1+1×Cm同构。包含Pm×Cn的每个顶点的路称为Pm×Cn的Hamilton路;类似地,Pm×Cn的Hamilton圈是指包含Pm×Cn的每一个顶点的圈。
为了方便证明,当i+j为奇数时称Pm×Cn中顶点vij为奇点;当i+j为偶数时称vij为偶点。定义集合[R1∶R2]={e|e∈(v1i,v2,i),1≤i≤m};[Rm-1∶Rm]={e|e∈(vm-1,i,vm,i),1≤i≤m}.
下面给出图Pm×Cn和M2(m,n)的两个性质,这些性质将在证明中被用到。
引理1[6]图M2(m,n)是哈密尔顿连通的,其中m≥2,n≥3且n是奇数。
引理2[7]图Pm×Cn是哈密尔顿连通的,其中m≥2,n≥3且n是奇数。
设f是Pm×Cn中一条故障边,其中m≥3且n≥5是奇数。根据故障边f的不同位置,分以下几种情况讨论。
引理1若f是一条列边,且f?[R1∶R2]∪[Rm-1∶Rn],则Pm×Cn-f是哈密尔顿连通的。
证明因为f是一条列边,且f?[R1∶R2]∪[Rm-1∶Rn],所以m≥4.不妨设f=(vi1,vi+1,1).令G1=R(1∶i),G2=R(i+1∶m).
注意到G1同构于Pi×Cn,G2同构于Pm-i×Cn,且i≥2,m-i≥2.由引理2,G1和G1都是哈密尔顿连通的。
设u、v是Pm×Cn-f中任意两个顶点,根据这两个点的位置,分两种情况讨论。
情形1u、v∈G1或u、v∈G2
由对称性,只需讨论u、v∈G1.因为G1是哈密尔顿连通的,所以在G1中存在从u到v的哈密尔顿路,设为P1.
因为n≥5,所以在R(i)上,除点u、v、vi1外,至少还有两个点,都是P1上的中间点。注意到这些点在G1中都与三条健康边关联,且其中两条都在R(i)上,故存在一个点vij,vij≠vi1,在R(i)上的关联边(v)ij,vi,j+1)也在P1上。
因为G2是哈密尔顿连通的,所以在G2中存在从vi+1,j到vi+1,j+1的一条哈密尔顿路P2.令P*=〈vij,vi+1,j,P2,vi+1,j+1,vi,j+1〉,则P1∪P*-(vij,vi,j+1)即为一条u到v的哈密尔顿路。见图3.
图3 引理1中情形1
情形2u∈G1,v∈G2
设vij是G1中R(i)上的点,满足vij≠u,vij≠vi1,且vi+1,j≠v.则G1有一条从u到vij的哈密尔顿路P1,G2有一条从vi+1,j到v的哈密尔顿路P2,即P=〈u,P1,vij,vi+1,j,P2,v〉为所求哈密尔顿路。见图4.
图4 引理1中情形2
证毕。
在给出引理2之前,首先给出一个例子。在图P3×C5中,边(v11,v21)是一条故障边,由于此时v11仅与两条健康边关联,则v12和v15之间不可能有哈密尔顿路。如图5.
图5 不存在从点v12到点v15的哈密尔顿路的实例
引理2若f是一条列边,且f∈[R1∶R2]∪[Rm-1∶Rn],则除了一种情况外,Pm×Cn-f是哈密尔顿连通的。
证明不失一般性设f=(v11,v21)∈[R1∶R2],显然Pm×Cn-f中不存在从点v12到v1n的哈密尔顿路。下证除这两点外,其余任意两点u、v之间仍然存在哈密尔顿路。
令G1=R(1),G2=R(2∶m).因为G2同构于Pm-1×Cn,且m-1≥2.由引理2,G2是哈密尔顿连通的。
情形1u、v∈G2
因为G2是哈密尔顿连通的,故G2有一条哈密尔顿路P1连接u、v,在R(2)上不难找到一条边e,使得e∈E(P1)且e不与v21关联。记e=(v2j,v2,j+1).令P2=Row(1)-(v1j,v1,j+1),则P=P1∪P2-e为所求哈密尔顿路。
情形2u∈G1,v∈G2
情形2.1u?{v11,v12}
记u=v1j,则u在R(1)上的两个邻点为v1,j-1,v1,j+1.这两个邻点都与f不关联且至少有一个在R(2)上的对应点不是v,不妨设v1,j-1满足条件。令P1=R(1)-(v1,j-1,u).显然,P1是G2中的哈密尔顿路,令P2是G2中一条从v2,j-1到v哈密尔顿路。则P=〈u,P1,v1,j-1,v2,j-1,P2,v〉为所求的哈密尔顿路,如图6.
图6 引理2中情形2.1
情形2.2u=v11
当v≠v2n时,如图7(a)所示,令P1=R(1)-(u,v1n),P2是G2中一条从v2n到v哈密尔顿路。则〈u,P1,v1n,v2n,P2,v〉即为所求哈密尔顿路。
图7 引理2中情形2.2
当v=v2n时,如图7(b)所示,在R(1∶2)-f中构造一条哈密尔顿路P1=〈u,v1n,v1,n-1,v2,n-1,v2,n-2,v1,n-2,…,v12,,v22,v21,v〉.此时,在R(3∶m)中存在连接v31到v32的哈密尔顿路P2.令P*=〈v21,v31,P2,v32,v22〉,此时,P=P1∪P*-(v21,v22)即为所求哈密尔顿路。
情形2.3u=v12
当v≠v23,令P1=R(1)-(v12,v13),P2是G2中从v23到v哈密尔顿路。则〈u,P1,v13,v23,P2,v〉即为所求哈密尔顿路。
当v=v23时,首先考虑m=3的情况。如图8所示,令P1=.可见P1经过了R(1∶2)中除v21,v22以外所有的点。令P2=〈v2,n-1,v3,n-1,v3,n-2,…,v32,v22,v21,v31,v3n,v2n〉.可见P2包含了R(3)上所有顶点和路P1未包含的点v21,v22.即P1∪P2-(v2,n-1,v2n)是连接u、v的哈密尔顿路。
图8 引理2中情形2.3 v=v23
当m≥4时,记上面构造的哈密尔顿路为P3,从R(3)∩P3上取一条边(v3j,v3,j+1)。由引理2知R(4∶m)中存在连接v4j、v4,j+1的哈密尔顿路P4,此时,将P3上的边(v3j,v3,j+1)用P4替换,可得到所求的哈密尔顿路。
情形3u、v∈G1
情形3.1u、v相邻
令P1=R(1)-(u,v).显然,P1是G1中的哈密尔顿路。取P1上的边(v1j,v1,j+1),用G2中一条从v2j到v2,j+1哈密尔顿路替换,即可得到所求的哈密尔顿路。
情形3.2u、v不相邻,且u=v11
设v=v1j,j≠2,n,如图9,令P1=〈u,v12,…,v1,j-1〉.因为G2是哈密尔顿连通的,故可设P2是G2中连接v2,j-1和v2n的哈密尔顿路。则〈u,P1,v1,j-1,v2,j-1,P2,v2n,v1n,v1,n-1,…,v〉即为所求的哈密尔顿路。
图9 引理2中情形3.2
不妨设u=u1i,v=v1j,且i<j.
当v≠v1n时,令P1=〈u,v1,i-1,…,v11,v1n,v1,n-1,…,v1,j+1〉,令P2是G2中从v2,j+1到v2,i+1的哈密尔顿路,则〈u,P1,v1,j+1,v2,j+1,P2,v2,i+1,v1,i+1,v1,i+2,…,v〉为所求的哈密尔顿路。见图10(a).
图10 引理2中情形3.3
当v=v1n时,注意此时u≠u12.令P1=〈u,v1,i+1,…,v1,n-1〉.令P2是G2中从v2,n-1到v2,i-1的哈密尔顿路,则〈u,P1,v2,n-1,P2,v2,i-1,v1,i-1,v1,i-2,…,v11,v〉为所求的哈密尔顿路。见图10(b).
证毕。
定理1设f是Pm×Cn中一条故障边,若f是一条列边,则除一种情况外,Pm×Cn-f是哈密尔顿连通的,其中m≥3且n≥5是奇数。
下面两个定理考虑f是行边的情况。
定理2若f是一条故障行边,且f?R(1)∪R(m),则Pm×Cn-f是哈密尔顿连通的,其中m≥3且n≥5是奇数。
证明注意到当f是一条行边且f?R(1)∪R(m)时,图M2(m,n)是Pm×Cn-f的生成子图。由引理1,M2(m,n)是哈密尔顿连通的,故Pm×Cn-f是哈密尔顿连通的。
证毕。
定理3若f是一条故障行边,且f∈R(1)∪R(m),则Pm×Cn-f中任意偶点与其他点之间存在哈密尔顿路,其中m≥3且n≥5是奇数。
情形1u、v∈G1
若点{u,v}≠{v1j,v2j},由于u是偶点,根据上面的讨论知G1中有一条连接u、v的哈密尔顿路P1.在R(2)∩P1上取一条边e1=(v2i,v2,i+1).令P2是G2中连接v3i和v3,i+1的哈密尔顿路。将P1上的e1用P2代替,可得到所求的哈密尔顿路。
首先构造当m=3时的哈密尔顿路。当u=v1j且v=v2j时,其中j是奇数,如图11(a)所示,可构造P3×Cn-f的哈密尔顿路。当u=v2j且v=v1j,其中j是偶数时,如图11(b)所示,可构造P3×Cn-f的哈密尔顿路。
图11 定理3中情形1
接下来,若m≥4,则在P2∩R(3)取边e2,用R(4∶m)上的哈密尔顿路代替e2,即可找到所求的从u到v的哈密尔顿路。
情形2u∈G1,v∈G2
若m≥4,在R(2)上找到一个点s,使得{u,s}≠{v1j,v2j},且s在在R(3)上的对应点不是v.令s=v2k,则G1中有从u到v2k的哈密尔顿路P1,G2中有从v3k到v的哈密尔顿路P2,连接P1和P2即为所求。
若m=3,则v∈R(3),且在R(3)上有两个邻点。选择其中一个邻点v3k使得v2k≠u且{u,v2k}≠{v1j,v2j}.则G1中有从u到v2k的哈密尔顿路P1,G2中有从v3k到v的哈密尔顿路P2,连接P1和P2即为所求。
情形3v∈G1,u∈G2
若m≥4,选取点v3k,其中k是偶数,使得v2k≠v且{v,v2k}≠{v1j,v2j}.因为v3k是奇点,则v3k≠u.进而G2中有从u到v3k的哈密尔顿路P2.因为v2k是G1中的偶点,故G1中有从v2k到v的哈密尔顿路P1.连接P1和P2即为所求。见图12(a).
图12 定理3中情形3
若m=3,则u∈R(3),且在R(3)上有两个奇邻点。选择其中一个奇邻点v3k使得v2k≠v且{v,v2k}≠{v1j,v2j}.则G1中有从v2k到v的哈密尔顿路P1,G2中有从u到v3k的哈密尔顿路P2,连接P1和P2即为所求。见图12(b).
情形4u、v∈G2
情形4.1m=3且u,v不相邻
图13 定理3中情形4.2
情形4.2m≥4或m=3且u,v相邻
令P2是G2中连接u,v的哈密尔顿路。在R
证毕。
猜你喜欢邻点所求奇数奇数凑20小猕猴智力画刊(2021年11期)2021-11-28奇数与偶数小学生学习指导(低年级)(2021年5期)2021-07-21围长为5的3-正则有向图的不交圈赤峰学院学报·自然科学版(2021年4期)2021-06-24无所求读写月报（初中版）(2021年12期)2021-05-25关于奇数阶二元子集的分离序列南京大学学报(数学半年刊)(2020年1期)2020-03-19感恩黄河之声(2016年24期)2016-02-03特殊图的一般邻点可区别全染色山西大同大学学报(自然科学版)(2016年6期)2016-01-30笛卡尔积图Pm×Kn及Cm×Kn的邻点可区别E-全染色研究长江大学学报(自科版)(2014年7期)2014-03-20边染色 9-临界图边数的新下界黑龙江科技大学学报(2010年5期)2010-09-23奇偶性 问题数学大世界·小学中高年级辅导版(2009年3期)2009-04-14
推荐访问:笛卡尔
哈密尔顿
乘积
姜璎哲,李 晶
(太原科技大学 应用科学学院,太原 030024)
在并行计算机系统中并行处理的核心问题之一是如何将线性阵列和环嵌入其底层互连网络拓扑中。嵌入是一个拓扑结构到另一个拓扑结构的映射,嵌入线性阵列和环与图论中的路和圈嵌入问题密切相关[1]。哈密尔顿路和圈的嵌入研究是互连网络拓扑性质研究的热点之一。
近年来,关于互连网络的容错哈密尔顿路和圈的嵌入问题的研究,学者们已经在各种互连网络上取得了很多相关成果:Chen等[2]提出了在m×n网格中寻找哈密顿路的线性时间算法;Park等[3]证明了具有一条故障边的笛卡尔乘积图Pm×Cn中,任意两个不同部中顶点u、v之间存在一条哈密尔顿路,其中m≥2,n≥4且n是偶数。基于该结果,学者们获得了有关二维和高维路和圈的笛卡尔乘积图的哈密尔顿路圈嵌入问题的一系列结论[4-5]。在文献[3]中,作者同时也证明了无故障Pm×Cn(n≥3且是奇数)是哈密尔顿连通的。然而,对具有一条故障边的Pm×Cn却没有类似的结论。本文就这一情况进行进一步探讨,对当m≥3且n≥5是奇数时,具有一条故障边的Pm×Cn的哈密尔顿路的存在情况进行刻画。通过对故障边位置的不同,对Pm×Cn中的哈密尔顿路的存在情况进行了讨论并得到3个相关结论。本文主要结论对具有一条故障边的笛卡尔乘积图Pm×Cn的哈密尔顿路问题进行了补充。同时,这些结论可以用作讨论高维奇圈笛卡尔乘积图的容错哈密尔连通性的归纳基础。
路和圈的笛卡尔乘积图(简记为Pm×Cn)是由mn个顶点构成的。Pm×Cn的顶点集V={vij|1≤i≤m,1≤j≤n},边集E={Er∪Ec},其中,Er={(vij,vi,j+1)|1≤i≤m,1≤j≤n}∪{(vin,vi1|1≤i≤m},Ec={(vij,vi+1,j)|1≤i<m,1≤j≤n}.其中包含在Er中的边称为行边,包含在Ec中的边称为列边;将所有的行环绕边删去所生成的图记为M(m,n);将M(m,n)中的第一行和最后一行加入两条环绕边,记为M2(m,n)[6].见图1、图2.
图1 P3×C5
图2 M(3,5)和M2(3,5)
令G=Pm×Cn,定义R(i)与C(j)分别为第i行、第j列的点导出的G的子图,即R(i)=G{vij|1≤j≤n}、C(j)=G{vij|1≤i≤m}.令R(i∶i′)=G{vkj|i≤k≤i′,1≤j≤n},否则R(i∶i′)=φ.同样地,令C(j∶j′)=G{vik|1≤i≤m,j≤k≤j′},否则C(j,j′)=φ.显然,R(i∶j)与Pi-j+1×Cn同构,C(∶j)与Pj-1+1×Cm同构。包含Pm×Cn的每个顶点的路称为Pm×Cn的Hamilton路;类似地,Pm×Cn的Hamilton圈是指包含Pm×Cn的每一个顶点的圈。
为了方便证明,当i+j为奇数时称Pm×Cn中顶点vij为奇点;当i+j为偶数时称vij为偶点。定义集合[R1∶R2]={e|e∈(v1i,v2,i),1≤i≤m};[Rm-1∶Rm]={e|e∈(vm-1,i,vm,i),1≤i≤m}.
下面给出图Pm×Cn和M2(m,n)的两个性质,这些性质将在证明中被用到。
引理1[6]图M2(m,n)是哈密尔顿连通的,其中m≥2,n≥3且n是奇数。
引理2[7]图Pm×Cn是哈密尔顿连通的,其中m≥2,n≥3且n是奇数。
设f是Pm×Cn中一条故障边,其中m≥3且n≥5是奇数。根据故障边f的不同位置,分以下几种情况讨论。
引理1若f是一条列边,且f?[R1∶R2]∪[Rm-1∶Rn],则Pm×Cn-f是哈密尔顿连通的。
证明因为f是一条列边,且f?[R1∶R2]∪[Rm-1∶Rn],所以m≥4.不妨设f=(vi1,vi+1,1).令G1=R(1∶i),G2=R(i+1∶m).
注意到G1同构于Pi×Cn,G2同构于Pm-i×Cn,且i≥2,m-i≥2.由引理2,G1和G1都是哈密尔顿连通的。
设u、v是Pm×Cn-f中任意两个顶点,根据这两个点的位置,分两种情况讨论。
情形1u、v∈G1或u、v∈G2
由对称性,只需讨论u、v∈G1.因为G1是哈密尔顿连通的,所以在G1中存在从u到v的哈密尔顿路,设为P1.
因为n≥5,所以在R(i)上,除点u、v、vi1外,至少还有两个点,都是P1上的中间点。注意到这些点在G1中都与三条健康边关联,且其中两条都在R(i)上,故存在一个点vij,vij≠vi1,在R(i)上的关联边(v)ij,vi,j+1)也在P1上。
因为G2是哈密尔顿连通的,所以在G2中存在从vi+1,j到vi+1,j+1的一条哈密尔顿路P2.令P*=〈vij,vi+1,j,P2,vi+1,j+1,vi,j+1〉,则P1∪P*-(vij,vi,j+1)即为一条u到v的哈密尔顿路。见图3.
图3 引理1中情形1
情形2u∈G1,v∈G2
设vij是G1中R(i)上的点,满足vij≠u,vij≠vi1,且vi+1,j≠v.则G1有一条从u到vij的哈密尔顿路P1,G2有一条从vi+1,j到v的哈密尔顿路P2,即P=〈u,P1,vij,vi+1,j,P2,v〉为所求哈密尔顿路。见图4.
图4 引理1中情形2
证毕。
在给出引理2之前,首先给出一个例子。在图P3×C5中,边(v11,v21)是一条故障边,由于此时v11仅与两条健康边关联,则v12和v15之间不可能有哈密尔顿路。如图5.
图5 不存在从点v12到点v15的哈密尔顿路的实例
引理2若f是一条列边,且f∈[R1∶R2]∪[Rm-1∶Rn],则除了一种情况外,Pm×Cn-f是哈密尔顿连通的。
证明不失一般性设f=(v11,v21)∈[R1∶R2],显然Pm×Cn-f中不存在从点v12到v1n的哈密尔顿路。下证除这两点外,其余任意两点u、v之间仍然存在哈密尔顿路。
令G1=R(1),G2=R(2∶m).因为G2同构于Pm-1×Cn,且m-1≥2.由引理2,G2是哈密尔顿连通的。
情形1u、v∈G2
因为G2是哈密尔顿连通的,故G2有一条哈密尔顿路P1连接u、v,在R(2)上不难找到一条边e,使得e∈E(P1)且e不与v21关联。记e=(v2j,v2,j+1).令P2=Row(1)-(v1j,v1,j+1),则P=P1∪P2-e为所求哈密尔顿路。
情形2u∈G1,v∈G2
情形2.1u?{v11,v12}
记u=v1j,则u在R(1)上的两个邻点为v1,j-1,v1,j+1.这两个邻点都与f不关联且至少有一个在R(2)上的对应点不是v,不妨设v1,j-1满足条件。令P1=R(1)-(v1,j-1,u).显然,P1是G2中的哈密尔顿路,令P2是G2中一条从v2,j-1到v哈密尔顿路。则P=〈u,P1,v1,j-1,v2,j-1,P2,v〉为所求的哈密尔顿路,如图6.
图6 引理2中情形2.1
情形2.2u=v11
当v≠v2n时,如图7(a)所示,令P1=R(1)-(u,v1n),P2是G2中一条从v2n到v哈密尔顿路。则〈u,P1,v1n,v2n,P2,v〉即为所求哈密尔顿路。
图7 引理2中情形2.2
当v=v2n时,如图7(b)所示,在R(1∶2)-f中构造一条哈密尔顿路P1=〈u,v1n,v1,n-1,v2,n-1,v2,n-2,v1,n-2,…,v12,,v22,v21,v〉.此时,在R(3∶m)中存在连接v31到v32的哈密尔顿路P2.令P*=〈v21,v31,P2,v32,v22〉,此时,P=P1∪P*-(v21,v22)即为所求哈密尔顿路。
情形2.3u=v12
当v≠v23,令P1=R(1)-(v12,v13),P2是G2中从v23到v哈密尔顿路。则〈u,P1,v13,v23,P2,v〉即为所求哈密尔顿路。
当v=v23时,首先考虑m=3的情况。如图8所示,令P1=.可见P1经过了R(1∶2)中除v21,v22以外所有的点。令P2=〈v2,n-1,v3,n-1,v3,n-2,…,v32,v22,v21,v31,v3n,v2n〉.可见P2包含了R(3)上所有顶点和路P1未包含的点v21,v22.即P1∪P2-(v2,n-1,v2n)是连接u、v的哈密尔顿路。
图8 引理2中情形2.3 v=v23
当m≥4时,记上面构造的哈密尔顿路为P3,从R(3)∩P3上取一条边(v3j,v3,j+1)。由引理2知R(4∶m)中存在连接v4j、v4,j+1的哈密尔顿路P4,此时,将P3上的边(v3j,v3,j+1)用P4替换,可得到所求的哈密尔顿路。
情形3u、v∈G1
情形3.1u、v相邻
令P1=R(1)-(u,v).显然,P1是G1中的哈密尔顿路。取P1上的边(v1j,v1,j+1),用G2中一条从v2j到v2,j+1哈密尔顿路替换,即可得到所求的哈密尔顿路。
情形3.2u、v不相邻,且u=v11
设v=v1j,j≠2,n,如图9,令P1=〈u,v12,…,v1,j-1〉.因为G2是哈密尔顿连通的,故可设P2是G2中连接v2,j-1和v2n的哈密尔顿路。则〈u,P1,v1,j-1,v2,j-1,P2,v2n,v1n,v1,n-1,…,v〉即为所求的哈密尔顿路。
图9 引理2中情形3.2
不妨设u=u1i,v=v1j,且i<j.
当v≠v1n时,令P1=〈u,v1,i-1,…,v11,v1n,v1,n-1,…,v1,j+1〉,令P2是G2中从v2,j+1到v2,i+1的哈密尔顿路,则〈u,P1,v1,j+1,v2,j+1,P2,v2,i+1,v1,i+1,v1,i+2,…,v〉为所求的哈密尔顿路。见图10(a).
图10 引理2中情形3.3
当v=v1n时,注意此时u≠u12.令P1=〈u,v1,i+1,…,v1,n-1〉.令P2是G2中从v2,n-1到v2,i-1的哈密尔顿路,则〈u,P1,v2,n-1,P2,v2,i-1,v1,i-1,v1,i-2,…,v11,v〉为所求的哈密尔顿路。见图10(b).
证毕。
定理1设f是Pm×Cn中一条故障边,若f是一条列边,则除一种情况外,Pm×Cn-f是哈密尔顿连通的,其中m≥3且n≥5是奇数。
下面两个定理考虑f是行边的情况。
定理2若f是一条故障行边,且f?R(1)∪R(m),则Pm×Cn-f是哈密尔顿连通的,其中m≥3且n≥5是奇数。
证明注意到当f是一条行边且f?R(1)∪R(m)时,图M2(m,n)是Pm×Cn-f的生成子图。由引理1,M2(m,n)是哈密尔顿连通的,故Pm×Cn-f是哈密尔顿连通的。
证毕。
定理3若f是一条故障行边,且f∈R(1)∪R(m),则Pm×Cn-f中任意偶点与其他点之间存在哈密尔顿路,其中m≥3且n≥5是奇数。
情形1u、v∈G1
若点{u,v}≠{v1j,v2j},由于u是偶点,根据上面的讨论知G1中有一条连接u、v的哈密尔顿路P1.在R(2)∩P1上取一条边e1=(v2i,v2,i+1).令P2是G2中连接v3i和v3,i+1的哈密尔顿路。将P1上的e1用P2代替,可得到所求的哈密尔顿路。
首先构造当m=3时的哈密尔顿路。当u=v1j且v=v2j时,其中j是奇数,如图11(a)所示,可构造P3×Cn-f的哈密尔顿路。当u=v2j且v=v1j,其中j是偶数时,如图11(b)所示,可构造P3×Cn-f的哈密尔顿路。
图11 定理3中情形1
接下来,若m≥4,则在P2∩R(3)取边e2,用R(4∶m)上的哈密尔顿路代替e2,即可找到所求的从u到v的哈密尔顿路。
情形2u∈G1,v∈G2
若m≥4,在R(2)上找到一个点s,使得{u,s}≠{v1j,v2j},且s在在R(3)上的对应点不是v.令s=v2k,则G1中有从u到v2k的哈密尔顿路P1,G2中有从v3k到v的哈密尔顿路P2,连接P1和P2即为所求。
若m=3,则v∈R(3),且在R(3)上有两个邻点。选择其中一个邻点v3k使得v2k≠u且{u,v2k}≠{v1j,v2j}.则G1中有从u到v2k的哈密尔顿路P1,G2中有从v3k到v的哈密尔顿路P2,连接P1和P2即为所求。
情形3v∈G1,u∈G2
若m≥4,选取点v3k,其中k是偶数,使得v2k≠v且{v,v2k}≠{v1j,v2j}.因为v3k是奇点,则v3k≠u.进而G2中有从u到v3k的哈密尔顿路P2.因为v2k是G1中的偶点,故G1中有从v2k到v的哈密尔顿路P1.连接P1和P2即为所求。见图12(a).
图12 定理3中情形3
若m=3,则u∈R(3),且在R(3)上有两个奇邻点。选择其中一个奇邻点v3k使得v2k≠v且{v,v2k}≠{v1j,v2j}.则G1中有从v2k到v的哈密尔顿路P1,G2中有从u到v3k的哈密尔顿路P2,连接P1和P2即为所求。见图12(b).
情形4u、v∈G2
情形4.1m=3且u,v不相邻
图13 定理3中情形4.2
情形4.2m≥4或m=3且u,v相邻
令P2是G2中连接u,v的哈密尔顿路。在R
证毕。
猜你喜欢邻点所求奇数奇数凑20小猕猴智力画刊(2021年11期)2021-11-28奇数与偶数小学生学习指导(低年级)(2021年5期)2021-07-21围长为5的3-正则有向图的不交圈赤峰学院学报·自然科学版(2021年4期)2021-06-24无所求读写月报（初中版）(2021年12期)2021-05-25关于奇数阶二元子集的分离序列南京大学学报(数学半年刊)(2020年1期)2020-03-19感恩黄河之声(2016年24期)2016-02-03特殊图的一般邻点可区别全染色山西大同大学学报(自然科学版)(2016年6期)2016-01-30笛卡尔积图Pm×Kn及Cm×Kn的邻点可区别E-全染色研究长江大学学报(自科版)(2014年7期)2014-03-20边染色 9-临界图边数的新下界黑龙江科技大学学报(2010年5期)2010-09-23奇偶性 问题数学大世界·小学中高年级辅导版(2009年3期)2009-04-14
推荐访问:笛卡尔
哈密尔顿
乘积