关于仙人掌图的等价命题

孙 慧，姚 兵,2

(1.西北师范大学 数学与统计学院, 甘肃 兰州 730070；2.兰州交通大学 电子与信息工程学院，甘肃 兰州 730070)

图论中的图可根据不同的依据分为不同的图类。 比如, 根据图是否有向, 可以分为有向图和无向图; 根据图是否有环和重边, 可以分为简单图和非简单图; 根据图是否含圈, 可以分为无圈图和非无圈图; 根据图是否连通, 可以分为连通图和非连通图等等。 已知, 图论学科里的树在复杂网络研究中占有极其重要的地位, 树的性质、结构、特点已经被许多的学者深入研究过[1-6]。 例如:任何一颗对虾树都有一个奇优美标号和奇优雅标号[7-8]。 但是除树以外, 图论中其余的图是否也有优秀的结论呢? 将复杂转化为简单, 从未知到已知, 是科学研究的主要思想方法之一。 已知, 网络模型中的生成树与网络的拓扑结构有着紧密的联系[9-10]。 仙人掌图被用于建立由环形局域网构成的复杂网络的模型, 刻画这类网络的拓扑结构对网络的信息传输和安全起着重要的作用。因此, 许多学者都把仙人掌图作为研究对象[11-16]。

1 定 义

在文献[11]中, 王晓敏等人给出了树的若干等价命题。 本文给出仙人掌图的15种等价命题及其证明。 文中所考虑的图均为有限、无向、简单图。 一个图称为仙人掌图, 也叫树形图, 是指它的任何2个圈最多有一个公共顶点。 换句话说, 该图的每个块要么是圈, 要么是完全图K2。 为了给出仙人掌图的等价命题, 必须先将仙人掌图泛化成一棵树。 反过来, 也可以将任何一棵正常的树转化成仙人掌图, 从而给出仙人掌图的构造及其拓扑性质, 为这种模型新描述的网络提供了可靠、准确的数学方法。 下面给出泛化方法和新概念。 泛化是指将仙人掌图转化为泛树的过程, 细节如下。

1)对于仙人掌图的任何一个有k个顶点和k条边的圈, 去掉这k个顶点,k条边, 并用一个特殊的顶点——三角顶点(用一个小三角表示, 记为upc, 其中u是顶点，pc是pan-circle的缩写)来代替这个圈。 如图1所示。

图1 一个泛化三角顶点Fig.1 A pan-triangular vertex

对仙人掌图中只有两个由一个公共顶点连接的圈, 除了要将这2个圈泛化为2个三角顶点外, 还要将公共顶点用一条特殊的边——泛化边(用两条平行线段表示, 记为ep, 其中e是表示边,p是pan的缩写)来表示, 见图2。

图2 一条泛化边Fig.2 A pan-edge

当仙人掌图中有3个及3个以上的k个圈由一个公共顶点连通时, 除了要将k个圈泛化为k个三角顶点, 还要将这个公共顶点用一个特殊的顶点——方顶点(用一个小正方形表示, 记为ups, 其中u是表示顶点,ps是pan-square的缩写)来表示, 再将表示k个圈的k个三角顶点用泛化边与方顶点分别相连。 图3给出一个例子。

图3 一个泛化方顶点和四个三角顶点Fig.3 A pan-square vertex and four pan-triangular vertexs

本文在此规定: 因为三角顶点和方顶点都是仙人掌图泛化后得到的, 所以将三角顶点、方顶点和正常顶点统称为泛顶点, 其中三角顶点、方顶点也称为泛化点。 泛化边和正常边统称为泛边。

2)泛树是指仙人掌图通过泛化后得到的泛化图, 记为Ptree。 泛树一般有3种顶点: 正常顶点, 三角顶点, 方顶点; 泛树包含2种边: 正常边, 泛化边。 见图4中的例子。 关于泛树的基本参数有:

泛树的顶点集Ptree=Vf∪Vp, 其中Vf表示正常的顶点的集合;Vp表示泛化点的集合。 泛树的边集E(Ptree)=Ef∪Ep, 其中Ef表示正常的边的集合;Ep表示泛化边的集合。 根据泛化的过程, 可计算在泛化过程中去掉的顶点个数M和边数N: 泛树的顶点个数|V(Ptree)|=|V(G)|-M; 泛树的边数|E(Ptree)|=|E(G)|-N, 其中G是泛化之前的仙人掌图。

泛度是指泛树中与某顶点v(这里的v可能是正常的顶点, 也可能是泛化点)关联的边(这里的边可能有正常边, 也可能有泛化边)的数目, 例如, 泛顶点v与s条正常边,t条泛边关联, 则v的泛度为deg(v)=s+t。δ(Ptree) 和Δ(Ptree) 分别表示最小泛度和最大泛度。泛叶子是指泛度为1的泛顶点。 若v是正常的顶点且与之关联的边全是正常的边, 则v的泛度与图论中顶点度的定义完全相同。符号nd(G) 表示图G中泛度为d的泛顶点的个数，见图4。

图4 泛树Fig.4 Pan-trees

3)泛化圈是指含泛化点和泛化边的圈。不含泛化点和泛化边的泛化圈, 就是图论中的圈; 泛路是指含泛化点和泛化边的路。不包含泛化点和泛化边的泛路, 就是图论中的路。

4)泛缩边图G·e是删去G的泛边e, 重合e的2的个端点新得到的图, 其中, 若泛边e的2个端点都是正常顶点, 则将泛边e的2个端点重合为正常顶点; 若泛边e的2个端点都是三角顶点, 则将泛边e的2个端点重合为三角顶点; 若泛边e的2个端点一个是三角顶点, 一个是方顶点, 则将泛边e的2个端点统一重合为方顶点; 若泛边e的2个端点一个是泛化点, 一个是正常顶点, 则将泛边e的2个端点统一重合为泛化点。

5)给图G的两个不相邻的泛顶点u和v之间添加泛边。 在实际操作过程中, 具体添加哪种边视具体情况而定, 若u和v中至少有一个是正常顶点, 则添加一条正常边; 若u和v都是泛化点, 则添加一条泛化边uv=e+, 再删除G的一条不是e+的泛边e-, 称这种运算为P(e+,e-)-运算, 也说对图G实施了一次P(e+,e-)-运算。

6)泛化图G的泛割边是指使得分支数目ω(G-e)>ω(G)的泛边e; 泛化图G的泛割点v使得分支数目ω(G-v)>ω(G)。

7) 生成泛树是指泛化图的生成树。设泛化仙人掌图得到的泛树有n个泛顶点, 且除泛顶点和泛边这样的符号不同外, 恰好形似n个顶点的完全图, 则称这样的泛树为仙完全图。 记为Kn*。 只有一个泛顶点的仙完全图记为K1*。

2 等价命题和证明

在无特殊说明的情况下, 以下说到的顶点是上一节定义的三种顶点的一种; 说到的边可能是正常边, 也可能是泛化边。没有说到的符号及术语均采用图论的标准。

定理1设图G是非平凡简单图，H=Ptree是G的泛化图, 则下面的命题两两相互等价:

1)H是泛树。

2) 对p个顶点的连通泛图H实施一系列P(e+,e-)-运算后, 总可以得到一条p个顶点的泛路。

3)H的任意一对顶点由唯一的一条泛路连接。

4)H恰有|V(H)|·[|V(H)|-1]/2条泛路, 且任意一对顶点有泛路连通。

5) 对于任意的边e∈E(H),H是使得图H-e不连通的最小连通图。

6)H连通, 且 |E(H)|=|V(H)|-1。

7)H无泛化圈, 且 |E(H)|=|V(H)|-1。

8)H连通,δ(H) ≥ 1,Σv∈V(H)deg (v)=2[|V(H)|-1]。

9)H满足连通且n1(H)=2+Σ3≤d(d-2)nd(H)。

10) 令连通泛化图H=H0, 则存在k≥ 1 ，使得图Hi=Ptreei(i=1,2…，k)至少含有Δ(Hi)片泛叶子, 删去图Hi的Δ(Hi)片泛叶子得到图Hi+1, 且Hk=K1*。

11) 图H的每条泛边都是图H的泛割边, 且 |E(H)|=|V(H)|-1。

12) 图H的每个泛度不为1的泛顶点都是H的泛割点, 且 |E(H)|=|V(H)|-1。

13) 图H连通, 对于任意的边e∈E(H), 图H的生成泛树的个数等于泛缩边图H·e的生成泛树的个数。

14) 当m≥ 3时, 连通图H不是仙完全图Km*, 且对图H的任何2个不相邻的顶点u和v添加边uv, 则图H+uv含有唯一的泛化圈。

15) 设H≠K1*∪K3*或者H≠K2*∪K3*, 且 |E(H)|=|V(H)|-1, 对于图H中任何两个不相邻的顶点u和v添加边uv, 则图H+uv含有唯一的泛化圈。

证明本证明用 “i) →j)” 表示根据命题i)来推证命题j), 其中1≤i,j≤ 15且i≠j。

1) →2): 因H是泛树, 故图H无泛化圈。 若H为泛路, 证明完成。 若图H不是泛路, 则图H的泛叶子数目n1(H) ≥ 3, 其中有2片泛叶子x,y在图H的一条泛路P=xu1u2…uky上, 另外一片泛叶子w与图H的顶点w′ 相邻。 对图H实施一次P(e+,e-)-运算, 其中e+=yw,e-=ww′, 得到新图H1的一条泛路P+yw, 且有一度顶点的个数n1(H) ≥n1(H1)。 像这样进行下去, 一定存在k, 使得图Hk是一条泛路。 命题2)得证。

2) →3): 因为图H是连通图的, 所以H的任意一对顶点u和v之间至少由一条泛路P(u,v)连接。 假设连接顶点u和v之间的泛路不唯一, 存在不同于泛路P(u,v)的另外一条泛路Q(u,v), 这2条泛路必将导致图H的一个泛化圈, 那么对图H实施多少次P(e+,e-)-运算都不能减少泛化圈的数目, 从而无法得到一条泛路, 这矛盾于命题2)。 换句话说, 图H的任意一对顶点u和v之间有且仅有一条泛路P(u,v)。

4) →5): 假设命题5)不成立, 则存在图H的一条边e, 使得删去边e的余图H-e是连通的, 可知图H-e至少有|V(H-e)|·[|V(H-e)|-1]/2条不同的泛路。 因为|V(H)|=|V(H-e)|, 说明图H的顶点之间至少存在1+|V(H)|·[|V(H)|-1]/2条不同的泛路, 这与命题4)矛盾, 命题5)得证。

5) →6): 可以用数学归纳法证明。 当|V(H)|=2时, 因为一条边仅能连2个分支H1和H2, 立得 |V(H1)|=|V(H2)|=1, 所以余图H-e不连通, 从而算出|E(H)|=1=2-1=|V(H1)|+|V(H2)|-1=|V(H)|-1。 假设当|V(H)|=k时, 命题6)成立。 现证|V(H)|=k+1时的情形。 由于对任意一条边e∈E(H), 命题5)保证图H-e不连通, 且H-e只有2个分支L1和L2。 由数学归纳法, 知|E(Li)|=|V(Li)|-1,i=1,2。 故得

|E(H)|=|E(L1)|+|E(L2)|+1=|V(L1)|+|V(L2)|-2+1=|V(H)|-1。

正是因为删去泛化圈上的边e后, 不能使图H是图H-e不连通的最小连通图, 故H无泛化圈, 命题6)得证。

6) →7): 假设图H含有泛化圈, 并且删去泛化圈中的任意边e后, 得到的图H-e仍然连通, 如果H-e不含泛化圈C, 则停止; 反之, 则继续删除泛化圈C上的一条边, 像这样进行下去, 直到所得到的图不含泛化圈为止。 设全体删除的泛边集合为E1。 上述过程保证H-E1是不含圈的连通图, 并有等式|E(H-E1)|=|V(H-E1)|-1成立。 注意到|V(H)|=|V(H-E1)|, 那么

|E(H)|=|E(H-E1)|+|E1|=

|V(H-E1)|-1+|E1|=

|V(H)|-1+|E1|≥ |V(H)|,

这与命题6)矛盾。 因此,H不含泛化圈。 用数学归纳法易证得 |E(H)|=|V(H)|-1。

7) →8): 假设图H有m个分支H1,H2,…,Hm, 其中m≥ 2。 由命题7), 得每个分支Hi都满足等式 |E(Hi)|=|V(Hi)|-1(i=1,2,…,m)。 又因为图H的边数目, 有下面的等式

成立。 再结合命题7), 得到m=1, 这与m≥ 2矛盾。 从而图H是连通的。 需注意H≠K2*∪K3*, 又因为∑v∈V(H)deg (v)=2|E(H)|, 立得命题8)。

8) →9): 假定图H不连通。 一般地,H有m个分支H1,H2,…,Hm, 其中m≥ 2。 由命题 (8) 知, 每个分支Hi满足

(i=1,2,…,m),

即

由命题8)保证等式∑v∈V(H)deg (v)=

2[|V(H)|-1]成立, 从而解出m=1。 因此, 假设图H不连通是错误的。 容易算出

以及|V(H)|=n1(H)+n2(H)+∑3≤dnd(H), 解得n1(H)=2+∑3≤d(d-2)nd(H)。

9) →10): 假设图H有m个分支H1,H2,…,Hm, 其中m≥ 2。 由命题9), 得每个分支Hi满足等式n1(H)=2+∑3≤d(d-2)nd(H) (i=1,2,…,m), 并得到

这与命题9)矛盾, 也就是说图H连通。又因为

2+[Δ(H)-2]nΔ(H)(H) ≥Δ(H),

且Δ(H)>0, 这意味着图H至少有Δ(H)片泛叶子, 则可以删去图H的这Δ(H)片泛叶子, 得到一个连通图H1; 又因H1连通, 命题9)保证H1至少有Δ(H1)>0片泛叶子, 删去它的Δ(H1)片泛叶子后, 得到图H2; 如此进行下去, 由于图H的顶点数目有限, 依次可得图H0,H1, …,Hk, 其中H0=H和Hk=K1*, 且每个图Hi至少有Δ(Hi)片泛叶子, 删去图Hi的Δ(Hi)片泛叶子就得到Hi+1(i=0, 1,…,k-1)。

10) →11): 若图H有一条非(泛)割边xy, 那么边xy一定在图H的一个泛化圈C上。 由于泛化圈C上的顶点不是泛叶子, 也就是说, 依次删去泛叶子最后所得到的图Hk一定含泛化圈C, 即Hk≠K1*, 这与命题10)矛盾。 若图H不连通, 设它有分支H1,H2,…,Hm(m≥ 2)。 由命题10), 得到每个分支Hi所对应的图Hi,1,Hi,2, …,Hi,mi, 其中Hi,mi=K1*, 删去图Hi,j的Δ(Hi,j)片泛叶子可得图Hi,j+1(j=0, 1,…,mi-1)。 当m≥ 2时, 像上面那样删去泛叶子, 最后得到m个K1*, 与命题10)矛盾, 只有图H不含泛化圈且连通, 这说明|E(H)|=|V(H)|-1。

11) →12): 假设图H有一个泛度不为1的顶点w, 使得H-w的分支数目ω(H-w)与图H的分支数目ω(H)相等, 也就是说, 与顶点w相邻的每一个顶点都不是泛叶子。 任取顶点w的邻点z, 删去边wz所得的余图H-wz的分支数目与图H的分支数目相等, 即边wz不是图H的泛割边, 这与命题 11)矛盾, 由此可知图H的每一个泛度大于1的顶点均为图H的泛割点。 由命题11)的结论|E(H)|=|V(H)|-1, 命题12)得证。

12) →13): 设e=uv是图H的任意一条边。H·e是收缩边e=uv后得到泛缩边图, 记顶点u与顶点v重合后的顶点为w*。 命题12)要求图H无泛化圈, 并满足等式|E(H)|=|V(H)|-1。 由7) →8), 得到图H和泛缩边图H·e都有各自的生成泛树。 若图H的生成泛树的个数与泛缩边图H·e的生成泛树的个数不相等, 那么图H含有不通过边e的生成泛树, 这意味着, 图H有一个泛化圈含边e, 对应地, 可以在泛缩边图H·e里找到一个泛化圈包含顶点w*。 从而证明了|E(H)| ≥ |V(H)|, 这与命题12)冲突。

13) →14): 根据命题13), 图H有生成泛树, 也就是说, 图H连通。 图H的生成泛树的个数与泛缩边图H·e的生成泛树的个数相等, 从而保证图H不含泛化圈。 由图H不是仙完全图Km*(m≥ 3), 又因图H至少包含一对不相邻的顶点u和v, 则可给图H添加边uv, 得到图H+uv。 若图H+uv包含2个泛化圈C和C′, 必须是泛化圈C和C′有且仅有公共边uv。 删去边uv, 泛化圈C和C′合并成图H的一个泛化圈, 这矛盾于图H不含泛化圈, 也矛盾于命题13)。 这就证得命题14)。

14) →15): 当H只有2个顶点时, 是平凡情形, 故设 |V(H)| ≥ 3。 由命题 (14) 的条件, 知图H连通, 且不是仙完全图Km*(m≥ 3)。 按照命题15)的条件, 图H满足|E(H)|=|V(H)|-1 ≠ |V(H)|·[|V(H)|-1]/2, 这也说明图H不是仙完全图。 因为H≠K1*∪K3*或者H≠K2*∪K3*, 按照命题14), 给连通图H的2个不相邻的顶点u和v添加边uv, 使得图H+uv仅含唯一的泛化圈, 命题15)得证。

15) →1): 假设图H不连通, 也就是说, 图H至少有2个分支H1和H2。 当|V(H1)|+|V(H2)|=4时, 命题15)的条件使得H≠K1*∪K3*, 故对于图H的2个不相邻的顶点u和v, 连接u和v所得到的加边图H+uv不含泛化圈, 这抵触于命题15)。 当|V(H1)|=2和|V(H2)|=3时, 命题15)的条件使得H≠K2*∪K3*, 故对于图H的2个不相邻的顶点u和v, 连接u和v所得到的加边图H+uv不含泛化圈, 这与命题15)冲突。 当|V(H1)|=1和|V(H2)|=4时, 命题15)的条件|E(H)|=|V(H)|-1说明H2等于4个顶点的泛化圈, 对于这个泛化圈上的2个不相邻的顶点x和y进行连边xy, 则图H+xy含2个泛化圈, 矛盾于命题15)。 当 |V(H1)|+

|V(H2)| ≥ 6时, 若|V(H1)| ≤ 2和|V(H2)| ≥ 4, 易得出矛盾; 若|V(H1)| ≥ 3和|V(H2)| ≥ 3, 命题15)的条件|E(H)|=|V(H)|-1约束分支H1和H2中至多一个有泛化圈, 不妨设H2含泛化圈。 然而, 对于分支H1的2个不相邻的顶点s和t, 用边连接s和t, 那么图H+st至少含2个泛化圈, 矛盾于命题15)。 当图H有3个以上的分支时, 令H1和H2是最大分支或次最大分支, 其余论证与上面的证明类同, 不再赘述。 注意到, 当图H有3个以上的分支时, 分别取前面2个分支H1和H2的顶点u和顶点v, 用新边连接这2个顶点, 所得到的加边图H+uv就不含唯一泛化圈, 又矛盾于命题15)。 这说明, 假设图H不连通是错误的。 图H的连通性与命题15)结合, 即可推证出命题1)。

对1≤i,j≤ 15且i≠j, 以上过程证明了命题i)成立的充要条件是命题j)成立。 本定理得证。

推论1设图G是非平凡简单图,H=Ptree是G的泛化图。 若泛化图H的2个正常顶点u和v之间的路上有k个三角顶点, 则在图G中, 顶点u和v由2k条不同的路连接。

证明用数学归纳法证。 当k=0时, 即u和v之间无三角顶点, 则u和v之间由唯一的路连接。

当k=1时, 即u和v之间有一个三角顶点, 由于三角顶点在仙人掌图G中是一个圈, 显然一个圈中度大于等于3的顶点之间路仅有两条, 则u和v之间由2条不同的路连接。

假设k=i-1时, 即u和v之间有i-1个三角顶点,u和v之间由2i-1条不同的路连接。

则当k=i时, 即u和v之间有i个三角顶点, 有归纳假设知, 若先将第i个三角顶点当成正常顶点, 前i-1个三角顶点, 使得u和v之间由2i-1条不同的路连接, 而加入第i个三角顶点的事件, 它与前i-1个三角顶点之间是相互独立事件, 因此u和v之间由2i条不同的路连接。 依据数学归纳法, 推论得证。

3 总结与问题

在类似仙人掌图的研究问题中, 今后可以运用本文的泛化方法。 显然, 本文为图论学科提供了一个新的图类, 同时, 也为网络研究提供了新的网络模型。 反过来看, 可以将一棵树的若干个顶点改为本文的泛化顶点, 将一些边改为泛边, 就得到一棵泛树。 然后, 将这棵泛树反转出一个仙人掌图。 本文的研究表明, 仙人掌图可通过泛化后研究其拓扑结构。 那么, 其他复杂的图如何进行泛化达到简化呢?这是今后要研究的课题。 需要指出, 本文的泛化图不是图论中的超图。 从应用的角度上看, 构造优秀的网络模型对理解、认识、研究现实世界的诸多网络有着重要而积极的作用。