图的支配问题^[1]是图论的重要内容，在实际应用和其他学科中都有非常广泛的应用。随着人们对支配问题研究的深入，根据不同的实际问题背景，衍生出了很多种支配类型，例如双罗马支配、意大利支配等。图的意大利支配是一种新兴的支配类型，也称为罗马{2}支配^[2]。确定图的意大利支配数是NP困难的。

可拓学^[3]是由我国学者蔡文创立的一门数学、哲学与工程学交叉的新兴学科。分合链方法是一种可拓创新方法^[4]，是可拓学应用于实际的桥梁。可拓创新方法已被应用于物流网络^[5]、企业管理^[6]、产品设计^[7-9]、建筑设计^[10]等领域。

本文利用分合链方法证明了图的意大利支配数下界等于上界，从而确定出图的意大利支配数。通过将图中顶点表示为物元，利用分合链方法能非常形象地表述组合的思想。该方法的可移植性较好，可用于确定多种图形不同类型的支配数。在图的支配数教学中，使用该方法可以使学生既快又好地理解和掌握并能举一反三。

1 意大利支配

意大利支配的直观描述是在某个地区(可以将该地区看作一个图，用 $ G $ 表示)，每个城市(顶点)最多可以安排两支防守部队。没有安排部队的城市(顶点)至少要与一个有两支部队的城市相邻，或者至少要与两个有一支部队的城市相邻。在满足这些条件的情况下，每一种安排驻守部队的方式都叫图的一个意大利支配函数 $ f $ ，此时所需的驻守部队的数量就是 $ f $ 的权重 $ w(f) $ 。权重的最小值，即保卫这个地区所需的最少部队数量就是图 $ G $ 的意大利支配数^[11]，记为 $ {\gamma _I}(G) $ 。如果意大利支配函数 $ f $ 的权重等于图 $ G $ 的意大利支配数，即 $ w(f) = {\gamma _I}(G) $ ，则称 $ f $ 为最优的意大利支配函数。

若用 $ V $ 表示图的顶点集合， $ E $ 表示图的边的集合，则图可表示为 $ G = (V,E) $ 。顶点 $ v \in V $ 的开邻域为 $ N(v) = \{ u|(u,v) \in E\} $ 。意大利支配函数 $ f $ 是 $ V $ 到数集 $ \{ 0,1,2\} $ 的映射，并且满足每一个函数值为0的顶点 $ v $ 都至少与一个函数值为2的顶点相邻或者至少与两个函数值为1的顶点相邻。

在确定图的意大利支配数时，通常是先找出意大利支配数的上界，然后证明意大利支配数的下界与上界相等。假设已知图G的意大利支配数 $ {\gamma _I}(G) $ 的上界为 $ a $ ，即 $ {\gamma _I}(G) \leqslant a $ 。欲证明 $ {\gamma _I}(G) = a $ ，只需证明 $ {\gamma _I}(G) \geqslant a $ 。在证明中将图中顶点或顶点集合表示为物元，通过物元组合的方式得到聚合物元 $ {M_i} $ ，使得对于每个 $ {M_i} $ 都有 $w({M_i}) \geqslant {a}/{m}$ ，即有

$ {\gamma _I}(G) {\text{ = }}\sum\nolimits_{i = 1}^m {w({M_i}) } \geqslant a 。$

2 分合链方法

分合链方法是一种可拓创新方法，是根据可扩规则，利用领域知识判断基元组合、分解或扩缩的可能性，以寻找创新或解决矛盾问题的途径的方法。组合、分解和扩缩都是创新或解决矛盾问题的有效手段。

基元是可拓学的逻辑细胞，分为物元、事元和关系元。本文研究的是图，使用的基本表达是物元。

可扩原则在本文中是指可组合原则，即给定物元 $ {M_1} = ({O_1},{c_1},{v_1}) $ ，则至少存在一个物元 $ {M_2} = ({O_2},{c_2},{v_2}) $ ，使 $ {M_1} $ 和 $ {M_2} $ 可以组合成 $ M $ ，这时

若 $ {O_1} = {O_2} $ ， $ {c_1} \ne {c_2} $ ，则

$ M{ = {M_1} \oplus {M_2}} = ({O_1},{c_1} \oplus {c_2},{v_1} \oplus {v_2})= \left[ {\begin{array}{*{20}{l}} {{O_1},}&{{c_1},}&{{v_1}} \\ {}&{{c_2},}&{{v_2}} \end{array}} \right] \\ $

若 $ {O_1} \ne {O_2} $ ， $ {c_1} = {c_2} $ ，则

$ M{ = {M_1} \oplus {M_2}} { = ({O_1} \oplus {O_2},{c_1},{v_1} \oplus {v_2}) } $

若 $ {O_1} \ne {O_2} $ ， $ {c_1} \ne {c_2} $ ，则

$ M{ = {M_1} \oplus {M_2}} \\ {}{ = \left[ {\begin{array}{*{20}{l}} {{O_1} \oplus {O_2},}&{{c_1},}&{{v_1} \oplus {c_1}({O_2}) } \\ {}&{{c_2},}&{{c_2}({O_1}) \oplus {v_2}} \end{array}} \right]} $

本文中物元 $ {M_1} $ 和 $ {M_2} $ 的组合形式是指可加形式，即 $ M = {M_1} \oplus {M_2} $ 表示物元 $ {M_1} $ 和 $ {M_2} $ 可以构成聚合物元 $ M $ 。当某一物元不能满足解决问题的需要时，就可以考虑加上另一个物元，使它们的聚合物元能用于解决问题。

分合链方法的基本步骤为：(1) 将所要分析的对象用物元 $ M $ 表示；(2) 利用发散树方法对物元 $ M $ 进行拓展，拓展出多个基元；(3) 根据领域知识，判断物元 $ M $ 是否可与拓展出来的其他物元组合；(4) 考察组合后的物元是否可用于解决问题。

3 意大利支配数的可拓证明

确定图 $ G $ 的意大利支配数通常采用的方法是先构造图 $ G $ 的意大利支配函数，计算出意大利支配数的上界为 $ a $ ，即 $ {\gamma _I}(G) \leqslant a $ ，然后证明 $ {\gamma _I}(G) \geqslant a $ ，最终可得 $ {\gamma _I}(G) = a $ 。

本节以确定广义彼得森图 $ P(n,1) $ 的意大利支配数为例，说明如何利用分合链方法证明意大利支配数的下界与上界相等。

3.1 广义彼得森图P (n,1)

广义彼得森图是图论中一类非常重要的图，用符号 $ P(n,k) $ 表示。本文研究的是当 $ k{\text{ = }}1 $ 时的广义彼得森图 $ P(n,1) $ ，其顶点个数为 $ 2n $ 。图1所示的是 $ P(5,1) $ 和 $ P(6,1) $ 。

3.2 P (n,1) 意大利支配数的上界

设 $ P(n,1) $ 外圈和内圈上的顶点分别为 $ {v_i} $ 和 $ {u_i} $ ( $1 \leqslant i \leqslant n$ ) ，按照如下形式构造意大利支配函数 $ f $ 。

当 $ n $ 为偶数时， $ f({v_{2i - 1}}) = f({u_{2i}}) = 1 $ $\left(1 \leqslant i \leqslant \dfrac{n}{2} \right)$ ，其他顶点函数值为0。

当 $ n $ 为奇数时， $ f({v_{2i - 1}}) = f({u_{2i}}) = 1 $ $\left( 1 \leqslant i \leqslant \dfrac{{n - 1}}{2} \right)$ ， $ f({v_n}) = 1 $ ，其他顶点函数值为0。

按照上述方式构造的意大利支配函数 $ f $ 其权重 $ w(f) = n $ 。因此， $ P(n,1) $ 的意大利支配数的上界为 $ n $ ，即

$ {\gamma _I}(P(n,1) ) \leqslant n $

(1)

图2所示的是 $ P(5,1) $ 和 $ P(6,1) $ 上的意大利支配函数 $ f $ ，其中实心点表示该顶点的函数值为1，空心点表示该顶点的函数值为0。

3.3 P (n,1) 意大利支配数的下界

将 $ P(n,1) $ 中外圈顶点 $ {v_i} $ 和相邻的内圈顶点 $ {u_i} $ ( $ 1 \leqslant i \leqslant n $ ) 看成是一个整体，称之为物元 $ {M_i} $ ，物元模型为

$ {M}_{i}=\left[\begin{array}{lll}{O}_{i}\text{，} & 权重\text{，} & w({M}_{i}) \\ & 可组合性\text{，} & D({M}_{i}) \\ & 组合数\text{，} & N({M}_{i}) \\ & 平均权重\text{，} & \overline{w}({M}_{i}) \end{array}\right] $

式中： $ {O_i}{\text{ = }}\{ {u_i},{v_i}\} $ ， $ w({M_i}) = f({v_i}) + f({u_i}) $ ， $ f $ 是 $ P(n,1) $ 的意大利支配函数， $ D({M_i}) = 0 $ 或1 (0表示未组合，1表示已组合)。组合数为 $ N({M_i}) = 1 $ ，故平均权重 $\overline w ({M_i}) {\text{ = }} w({M_i})$ 。

欲证明 $ P(n,1) $ 的意大利支配数的下界也是 $ n $ ，即 $ {\gamma _I}(P(n,1) ) \geqslant n $ ，只需证明物元 $ {M_i} $ ( $ 1 \leqslant i \leqslant n $ ) 的权重 $ w({M_i}) \geqslant 1 $ 。然而， $ P(n,1) $ 的意大利支配函数并不唯一， $ f({v_i}) = f({u_i}) = 0 $ ，即 $ w({M_i}) = 0 $ 的情形是可能存在的。

3.3.1 聚合物元

为了解决上述问题，考察聚合物元。为了区分物元和聚合物元，以下用 $ B $ 表示聚合物元。聚合物元 $ B $ 由若干物元以可加的形式组合而成，形如

$B ={M}_{1}\oplus {M}_{2}\oplus \cdots \oplus {M}_{k} =\left[\begin{array}{lll}O, & 权重\text{，} & w(B) \\ & 可组合性\text{，} & D(B) \\ & 组合数\text{，} & N(B) \\ & 平均权重\text{，} & \overline{w}(B) \end{array}\right] $

式中： $ O = {O_1} \cup {O_2} \cup \cdots \cup {O_k}{\text{ = \{ }}{u_1}{\text{,}}{v_1}{\text{,}}{u_2}{\text{,}}{v_2}{\text{,}} \cdots {\text{,}}{u_k}{\text{,}}{v_k}{\text{\} }} $ ， $w(B) = w({M_i}) + w({M_{i + 1}}) + \cdots + w({M_{i + k - 1}})$ ， $ D(B) {\text{ = }}0 $ ， $N(B) {\text{ = }} k$ ， $ \overline w (B) {\text{ = }}w(B) /k $ 。

3.3.2 支配数下界的可拓证明

下面证明 $ P(n,1) $ 意大利支配数下界是 $ n $ ，即 $ {\gamma _I}(P(n,1) ) \geqslant n $ 。

设 $ {M_1} $ , $ {M_2} ,\cdots $ , $ {M_n} $ 为 $ P(n,1) $ 包含的 $ n $ 个物元， $ f $ 是 $ P(n,1) $ 的意大利支配函数，则每一个函数值为0的顶点 $ v $ 都至少与一个函数值为2的顶点相邻或者至少与两个函数值为1的顶点相邻。由此可知，如果存在权值为0的物元 $ {M_i} $ ，即 $ w({M_i}) {\text{ = }}0 $ ，那么与其相邻的两个物元权值和大于等于4，即

$ w({M_i}) = 0 \Rightarrow w({M_{i - 1}}) {\text{ + }}w({M_{i + 1}}) \geqslant 4 $

(2)

其中脚标对 $ n $ 取模。

定理 　 $ P(n,1) $ 意大利支配数下界是 $ n $ ，即

$ {\gamma _I}(P(n,1) ) \geqslant n $

(3)

证明：(1) 将 $ P(n,1) $ 中外圈顶点 $ {v_i} $ 和相邻的内圈顶点 $ {u_i} $ ( $ 1 \leqslant i \leqslant n $ ) 看成是一个物元 $ {M_i} $ ，物元模型为

$ {M}_{i}=\left[\begin{array}{lll}{O}_{i}，& 权重，& w({M}_{i}) \\ & 可组合性，& D({M}_{i}) \\ & 组合数，& 1 \\ & 平均权重，& \overline{w}({M}_{i}) \end{array}\right] $

设 $ {M_1} $ , $ {M_2},\cdots $ , $ {M_n} $ 为 $ P(n,1) $ 包含的 $ n $ 个物元， $ f $ 是 $ P(n,1) $ 的最优意大利支配函数。

(2) 假设当前处理的物元为 $ {M^{\text{*}}} $ ，根据位置邻近原则发散出 $ {M^{\text{*}}} $ 的 $ l $ 个同征物元 $ M_1^{\text{*}} $ , $ M_2^{\text{*}},\cdots $ , $ M_l^{\text{*}} $ 。

(3) 通过下面的步骤选取 $ {M^{\text{*}}} $ 并判断 $ {M^{\text{*}}} $ 是否可与拓展出来的 $ M_1^{\text{*}} $ , $ M_2^{\text{*}},\cdots $ , $ M_l^{\text{*}} $ 组合。

首先对参数初始化，令 $ m = 0 $ 并把 $ P(n,1) $ 中物元 $ {M_i} $ ( $ 1 \leqslant i \leqslant n $ ) 的可组合性特征量值 $ D({M_i}) $ 都赋值为0。

第一步：选择权重特征值大于等于3的物元作为 $ {M^{\text{*}}} $ ，本步骤中的 $ {M_i} $ 为 $ {M^{\text{*}}} $ ， $ {M_{i - 1}} $ 和 $ {M_{i + 1}} $ 为由 $ {M^{\text{*}}} $ 拓展出的物元 $ M_1^{\text{*}} $ , $ M_2^{\text{*}} $ 。

从 $ i = 1 $ 开始，对所有满足 $ w({M_i}) \geqslant 3 $ 且 $ D({M_i}) = 0 $ 的物元 $ {M_i} $ 执行以下操作：

$ m = m + 1 。$

由物元 $ {M_i} $ 拓展出其相邻物元 $ {M_{i - 1}} $ 和 $ {M_{i + 1}} $ 。

如果拓展出的物元 $ {M_{i - 1}} $ 和 $ {M_{i + 1}} $ 的特征值 $w({M_{i - 1}}) {\text{ = }} w({M_{i + 1}}) {\text{ = }}0$ 且 $ D({M_{i - 1}}) {\text{ = }}D({M_{i{\text{ + }}1}}) {\text{ = }}0 $ ，则将 $ {M_i} $ ， $ {M_{i - 1}} $ 和 $ {M_{i + 1}} $ 组合为聚合物元 $ {B_m} $ ，即 $ {B_m} = {M_{i - 1}} \oplus {M_i} \oplus {M_{i{\text{ + }}1}} $ ，并将物元 $ {M_i} $ ， $ {M_{i - 1}} $ 和 $ {M_{i + 1}} $ 的特征值标为1，即 $D({M_{i - 1}}) {\text{ = }}D({M_i}) {\text{ = }} D({M_{i{\text{ + }}1}}) {\text{ = }}1$ 。

如果 $ w({M_{i - 1}}) {\text{ = }}D({M_{i - 1}}) {\text{ = }}0 $ 且 $ w({M_{i{\text{ + }}1}}) \geqslant 1 $ ，则 ${B_m} = {M_{i - 1}} \oplus {M_i}$ ， $ D({M_{i - 1}}) {\text{ = }}D({M_i}) {\text{ = }}1 $ 。

如果 $ w({M_{i{\text{ + }}1}}) {\text{ = }}D({M_{i{\text{ + }}1}}) {\text{ = }}0 $ 且 $ w({M_{i - 1}}) \geqslant 1 $ ，则 ${B_m} = {M_i} \oplus {M_{i + 1}}$ ， $ D({M_i}) {\text{ = }}D({M_{i + 1}}) {\text{ = }}1 $ 。

如果是其他情况，则 $ {B_m} = {M_i} $ ， $ D({M_i}) {\text{ = }}1 $ 。

此时，

$ {B}_{m}=\left[\begin{array}{lll}{O}_{m}, & 权重\text{，} & w({B}_{m}) \\ & 可组合性\text{，} & D({B}_{m}) \\ & 组合数\text{，} & N({B}_{m}) \\ & 平均权重\text{，} & \overline{w}({B}_{m}) \end{array}\right] $

式中： $ w({B_m}) \geqslant 3 $ ， $ N({B_m}) \leqslant 3 $ ， $ \overline w ({B_m}) \geqslant 1 $ 。

第二步：选择权重特征值等于2的物元作为 $ {M^{\text{*}}} $ ，本步骤中的 $ {M_i} $ 为 $ {M^{\text{*}}} $ ， $ {M_{i + 1}} $ 为由 $ {M^{\text{*}}} $ 拓展出的物元 $ M_1^{\text{*}} $ 。

从 $ i = 1 $ 开始，对所有满足 $ w({M_i}) = 2 $ 且 $ D({M_i}) = 0 $ 的物元 $ {M_i} $ 执行以下操作：

$ m = m + 1 。$

根据式(2)，如果与 $ {M_i} $ 相邻的物元 $ {M_{i - 1}} $ 权值为0，则 $ w({M_{i - 2}}) \geqslant 2 $ ，由此可知， $ D({M_{i - 1}}) {\text{ = 1}} $ 。

因此，当 $ w({M_i}) = 2 $ 且 $ D({M_i}) = 0 $ 时，只需考察拓展物元 $ {M_{i + 1}} $ 。如果 $ w({M_{i{\text{ + }}1}}) {\text{ = }}D({M_{i{\text{ + }}1}}) {\text{ = }}0 $ ，则 ${B_m} = {M_i} \oplus {M_{i + 1}}$ ， $ D({M_i}) {\text{ = }}D({M_{i + 1}}) {\text{ = }}1 $ 。如果是其他情况，则 ${B_m} = {M_i}$ ， $ D({M_i}) {\text{ = }}1 $ 。

此时，

$ {B}_{m}=\left[\begin{array}{lll}{O}_{m}, & 权重\text{，} & w({B}_{m}) \text=2 \\ & 可组合性\text{，} & D({B}_{m}) \\ & 组合数\text{，} & N({B}_{m}) \leqslant 2 \\ & 平均权重\text{，} & \overline{w}({B}_{m}) \geqslant 1 \end{array}\right] $

经过前两步处理以后，所有满足可组合性特征值为0的物元其权值特征值均为1。

第三步：选择权重特征值等于1的物元作为 $ {M^{\text{*}}} $ ，本步骤中的 $ {M_i} $ 为 $ {M^{\text{*}}} $ ， $ {M_i} $ 本身满足权重特征值为1，不需要和其他物元组合。

从 $ i = 1 $ 开始，对所有满足 $ w({M_i}) = 1 $ 且 $ D({M_i}) = 0 $ 的物元 $ {M_i} $ 执行以下操作：

$ m = m + 1 \text{，} {B_m} = {M_i} \text{，} D({M_i}) {\text{ = }}1 。$

此时，

$ {B}_{m}=\left[\begin{array}{lll}{O}_{m}, & 权重\text{，} & w({B}_{m}) \text=1 \\ & 可组合性\text{，} & D({B}_{m}) \\ & 组合数\text{，} & N({B}_{m}) \text=1 \\ & 平均权重\text{，} & \overline{w}({B}_{m}) \text=1 \end{array}\right] $

由第一步到第三步可知，

$ \sum\nolimits_{t = 1}^m {w({B_m}) } \geqslant n $

因此，

$ w(f) = \sum\nolimits_{i = 1}^n {w({M_i}) } = \sum\nolimits_{i = 1}^m {w({B_i}) } \geqslant n $

即

$ {\gamma _I}(P(n,1) ) \geqslant n $

由式(1)和(3)知， $ P(n,1) $ 意大利支配数为n，即 $ {\gamma _I}(P(n,1) ) {\text{ = }}n $ 。

4 结语

本文利用可拓学中分合链方法证明了图的意大利支配数下界与上界相等，从而确定了图的意大利控制数。以广义彼得森图 $ P(n,1) $ 为例，阐述了如何利用分合链方法证明图的意大利支配数下界与上界相等。将图形中某些相关联的顶点看作物元，利用分合链中的组合原则把权重为零的物元与邻近的物元组合，形成新的聚合物元，使得聚合物元的权重满足要求，从而获得图形的意大利支配数的下界。

该方法的可移植性好，可用于确定多种图形的不同支配数。在图的支配数教学中使用该方法，可以使学生既快又好地理解和掌握。学生利用这种证明方法还可以得到其他图形(如梯形图、格图等)的多种支配数(双罗马支配数、彩虹支配数等)。