复杂网络的研究在复杂系统中有重要的应用^[1-3]。在复杂网络中，物流多重图网络的突出特点是节点间可以有多种运输方式可以选择，可以选择铁路运输、公路运输、航空运输等。

在应用图论工具研究复杂网络时，通常是针对无多重边的网络研究，但是多重边复杂网络比通常的单边复杂网络在拓扑结构、节点动态特性等性质方面有着更为复杂的形态，从而需要更合适的模型表达方式和更实用的解决方案。

马啸来^[4]建立了同一位置有多个物流节点和物流路径可供选择的、以多重图作为拓扑形式的物流链选择决策模型，并讨论了将其转化为简单图的求解算法。高洋等^[5]根据网络中边的不同性质提出了网络拆分的思想, 通过引入时滞进行拆分, 从而建立了多重边复杂网络的动力学模型；安新磊等^[6]在通常公交网络模型的基础上, 建立了一种新的多重边公交线路网络模型；Acosta-Mendoza等^[7]提出一种用于多重图集合中的近似模式挖掘的新算法；Suil^[8]提出在一般多重图中特征值边缘连通性的新方法；Haxella^[9]提出没有小密集子集的边缘着色多重图，给出多重图色度指数的推论结果；Yang^[10]提出通过多重图排名的鲁棒视觉跟踪原创研究文章来探讨图的排名和多个组合方法；Chakareski^[11]给出多重图分析选择顶点的方法; 文献[12]针对SF和ER网络，研究了随机攻击条件下层级网络间的依存强度对系统的作用效果；Stippinger^[13]提出交织型层级复杂网络，它是用于描述子网络交织关系的密切程度。

本文依托物流网络的应用背景，试图引入可拓学的基元理论^[14-15]，构建一种多重图网络的新模型，这种新型多重图网络模型的特点是其重边具有异质性，并且依据可拓论的思想能够进一步研究这种网络模型的优化问题。

1 基本概念

经典图论中关于图是这样定义的。

定义1 一个有序二元组(V, E)称为一个图, 记为G=(V, E), 其中V称为G的顶点集, V≠∅, 其元素称为顶点或结点, 一般可记为V={v₁, v₂, …，v_m}；E称为G的边集, 一般可记为E={e₁, e₂, …, e_n}，其元素称为边, 它联结V中的两个点, 如果这两个点是无序的, 则称该边为无向边, 相应G称为无向图；否则, 称为有向边，相应G称为有向图。

定义2 在图G=(V, E)中，如果允许有多重边，也就是有至少二个边的二个顶点完全相同，至少有二个顶点可以由二个边相连接，则称G为多重图。图 1表示了一个一般性的多重图的示意图。

定义3 若将图G的每一条边e都对应一个实数w(e), 称w(e)为该边的权, 并称图G为赋权图(网络), 记为G=(V, E, w)。

定义4 在多重图G中的每一条边e都对应一个实数w(e), 称w(e)为该边的权, 并称图G为多重图网络。

定义5 如果多重图G的任何两个不同的顶点之间都有r重边，则称G为r-多重完全图。图 2表示3-多重图的示意图。

在经典的多重图网络研究中，一般是将多重边看成是同一性质的连接，每一边e上权w(e)也都是一致的可公度的度量，即要么都是费用，要么都是距离。但是在复杂的物流网络以及更为复杂的社会网络中，多重边的性质往往是不一致的，或者说是异质性的。那么怎么样标度多重图中边的异质性，怎样研究这种复杂网络的性质，怎样实现这种复杂网络的优化，带着这些问题，我们引入可拓学中的基元概念及其可拓性, 将其应用到具有异质边的多重图网络模型的构建。

可拓学是研究解决矛盾问题的规律和方法的学科，可拓学理论的逻辑细胞是基元^[4]，基元包括物元、事元、关系元。

定义6 以物O_m为对象，n个特征C_m1, C_m2, …, C_mn及O_m关于C_mi(i=1, 2, …, n)对应的量值V_mi(i=1, 2, …, n)所构成的n维阵列：

$ M = \left[ {\begin{array}{*{20}{c}} {{O_{m'}},}&{{O_{m1'}},}&{{O_{m2'}}}\\ {}&{{c_{m2'}},}&{{v_{m2}}}\\ {}& \vdots & \vdots \\ {}&{{c_{mn'}},}&{{v_{mn}}} \end{array}} \right] = \left( {{O_{m'}},{C_m},{V_m}} \right) $

称为n维物元^[15]，其中

$ {C_m} = \left[ {\begin{array}{*{20}{c}} {{c_{m1}}}\\ {{c_{m2}}}\\ \vdots \\ {{c_{mn}}} \end{array}} \right],\;\;\;\;\;{V_m} = \left[ {\begin{array}{*{20}{c}} {{v_{m1}}}\\ {{v_{m2}}}\\ \vdots \\ {{v_{mn}}} \end{array}} \right] $

定义7 设A₀是平面上的一个凸区域，Γ₀是A₀的边界，P(x₁, x₂)为平面上的一点，则点P(x₁, x₂)与区域A₀的二维可拓距^[16-17]规定为

$ \rho \left( {P,{A_0}} \right) = \left\{ \begin{array}{l} \mathop {\inf }\limits_{{P_1} \in {\mathit{\Gamma }_0}} \rho \left( {P,{A_0}} \right),\;\;\;\;P \notin {A_0}\\ - \mathop {\inf }\limits_{{P_1} \in {\mathit{\Gamma }_0}} \rho \left( {P,{A_0}} \right),\;\;P \in {A_0} \end{array} \right. $

式中：P₁为区域A₀的边界Γ₀上的一点。

定义8 二维位值。设A₀和A是平面上的矩形区域，且A₀⊂A，Γ是A的边界，P(x₁, x₂)为平面上的一点，则P(x₁, x₂)关于区域A₀和A组成的区域套的位值规定为

$D\left( {P,{A_0},A} \right) = \rho \left( {P,A} \right) - \rho \left( {P,{A_0}} \right)$

为二维位值^[18]，其中

$ \rho \left( {P,{A_0}} \right) = \left\{ \begin{array}{l} \mathop {\inf }\limits_{{P_2} \in \mathit{\Gamma }} \rho \left( {P,{P_2}} \right),\;\;\;\;P \notin A\\ - \mathop {\inf }\limits_{{P_2} \in \mathit{\Gamma }} \rho \left( {P,{P_2}} \right),\;\;P \in A \end{array} \right. $

P₂为区域A的边界Γ上的一点。D(P, A₀, A)就描述了点P(x₁, x₂)与区域A₀和A组成的区域套的位置关系。

基元是有序三元组，是现实世界中“物”、“事”、“关系”的形式化表示，是“质”与“量”的统一体。为了描述多重图中边的异质性，我们将基元概念引入多重图网络中，构造一种新型网络模型。

2 模型构建

针对每个节点之间有r个边的r-多重完全图网络来研究, 将模型称之为基于物元特征的r-异质边多重完全图网络模型。

记所构造的网络为G=(V, E, F)，在G中，顶点集合V中的元素为r维物元M, 即V={M₁, M₂, …, M_n}

$ {M_i} = \left[ {\begin{array}{*{20}{c}} {{O_{mi}},}&{{c_{m1}},}&{{v_{m1}}}\\ {}&{{c_{m2}},}&{{v_{m1}}}\\ {}& \vdots & \vdots \\ {}&{{c_{mr}},}&{{v_{mr}}} \end{array}} \right] $

式中：c_m1, c_m2, …, c_mr是所有物元M共有的r个特征，任何两个顶点M_i和M_j之间有r重边相连，r个边是不同质的，分别对应特征c_m1, c_m2, …, c_mr，连接示意图见图 3。

可以将该网络边的集合记为E={e_{i, j, 1}, e_{i, j, 2}, …, e_{i, j, r}|i, j=1, 2, …, n}，其中各边上的权的集合记为F,

$ F = \left\{ {{f_{ij}}\left( {{c_{mh}}} \right)\left| {h = 1,2, \cdots r;i,j = 1,2, \cdots ,n} \right.} \right\} $

这样构成的网络属于r-多重完全图网络。但是与普通r-多重完全图网络的不同点在于任何两顶点间的r条边是异质的，其异质性由r个特征c_m1, c_m2, …, c_mr所决定，而网络中所有节点(顶点)是同质的。为了描述两个顶点间的关系, 还需要引入两个论域上关系的概念。

定义9 可拓关系。设U、V是任意两个集合，且k是U×V到是实数域R的一个映射，称

$ \tilde r = \left\{ {\left( {u,v,y} \right)\left| {\left( {u,v} \right)} \right. \in U \times V,y = k\left( {u,v} \right)} \right\} $

为U和V之间的一个二元可拓关系^[18]。所有U和V二元可拓关系的全体记为￡(U×V):称$\tilde r$={(u, v, y)|(u, v)∈U×V, y=k(u, v)≥0}为$\tilde r$的正域；$\tilde r$={(u, v, y)(u, v)∈U×V, y=k(u, v)≤0}为$\tilde r$的负域；J₀($\tilde r$)={(u, v)|(u, v)∈U×V, k(u, v)}=0为$\tilde r$的零界；这里的关联函数y=k(u, v)是二维的, 在文献[19-20]中给出了一种构造二维关联函数的方法。

由于需要描述的是网络两个节点间在某一指定特征上的关系，故此将上面定义的可拓关系再扩充为如下定义的概念。

定义10 基于特征的可拓关系。设V={M₁, M₂, …, M_n}是前面在描述基于物元特征的r-异质边多重完全图网络中定义的n维物元集，V中物元的r个特征为c_m1, c_m2, …, c_mr针对其中某一c_mh, 定义

$ \begin{array}{*{20}{c}} {{{\tilde r}_{{c_{mh}}}} = \left\{ {\left( {u,v,y} \right)\left| {\left( {u,v} \right)} \right. \in V \times V,y = } \right.}\\ {\left. {{k_{{c_{mh}}}}\left( {u,v} \right) \in \left( { - \infty , + \infty } \right)} \right\}} \end{array} $

称为物元集V上关于特征c_mh的可拓关系。其中k_cmh(u, v)称为该可拓关系的关联函数。这里，二维关联函数k_cmh(u, v)是一个物元集合笛卡儿积V×V到实数域I的映射。本文根据实际应用问题设置其的具体构造。构造思想借鉴文献[19-20]，建立二维简单关联函数。

正域为有限区域A=〈a, b〉×〈c, d〉，且最大值点M(x₀, y₀)∈A，对于不同的有限区域和最大值点的取值不同，建立的关联函数也是不同的，但是对于物流节点的各个功能关联函数构造方法是相同的，关联函数的形状相似，都是锥形的，如图 4所示。对于任意一点p(x, y)的二维关联函数构造为

$ k\left( p \right) = \left\{ \begin{array}{l} \left( {y - c} \right)/\left( {{y_0} - c} \right),\;\;\;\;y \le {y_0},{x_1} \le x \le {x_4}\\ \left( {x - a} \right)/\left( {{x_0} - a} \right),\;\;\;\;x \le {x_0},{y_1} \le y \le {y_2}\\ \left( {y - d} \right)/\left( {{y_0} - d} \right),\;\;\;\;y \ge {y_0},{x_2} \le x \le {x_3}\\ \left( {x - b} \right)/\left( {{x_0} - b} \right),\;\;\;\;\;x \ge {x_0},{y_3} \le y \le {y_4} \end{array} \right. $

(1)

式中：

$ \left\{ \begin{array}{l} {x_1} = \frac{{{x_0} - a}}{{{y_0} - c}}y + \frac{{a{y_o} - c{x_0}}}{{{y_0} - c}}\\ {x_2} = \frac{{{x_0} - a}}{{{y_0} - d}}y + \frac{{a{y_o} - d{x_0}}}{{{y_0} - d}}\\ {x_3} = \frac{{{x_0} - b}}{{{y_o} - d}}y + \frac{{b{y_o} - d{x_0}}}{{{y_0} - d}}\\ {x_4} = \frac{{{x_0} - b}}{{{y_0} - c}}y + \frac{{b{y_o} - c{x_0}}}{{{y_0} - c}} \end{array} \right. $

$ \left\{ \begin{array}{l} {y_1} = \frac{{{y_0} - c}}{{{x_0} - a}}x + \frac{{c{x_0} - a{y_o}}}{{{x_0} - a}}\\ {y_2} = \frac{{{y_0} - d}}{{{x_0} - a}}x + \frac{{d{x_0} - a{y_o}}}{{{x_0} - a}}\\ {y_3} = \frac{{{y_0} - d}}{{{x_o} - b}}x + \frac{{d{x_0} - b{y_o}}}{{{x_0} - b}}\\ {y_4} = \frac{{{y_0} - c}}{{{x_0} - b}}x + \frac{{c{x_0} - b{y_o}}}{{{x_0} - b}} \end{array} \right. $

则k(p)满足如下性质：

1)k(p)在p=M处达到最大值，且k(M)=1;

2)p(x, y)∈D, 且x≠a, b, y≠c, d⇔k（p）>0；

3)p(x, y)∉D, 且x≠a, b, y≠c, d⇔k(p)＜0;

4)x=a or b, y=c or d⇔k(p)=0。

网络权F可以根据可拓关系确定：

$ {f_{ij}}\left( {{c_{mh}}} \right) = {k_{{c_{mh}}}}\left( {{M_i},{M_j}} \right),h = 1,2, \cdots ,r,i,j = 1,2, \cdots ,n $

(2)

根据可拓学的基元理论，采用物元表示网络节点，所有网络节点都具有r个相同特征，特征之间是不同质的，而每一个特征决定了两个相邻节点间相连接的一条边，用不同特征下的关联函数值表示边权，实现异质边的统一性度量，这就为异质边多重边物流网络的处理带来便利。

3 实例

我们提出的这种r-多重完全图网络模型是建立在物元特征基础之上的，对于物流网络的应用背景来说，物流节点的功能特征可以作为网络节点物元的特征。比如物流中心一般具有如下功能：运输功能、储存功能、装卸搬运功能、包装功能、流通加工功能、信息处理功能、结算功能、需求预测功能、设计咨询功能、教育与培训功能等。而对于物流配送中心来说，一般其功能特征主要是配送功能、储存功能、配组功能、分拣功能、衔接功能、集散功能、包装功能、流通加工功能、运输功能、信息处理与提供功能理功能等。物流中心和物流配送中心的共有的功能有运输功能、储存功能、包装功能、流通加工功能、信息处理功能。对于物流中心和物流配送中心的功能量化如下：运输功能、储存功能、包装功能、流通加工功能、信息处理功能分别对应着运输能力、仓库储存量、流通加工量、信息处理能力。本文以图 3为例给出M_i和M_j的物元表示。

$ {M_i} = \left[ {\begin{array}{*{20}{c}} {物流节点\;{D_i},}&{运输功能\;{c_{m1}},}&{45\% }\\ {}&{储存功能\;{c_{m2}},}&{100}\\ {}&{包装功能\;{c_{m3}},}&{350}\\ {}&{加工功能\;{c_{m4}},}&{300}\\ {}&{信息功能\;{c_{m5}},}&{75\% } \end{array}} \right] $

$ {M_j} = \left[ {\begin{array}{*{20}{c}} {物流节点\;{D_i},}&{运输功能\;{c_{m1}},}&{85\% }\\ {}&{储存功能\;{c_{m2}},}&{90}\\ {}&{包装功能\;{c_{m3}},}&{400}\\ {}&{加工功能\;{c_{m4}},}&{350}\\ {}&{信息功能\;{c_{m5}},}&{80\% } \end{array}} \right] $

最大值点在中点取得，根据式(1) 构造的二维关联函数构造方法，计算出节点M_i与M_j之间5个功能的5个关联函数，每个特征的关联函数的正域取值及功能特征的取值是根据物流网络的实际情况来定值。

1) 计算运输功能的关联度，其中正域为有限区域A₁=〈a₁, b₁〉×〈c₁, d₁〉，其中，〈a₁, b₁〉=〈50%, 80%〉，〈c₁, d₁〉=〈70%, 95%〉且最大值点M₁65%, 82.5%∈A₁，将p₁45%, 85%代入建立二维关联函数构造k(p₁):

$ k\left( {{p_1}} \right) = \left\{ \begin{array}{l} \left( {y - 70\% } \right)/\left( {82.5\% - 70\% } \right),\;\;y \le 82.5\% ,\frac{4}{3}y - \frac{{13}}{{30}} \le x \le - \frac{6}{5}y + \frac{{41}}{{25}}\\ \left( {y - 50\% } \right)/\left( {65\% - 50\% } \right),\;\;\;\;\;x \le 65\% \frac{3}{4}x + \frac{{13}}{{40}} \le y \le - \frac{5}{6}x + \frac{{41}}{{30}}\\ \left( {y - 95\% } \right)/\left( {82.5\% - 95\% } \right),\;\;\;y \le 82.5\% , - \frac{6}{5}y + \frac{{41}}{{25}} \le x \le \frac{4}{3}y - \frac{{13}}{{30}}\\ \left( {x - 80\% } \right)/\left( {65\% - 80\% } \right),\;\;\;\;\;\;x \ge 65\% , - \frac{5}{6}x + \frac{{41}}{{30}} \ge y \le \frac{3}{4}x + \frac{{13}}{{40}} \end{array} \right. $

求得${k_{{c_{m1}}}}\left( {{M_i},{M_j}} \right) = \frac{1}{3}$。

2) 计算储存功能的关联度，其中正域为有限区域A₂=〈a₂, b₂〉×〈c₂, d₂〉，其中，〈a₂, b₂〉=〈40, 300〉，〈c₂, d₂〉=〈40, 250〉且最大值点M₂(170，145)∈A₂。

3) 将p₂(100, 90) 代入建立二维关联函数构造k(p₂):

$ k\left( {{p_2}} \right) = \left\{ \begin{array}{l} \left( {y - 40} \right)/\left( {145 - 40} \right),\;\;\;\;\;\;y \le 145,\frac{{26}}{{21}}y - \frac{{200}}{{21}} \le x \le - \frac{{26}}{{21}}y + \frac{{1340}}{{21}}\\ \left( {x - 40} \right)/\left( {170 - 40} \right),\;\;\;\;\;\;x \le 170,\frac{{21}}{{26}}x + \frac{{100}}{{13}} \le y \le - \frac{{21}}{{26}}x + \frac{{3670}}{{13}}\\ \left( {y - 250} \right)/\left( {145 - 250} \right),\;\;\;\;\;\;y \ge 145, - \frac{{26}}{{21}}y + \frac{{1340}}{{21}} \le x \le \frac{{26}}{{21}}y + \frac{{200}}{{21}}\\ \left( {x - 300} \right)/\left( {170 - 300} \right),\;\;\;\;\;\;x \ge 170, - \frac{{21}}{{26}}x + \frac{{3670}}{{13}} \le y \le \frac{{21}}{{26}}x + \frac{{100}}{{13}} \end{array} \right. $

求得${k_{{c_{m2}}}}\left( {{M_i},{M_j}} \right) = \frac{{60}}{{105}}$。

3) 计算包装功能的关联度，其中正域为有限区域A₃=〈a₃, b₃〉×〈c₃, d₃〉，其中〈a₃, b₃〉=〈100, 500〉，〈c₃, d₃〉=〈100, 500〉且最大值点M₃(300, 300)∈A₃，将p₃(350, 400) 代入建立二维关联函数构造k(p₃):

$ k\left( {{p_3}} \right) = \left\{ \begin{array}{l} \left( {y - 100} \right)/\left( {300 - 100} \right),\;\;\;y \le 300,y \le x \le - y + 400\\ \left( {x - 100} \right)/\left( {300 - 100} \right),\;\;\;x \le 300, \le y \le - x + 400\\ \left( {y - 500} \right)/\left( {300 - 500} \right),\;\;\;y \ge 300, - y + 400 \le x \le y\\ \left( {x - 500} \right)/\left( {300 - 500} \right),\;\;\;x \ge 300, - x + 400 \le y \le x \end{array} \right. $

求得${k_{{c_{m3}}}}\left( {{M_i},{M_j}} \right) = \frac{1}{2}$。

4) 计算加工功能的关联度，其中正域为有限区域A₄=〈a₄, b₄〉×〈c₄, d₄〉，其中〈a₄, b₄〉=〈200, 400〉，〈c₄, d₄〉=〈200, 450〉且最大值点M₄(300, 325)∈A₄将p₄(300, 350) 代入建立二维关联函数构造k(p₄):

$ k\left( {{p_4}} \right) = \left\{ \begin{array}{l} \left( {y - 200} \right)/\left( {325 - 200} \right),\;\;\;\;y \le 325,\frac{4}{5}y + 40 \le x \le - \frac{4}{5}y + 640\\ \left( {x - 200} \right)/\left( {300 - 200} \right),\;\;\;\;x \le 300,\frac{5}{4}x - 50 \le y \le - \frac{5}{4}x + 800\\ \left( {y - 450} \right)/\left( {325 - 450} \right),\;\;\;\;y \ge 325, - \frac{4}{5}y + 640 \le x \le \frac{4}{5}y + 40\\ \left( {x - 400} \right)/\left( {300 - 400} \right),\;\;\;\;x \ge 300, - \frac{5}{4}x + 800 \le y \le \frac{5}{4}x - 50 \end{array} \right. $

求得${k_{{c_{m4}}}}\left( {{M_i},{M_j}} \right) = \frac{1}{2}$。

5) 计算信息功能的关联度，其中正域为有限区域A₅=〈a₅, b₅〉×〈c₅, d₅〉, 其中〈a₅, b₅〉=〈60%, 80%〉，〈c₅, d₅〉=〈60%, 90%〉且最大值点，M₅(70%，75%)∈A₅，将p₅(75%, 80%)代入建立二维关联函数构造k(p):

$ k\left( p \right) = \left\{ \begin{array}{l} \left( {y - 60\% } \right)/\left( {75\% - 60\% } \right),\;\;\;\;y \le 75\% ,\frac{2}{3}y + \frac{1}{5} \le x \le - \frac{2}{3}y + \frac{6}{5}\\ \left( {x - 60\% } \right)/\left( {70\% - 60\% } \right),\;\;\;\;x \le 70\% ,\frac{3}{2}x - \frac{3}{{10}} \le y \le - \frac{3}{2}x - \frac{9}{5}\\ \left( {y - 90\% } \right)/\left( {75\% - 90\% } \right),\;\;\;\;y \ge 75\% , - \frac{2}{3}y + \frac{6}{5} \le x \le \frac{2}{3}y + \frac{1}{5}\\ \left( {x - 80\% } \right)/\left( {70\% - 80\% } \right),\;\;\;\;x \ge 70\% , - \frac{3}{2}x - \frac{9}{5} \le y \le \frac{3}{2}x - \frac{3}{{10}} \end{array} \right. $

求得${k_{{c_{m5}}}}\left( {{M_i},{M_j}} \right) = \frac{1}{2}$。

根据式(2) 网络权F可以根据可拓关系确定，即f_ij(c_mh)=k_cmh(M_i, M_j)，h=1, 2, …, r, i, j=1, 2, …, n, ${f_{ij}}\left( {{c_{m1}}} \right) = - \frac{1}{3},{f_{ij}}\left( {{c_{m2}}} \right) = \frac{{60}}{{105}},{f_{ij}}\left( {{c_{m3}}} \right) = \frac{1}{2},$${f_{ij}}\left( {{c_{m4}}} \right) = \frac{4}{5},{f_{ij}}\left( {{c_{m5}}} \right) = \frac{1}{2}$。

4 结束语

本文根据可拓学的基元理论构建了一种异质边多重图网络模型——基于物元特征的r-异质边多重图网络模型。这种模型适用于所有网络节点都具有r个相同特征，特征之间是不同质的，而每一个特征决定了两个相邻节点间相连接的一条边，从而形成r-异质多重完全图网络。对于物流网络背景来说，这种模型适用于物流网络各节点的功能特征基本相同或者所关注的若干功能特征相同的情况，这些功能特征是异质的，并且对应每个功能特征能够建立起物流节点间的可拓关系。

物流网络的运行是由许多运动过程和许多相对停顿过程组成的。因此，物流网络结构也是由执行运动使命的线路和执行停顿使命的节点两种基本元素所组成，全部物流活动是在线路和结点进行的物流网络水平高低、功能强弱则取决于网络中这两个基本元素的配置和两个基本元素本身。

提高物流网络的效能就应该从变换网络节点的功能特征和节点间的连接关系入手。这就体现在物流节点的物元变换和关联函数的变换。配置和关系的改变是网络结构的演变，节点功能的改变则是节点本身的功能性改变。由于我们采用物元表示网络节点，用基于特征的关联函数表示边权，这就为异质多重边物流网络的处理带来便利。同时，这种异质多重边网络的优化可以通过网络中节点特征间的联合相关度作为评价指标来指导网络的优化演变。