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

1 定义

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

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

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

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

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

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

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

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

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个顶点的完全图, 则称这样的泛树为仙完全图。记为K_n^*。只有一个泛顶点的仙完全图记为K₁^*。

2 等价命题和证明

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

定理1  设图G是非平凡简单图，H=P_tree是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满足连通且n₁(H)=2+Σ_3≤d(d-2) n_d(H)。

10) 令连通泛化图H=H₀, 则存在k ≥ 1，使得图H_i=P_treeⁱ(i=1, 2…，k)至少含有Δ(H_i)片泛叶子, 删去图H_i的Δ(H_i)片泛叶子得到图H_i+1, 且H_k=K₁^*。

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不是仙完全图K_m^*, 且对图H的任何2个不相邻的顶点u和v添加边uv, 则图H+uv含有唯一的泛化圈。

15) 设H ≠ K₁^*∪K₃^*或者H ≠ K₂^*∪K₃^*, 且|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的泛叶子数目n₁(H) ≥ 3, 其中有2片泛叶子x, y在图H的一条泛路P=xu₁u₂…u_ky上, 另外一片泛叶子w与图H的顶点w′相邻。对图H实施一次P(e⁺, e^-)-运算, 其中e⁺=yw, e^-=ww′, 得到新图H₁的一条泛路P+yw, 且有一度顶点的个数n₁(H) ≥ n₁(H₁)。像这样进行下去, 一定存在k, 使得图H_k是一条泛路。命题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)。

3) →4):由命题3), 知图H的任意一对顶点之间必有一条泛路, 因此H是连通图。由组合知识, 这使得图H至少含有C_|V(H)|²=|V(H)|·[|V(H)|-1]/2条不同的泛路。若图H有数目多于|V(H)|·[|V(H)|-1]/2的泛路, 这将出现一对顶点之间至少2条泛路连通的情况, 矛盾于命题3)。从而, 命题4)得证。

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个分支H₁和H₂, 立得|V(H₁)|=|V(H₂)|=1, 所以余图H-e不连通, 从而算出|E(H)|=1=2-1=|V(H₁)|+|V(H₂)|-1=|V(H)|-1。假设当|V(H)|=k时, 命题6)成立。现证|V(H)|=k+1时的情形。由于对任意一条边e∈E(H), 命题5)保证图H-e不连通, 且H-e只有2个分支L₁和L₂。由数学归纳法, 知|E(L_i)|=|V(L_i)|-1, i=1, 2。故得

$ \begin{array}{l} |E(H)\left| = \right|E({L_1})\left| + \right|E({L_2})\left| { + 1 = } \right|\\ V({L_1})\left| + \right|V({L_2})\left| { - 2 + 1 = } \right|V(H)| - 1。\end{array} $

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

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

$ \begin{array}{l} |E(H)\left| = \right|E(H - {E_1})\left| + \right|{E_1}| = \\ |V(H - {E_1})\left| { - 1 + } \right|{E_1}| = \\ |V(H)\left| { - 1 + } \right|{E_1}\left| \ge \right|V(H)|, \end{array} $

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

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

$ \begin{array}{l} |E(H)| = \sum\limits_{i = 1}^m {|E({H_i})| = } \\ \sum\limits_{i = 1}^m {[|V({H_i})\left| { - 1] = } \right|V(H)| - m} \end{array} $

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

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

$ \begin{array}{l} \sum\limits_{v \in V({H_i})} {{\rm{deg}}\;(v) = 2[|V({H_i})| - 1]{\rm{ }}} \\ \;\;\;\;(i = 1, 2, \ldots , m), \end{array} $

即

$ \begin{array}{l} \sum\limits_{v \in V(H)} {{\rm{deg}}\;(v) = \sum\limits_{i = 1}^m {\sum\limits_{v \in V({H_i})} {{\rm{deg}}\;(v) = } } } \\ \sum\limits_{i = 1}^m {2\;[|V({H_i})\left| { - 1] = 2} \right|V(H)| - 2m, } \end{array} $

由命题8)保证等式∑_v∈V(H)deg (v)=2[|V(H)|-1]成立, 从而解出m=1。因此, 假设图H不连通是错误的。容易算出

$ \begin{array}{l} \;\;\;\;\;\;\sum\limits_{v \in V(H)} {{\rm{deg}}\;(v) = {n_1}(H) + 2{n_2}(H) + \sum\limits_{3 \le d} {d \cdot } } \\ {n_d}(H), \end{array} $

以及|V(H)|=n₁(H)+n₂(H)+∑_3≤dn_d(H), 解得n₁(H)=2+∑_3≤d(d-2) n_d(H)。

9) →10):假设图H有m个分支H₁, H₂, …, H_m, 其中m ≥ 2。由命题9), 得每个分支H_i满足等式n₁(H)=2+∑_3≤d(d-2) n_d(H) (i=1, 2, …, m), 并得到

$ \begin{array}{l} \;\;\;\;\;\;\;\;{n_1}(H) = \sum\limits_{i = 1}^m {{n_1}({H_i}) = 2m + \sum\limits_{i = 1}^m {\sum\limits_{3 \le d} {(d - 2)} } } \\ {n_d}({H_i}) = 2m + \sum\limits_{3 \le d} {(d - 2){n_d}(H), } \end{array} $

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

$ \begin{array}{l} {n_1}(H) = 2 + \sum\limits_{3 \le d} {(d - 2){n_d}(H) \ge } \\ 2 + [\Delta (H) - 2]{n_{\Delta (H)}}(H){\rm{ }} \ge \Delta (H), \end{array} $

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

10) →11):若图H有一条非(泛)割边xy, 那么边xy一定在图H的一个泛化圈C上。由于泛化圈C上的顶点不是泛叶子, 也就是说, 依次删去泛叶子最后所得到的图H_k一定含泛化圈C, 即H_k≠ K₁^*, 这与命题10)矛盾。若图H不连通, 设它有分支H₁, H₂, …, H_m(m ≥ 2)。由命题10), 得到每个分支H_i所对应的图H_{i, 1}, H_{i, 2}, …, H_{i, mi}, 其中H_{i, mi}=K₁^*, 删去图H_{i, j}的Δ(H_{i, j})片泛叶子可得图H_{i, j+1}(j=0, 1, …, m_i-1)。当m ≥ 2时, 像上面那样删去泛叶子, 最后得到m个K₁^*, 与命题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不是仙完全图K_m^*(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连通, 且不是仙完全图K_m^*(m ≥ 3)。按照命题15)的条件, 图H满足|E(H)|=|V(H)|-1 ≠ |V(H)|·[|V(H)|-1]/2, 这也说明图H不是仙完全图。因为H ≠ K₁^*∪K₃^*或者H ≠ K₂^*∪K₃^*, 按照命题14), 给连通图H的2个不相邻的顶点u和v添加边uv, 使得图H+uv仅含唯一的泛化圈, 命题15)得证。

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

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

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

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

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

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

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

3 总结与问题

本文将树的性质嫁接在仙人掌图上, 并提供泛化方法来帮助将仙人掌图中的圈弱化为“顶点”, 从而达到嫁接的目的。泛化图体现了“小中见大”、“以简代繁”、化复杂为精炼的思想。此外, 研究网络2顶点之间的路是研究网络熵和随机游走的基础, 十分有必要搞清楚仙人掌模型的顶点间的路。由于在泛化图H中任意2个正常顶点u和v之间有方顶点的情况过于复杂, 所以本文推论1只讨论了没有方顶点的情形时, 原图G中u和v之间路的数目。为防止出现圈的情形, 所考虑的路的条数与泛化图中从顶点u和v路上三角顶点的数目有关, 而与方顶点相邻的三角顶点的数目无关。若泛化图H的2个正常顶点u和v之间只有一个方顶点, 并且除了用泛化边与方顶点相邻的n个三角顶点外, 没有其他三角顶点, 则在图G中, 顶点u和v之间路的数目与u和v的位置有关系:若顶点u和v都连在方顶点上或同一个圈的同一个顶点上, 则在图G中, 顶点u和v之间路的数目是x=C_n⁰+C_n¹+…+C_nⁿ; 若其中一个顶点u连在方顶点上, 另一个顶点v连在三角顶点上, 则在图G中, 顶点u和v之间路的数目是y=2(C_n-1⁰+C_n-1¹+…+C_n-1^n-1); 若顶点u和v连在同一个圈的不同顶点上, 则在图G中, 顶点u和v之间路的数目是z=1+C_n-1⁰+C_n-1¹+…+C_n-1^n-1; 若顶点u和v连在不同的三角顶点上, 则在图G中, 顶点u和v之间路的数目是w=4(C_n-2⁰+C_n-2¹+…+C_n-2^n-2)。由此可见, 有方顶点的情况相当复杂, 须另文细细研究。

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