字典乘积图的Euler性

2023年12月22日发(作者：佛山期末初三数学试卷)

字典乘积图的Euler性

李峰;梁栋;徐宗本

【摘 要】It is found in practice that some properties of the network

topological structure can measure the function of a network, and the

network reliability is one of the most important factors. Analyzing the

reliability of real networks, like the computer network, electric net-work

and the communication network, owns great theoretic implication and

application value. Actually, using the method of lexicographic product can

easily construct a large graph from some smaller graphs, and the

eigenvalues of the large graph are completely described by the parameters

of the topological structure of smaller graphs. The Euler graph and Euler

trail have a broad application in this field. In this paper, we mainly consider

whether a lexicographic product graph, whose topological structure is

affected by the factor graphs, is Euler graph or Euler trail. By using the

theory of combination and the way of extreme construction, some

necessary and suffcient conditions are given to ensure the lexicographic

product is an Euler graph or Euler trail.%人们在实践中发现，网络拓扑结构的一些性质能够在某种程度上衡量一个网络的性能如何，网络的可靠性便是其中的一个重要性能指标。分析现实世界中已有网络，如计算机网络、电网以及通讯网络等的可靠性具有重要的理论意义和应用价值。图的字典乘积利用已有规模较小的网络来构建规模较大的网络，且所得大网络的特征值完全由小网络的拓扑结构参数来刻画，并具有良好的性能，而图的欧拉回路与欧拉迹亦在此领域有着广泛的应用。乘积因子图的拓扑结构影响着字典乘积图的拓扑结构。本文主要研究字典乘积图的

Euler回路问题和Euler迹问题，利用组合理论和极值构造方法，给出了两图的字典乘积图为Euler回路和Euler迹的一些充分必要条件。

【期刊名称】《工程数学学报》

【年(卷),期】2014(000)003

【总页数】7页(P317-323)

【关键词】图;图的拓扑结构;Euler迹;字典乘积

【作 者】李峰;梁栋;徐宗本

【作者单位】西安交通大学数学与统计学院，西安 710049; 青海师范大学计算机学院，西宁 810008;西安交通大学数学与统计学院，西安 710049;西安交通大学数学与统计学院，西安 710049

【正文语种】中 文

【中图分类】O157.5

1 引言

本文未解释的定义和记号均同文献[1]，且无特别指明时，所考虑的图均为简单连通无向图．设图G=G(V,E)，其中V是G的顶点集，E⊆V×V是G的边集．记G的顶点数为ν(G)；记G中所有与顶点r相邻的点的集合为NG(r)；记顶点r在G中的度数为dG(r)．一个图G的一条途径是一个顶点和边的交替序列，如下面的形式

使对1≤ i≤ n，边si的端点是ri−1和ri，这里r0和rn分别称为途径µ的起点和

终点，µ中的边数n称为它的长．若µ中的边s1,s2,···,sn均不相同，则称为链，或者迹．若途径µ中的所有顶点均不相同，从而导致所有的边必然都不相同，这样的途径叫做道路．一条闭的道路称为圈．经过图G中每一条边的链称为欧拉链(Euler chain)，含有欧拉闭链的图G叫做欧拉图(Euler graph)，含有欧拉开链的图G叫做欧拉迹(Euler trail)．

图的字典乘积是由Hausdor ff在研究电网可靠性时，首先从图论角度提出的．设G1=(V1,E1)和G2=(V2,E2)是两个无向图，两个图的字典乘积图记为G1⊙G2，它是以为顶点集、以两个顶点(ri,zj)与(rk,zl)相连当且仅当ri连接rk或ri=rk时zj连接zl为边的图．根据字典乘积定义，设x是图H⊙G的一个顶点，则对于图H的某个顶点h，有x属于Gh．因此，图H⊙G也可以认为是通过因子图G的一个拷贝Gh代替因子图H的每个顶点而得到的．

由字典乘积方法构造的大图包含特定的小图作为它的子图，且保留这些小图的许多好性质，比如，正则性、连通性、可嵌入性、点(边)可迁性、Hamilton性等[2-5]．又由于字典乘积不满足交换律，不同的乘积序得到不同拓扑结构的图，因而得到不同的结果[6]．

1736年，瑞士数学家欧拉(Euler)发表了图论的第一篇论文“哥尼斯堡七桥问题”[1]．欧拉回路在计算机鼓轮设计(模数转换)和中国邮递员等问题中有着广泛地的应用[1,7]．1999年，Tom´as和Ivan[7]研究了特殊的完全图K2m的欧拉回路构造问题，给出了一个求解该图的欧拉回路算法，并对算法的复杂度进行了分析．Ehrenborg和Farjoun[8]于2010年研究了任意二部图的欧拉回路问题，并对该类图的欧拉回路数目和性质进行了刻画．更多关于这方面的理论，可参见文献[9–11]．

本文主要研究字典乘积图的Euler回路问题和Euler迹问题．由于字典乘积图

G1⊙G2是通过已知的阶数较小的图G1和G2构造出来的，因而小图G1和G2的拓扑结构决定着大图G1⊙G2的拓扑结构．当考虑字典乘积图的Euler性时，自然首先考虑的是小图的拓扑结构对构建字典乘积图的Euler性的影响．由此可将字典乘积图G1⊙G2的Euler性问题转化为对已知小图G1和G2的构造问题．我们利用极值构造方法，首次给出了图的字典乘积为Euler回路和Euler迹的一个充分必要条件．

2 主要定理及其证明

Euler图的研究主要在于构造回路，若需要，回路可以重复访问结点，但边只能访问一次.由于Euler回路是图的连通支撑圈，根据字典乘积的性质，因而要求小图(即乘积因子图)都是连通的．

定理1 设G1和G2为两个非平凡的连通图，则字典乘积图G1⊙G2是Euler图当且仅当下列条件之一成立：

1) G1和G2的每个顶点的度数皆为奇数，且G2的阶数为奇数；

2) G1和G2的每个顶点的度数皆为偶数；

3) G1的每个顶点度数均为奇数，而G2的每个顶点的度数皆为偶数，且G2的阶数为偶数．

证明 现证明情形1)的情况，首先假设G1和G2的每个顶点的度数皆为奇数，且G2的阶数为奇数．根据字典乘积的定义易知，图G1⊙G2是连通的．在字典乘积图G1⊙G2的所有迹中，设T是最长的一条．假设T是一条(zu,ru)−→(zv,rv)迹，记为

可以断言(zu,ru)=(zv,rv)．假如情形相反，迹T终止于(zu,ru)̸=(zv,rv)．当然，迹T中的顶点(zv,rv)可能在前面已经出现过，并且每出现一次都要关联图G1⊙G2的两条边，一条边进入顶点(zv,rv)，另一条边离开顶点(zv,rv)，由于迹T是终止于顶

点(zv,rv)，这样就有奇数条边在顶点(zv,rv)处相遇．根据字典乘积的性质可知

根据这个式子，可得顶点(zv,rv)至少还连接一条边，不妨假定为(zv,rv)∼(zw,rw)，且该边在迹T中没有出现．此时，迹T可以延长到顶点(zw,rw)，这与T是最长迹相矛盾．因此，T是一条(zu,ru)−→(zu,ru)迹，也就是说，C=T是一条

回路，这里的C表示一条回路，如果C包含字典乘积图G1⊙G2的所有边，则C是一条Euler回路，即字典乘积图G1⊙G2是Euler图．否则，见下面情形．假设字典乘积图G1⊙G2的一个回路C，记为

并非包含G1⊙G2的所有边，也就是说，字典乘积图G1⊙G2的某些边没有在回路C中出现．由于图G1⊙G2是连通的，因而一定存在某条不在C中的边ε，记为

该边ε与C上的顶点(zx,rx)相关联．设H=G1⊙G2−E(C)，也就是说，H是由图G1⊙G2通过删除回路C的所有边得到的生成子图．由于回路C的每个顶点均关联C的偶数条边，根据字典乘积图的顶点度数性质可知，图G1⊙G2−E(C)的每个顶点度也为偶数．当然，图G1⊙G2−E(C)的也可能是不连通的．另一方面，图H至少存在一个连通分支，不妨假定为H1，它包含边ε=((zx,rx),(zy,ry))，也就是说，子图H1是连通的平凡图．现考虑H1中始于顶点(zx,rx)的一条最长迹．前面已证明，这条迹也必须终止于顶点(zx,rx)，记为

即是H1的一条回路C′．现在，在回路C到达顶点(zx,rx)时，把C′粘到C上，因此，获得字典乘积图G1⊙G2中一个比C长的回路C′′，导致矛盾．由此，C包含

图G1⊙G2的所有边，从而C是一条Euler回路．

反过来，假设字典乘积图G1⊙G2是Euler图，则G1⊙G2包含一条Euler回路，不妨设为 C′′′，记为

其中ki∈V(G1),ti∈V(G2),u≤i≤v，设顶点(kx,tx)是字典乘积图G1⊙G2中不同于(ku,tu)的顶点，由于回路C′′′既不出发于顶点(kx,tx)，也不终止于顶点(kx,tx)，因此在回路C′′′中每次相遇到顶点(kx,tx)，都有两条边被计数，一条是入边，一条是出边．并且在字典乘积图G1⊙G2中，有这样多个顶点(kh,ti)与顶点(kx,tx)相连，当顶点kh与顶点kx在G1中相连．而对顶点ti不作要求，即顶点ti可取字典乘积因子图G2的任意顶点．由于因子图G2的阶数为奇数，且G1和G2的每个顶点的度数皆为奇数．根据字典乘积定义，因此顶点(kx,tx)的度数满足一进一出的要求．现在来看顶点(ku,tu)，它在回路C′′′中是起始顶点，这样有一条边被计算，另外，还有一条边被计算是因为顶点(ku,tu)在回路C′′′中是结束顶点．如果顶点(ku,tu)在其它时候被遇到，则肯定是这样的顶点(ka,tb)，根据字典乘积定义，要么顶点ka与顶点ku相连，要么当ka=ku时，顶点tb与顶点tu相连．对于前一种情形，对顶点tb没有限制，这样的顶点数有|V(G2)|个，对于后面一种情形，由于因子图G1和G2的每个顶点的度数都是奇数点，则每相遇一次就计算偶次，因而，符合本定理所给出的条件．综合上面情形，定理1的2)和3)可以用相似的方法证明，这里不在赘述，本定理得证．

注1 由于字典乘积图G1⊙G2不满足交换律，当乘积因子图G1和G2的字典乘积次序变换了，即为G2⊙G1时，定理1中因子图G1和G2的条件要互换．

定理2 设G1和G2为两个非平凡的连通图，则字典乘积图G1⊙G2含有一条Euler迹当且仅当下列之一条件成立：

1) 因子图G1的每个顶点的度数皆为偶数，且G2恰存在两个度为奇数的顶点；

2) 因子图G1和G2各恰存在两个度为奇数的顶点，且G2的阶数为偶数；

3) 因子图G1恰存在两个度为奇数的顶点，而G2的每个顶点的度数皆为偶数，且G2的阶数为奇数．

证明 现证明情形1)的情况，其它情形可类似证明．由于G1和G2为非平凡的连通图，易知字典乘积图G1⊙G2是连通的．设因子图G1的每个顶点的度数皆为偶数，且G2恰存在两个度为奇数的顶点．设顶点(za,ra)和(zc,rc)为字典乘积图G1⊙G2的两个顶点，其中顶点ra和rc恰为字典乘积因子图G2的两个奇度顶点．在添加一个新的度为2的顶点(zo,ro)到字典乘积图G1⊙G2上，并分别连接顶点(zo,ro)到顶点(za,ra)和(zc,rc)．所得的新图记为W，即

不妨假设L是一条从顶点(za,ra)到顶点(zc,rc)迹，且假定L是图W中所有迹中最长的一条．这样的迹记为

根据构造方法，显然等式za=zc,ra=rc成立．假如情形相反，这条迹L是终止于另外一点，即

根据迹的构造方法，顶点(zc,rc)每出现一次都要关联图W的两条边，一条边进入顶点(zc,rc)，另一条边离开顶点(zc,rc)．由于迹L是终止于顶点(zc,rc)，如果迹L中的顶点(zc,rc)可能在前面已经出现过，这样就有奇数条边在顶点(zc,rc)处相遇．根据字典乘积的性质可知

根据这个式子，结合顶点rc恰为字典乘积因子图G2的一个奇度顶点，且因子图G1的每个顶点的度数都是偶数．可得顶点(zc,rc)至少还连接一条边，不妨假定为

且同时满足

符号ε表示迹中的边，此时，迹L可以延长到顶点(zr,rr)，即

根据字典乘积图中迹的扩展性质，可得∅(L′)>∅(L)，这里∅表示迹的长度，这与L是最长迹相矛盾．因此，L是一条(za,ra)−→(za,ra)迹，也就是说，R=L是一条

回路，这里的R表示一条回路，如果R包含字典乘积图W的所有边，则R是一条Euler回路，即图W是Euler图．否则，见下面情形．假设图W的一个回路R，记为

并非包含W的所有边，也就是说，图W的某些边没有在回路R中出现．由于图W是连通的，因而一定存在某条不在R中的边γ，记为

且同时要满足

由于该边γ与R上的顶点(zz,rz)相关联．不妨设Q=W −E(R)，也就是说，Q是由图W通过删除回路R的所有边得到的生成子图．由于回路R的每个顶点均关联R的偶数条边，根据字典乘积图的顶点度数可知，图W −E(R)的每个顶点度也为偶数．当然，图W −E(R)的也可能是不连通的．另一方面，图Q至少存在一个连通分支，不妨假定为Q1，于是有

根据上面的分析，Q1至少包含下面的一条边，即

也就是说，子图Q1是连通的平凡图．现考虑Q1中始于顶点(zz,rz)的一条最长迹R′．利用上述相似的方法，这条迹也必须终止于顶点(zz,rz)，记为

即R′是连通分支Q1的一条回路．现在，在回路R到达顶点(zz,rz)时，把R′粘到R上，因此，图W中获得了一个比R长的回路R′′，导致矛盾．由此，R包含图W的所有边，从而R是一条Euler回路．

由于与回路R中的起点和终点的选择无关，故可假定R是图W中这样的一条回路

因为顶点(zo,ro)仅与下面的两条边

相关联．其中的一条是回路R的第一条边，另一条是R的最后一条边，则从R中删除顶点(zo,ro)．在字典乘积图G1⊙G2中，将得到一条从顶点(za,ra)出发而终止于顶点(zc,rc)，或从顶点(zc,rc)出发而终止于顶点(za,ra)的Euler迹T．

用相似的方法证明定理的必要性，假设字典乘积图G1⊙G2含有一条Euler迹T．因此不妨设T是某两个顶点(za,ra)和(zc,rc)之间的一条Euler迹T．通过添加一个新的顶点(zo,ro)，从而构造了一个新的连通图H，则

是图H的一条Euler回路．根据字典乘积的性质和回路的构造方法，结合上面的方法，即得本文的结果．

注2 对于定理1和定理2的讨论也可以应用到带有圈的图中，在带有圈的图中，设每个圈对顶点的度数贡献为2，可以将顶点度的概念扩展到带圈的图中．这不改变度的奇偶性，并且圈的出现既不影响一个图是否有欧拉迹，也不影响一个图是否有欧拉回路．

参考文献：

[1]Bondy J A,Murty U Theory with Application[M].London:The

Macmillan Press Ltd,1976

[2]Li F,et results on the lexicographic product of vertex-transitive

graphs[J].Applied Mathematics Letters,2011,24(11):1924-1926

[3]Imrich W,Klavzar t Graphs[M].New York:Wiley,2000

[4]Li F,et the number of spanning trees of the lexicographic product

of networks[J].Scientia Sinica Informations,2012,42(8):949-959

[5]徐宗本，李峰，赵海兴.字典乘积图的点转发指数[J].中国科学：信息科学，2014,44(1):1-16 Xu Z B,Li F,Zhao H the vertex-forwarding index of the

lexicographic product of graphs[J].Scientia Sinica

Informations,2014,44(1):1-16

[6]Yegnanarayanan V,Thiripurasundari P some graph operations and

related applications[J].Electronic Notes in Discrete

Mathematics,2009,33:123-130

[7]Tom´as D,Ivan H,Petr cycles in K2mplus perfect

matching[J].European Journal of Combinatorics,1999,20(3):227-232

[8]Ehrenborg R,Farjoun otics of the Euler number of bipartite

graphs[J].Electronic Notes in Discrete Mathematics,2010,36(1):1289-1293

[9]Edmonds complexes(oiks)[J].Advances in Applied

Mathematics,2010,44(2):155-167

[10]Chebolu P,Cryan M,Martin counting of Euler tours for

generalized series-parallel graphs[J].Journal of Discrete

Algorithms,2012,10:110-122

[11]Ille P.A proof of a conjecture of sabidussi on graphs idempotent under

the lexicographic product[J].Discrete Mathematics,2009,309(11):3518-3522