第13卷 第1期2000年1月
文章编号:100127372(2000) 0120095203
中 国 公 路 学 报
Ch ina Jou rnal of H ighw ay and T ran spo rt
V o l 113 N o 11Jan. 2000
公路网连通性研究
徐 军, 罗嵩龄
(中国人民解放军汽车管理学院军交运输研究室, 安徽蚌埠 233011)
摘 要:在分析现有的公路网连通性评价指标的基础上, 应用图论理论, 提出网络连通性评价指标的新定义, 并分析和比较了它与传统定义之间的差异。关键词:公路网; 评价指标; 连通性
中图分类号:U 491113 文献标识码:A
A study for network
XU Song 2ling
(T on , Peop le’sL iberati on A r m y A uto 2m anagem ent Institute , Bengbu 233011, Ch ina )
B on the analysis of the ex isting h ighw ay netw o rk connectness evaluati on indexes , acco rding to the grap h theo ry , w e p ropo se a new defin iti on of the h ighw ay netw o rk connectness evaluati on index in th is p aper , and com pare the differences betw een the o ld defin iti on s and the new one .
Key words :h ighw ay netw o rk ; evaluati on index ; connectness
1 问题的提出
为了科学、全面地评价公路网, 需要从定性和定
量分析两个方面入手, 恰当选取并准确描述评价指标。在现有的公路网评价指标体系中, 不论从什么角度确定评价指标体系, 连通度都是不可或缺的。
公路网由节点和边组成, 它们的连通方式很多, 连通性反映了网络中各节点的连通状况, 体现了网络的一种结构上的特征。只有从解析表达式上清晰地阐明公路网连通度, 才能从理论上给出网络结构性能的评价。在实际应用中, 特别是在研究国防交通网络模型时, 更体现出它所具有的意义。
在现今众多文献资料中, 刻画公路网连通性方面的指标有“连通度”、“通达度”、“回路数”、“Α指数”、“Β指数”、“Χ指数”等, 它们从不同角度反映了公路网的连通程度。在一些文献中, 存在着叙述不够严谨之处, 因此, 有统一认识的必要。笔者在研究现有的连通性指标的概念、计算方法和物理意义的基础上, 提出一个与原有概念完全不同的新定义, 从另
收稿日期:1998210227
作者简介:徐 军(19632) , 男, 副教授, 理学博士
一角度深化对公路网连通性的研究。
在本文中, 公路网络记作N (V , E ) , 其中V 为网络N 的节点集, E 为N 的边集; 所涉及到的网络均是简单连通的(不包含环和多重边) , 而未定义的概念和术语参见文献[1, 3, 4]。
2 传统定义的分析
在文献[1, 3, 4]中, 立足于网络分析所提出的反映公路网连通程度的指标有如下几个:
定义1 规划区域内各节点依靠公路相互连通的强度, 称为公路网N (V , E ) 的连通度, 记为C 。其计算式为
C =
=nH
nA
式中:L 为规划区域内公路的总里程(km ) ; A 为规
划区域面积(km 2) ; n 为规划区域内应连通的节点数; H 为相邻两节点的平均空间直线距离(km ) ; Φ为规划区域内公路网的变形系数, 定义为各节点间实际线路总里程与直线总里程之比, 其值与道路的
96 中 国 公 路 学 报 2000年歪曲情况及节点分布的几何形状有关。
理想状态时, 道路是直线形的, Φ=1, 所以C =
(式中:e 为公路网的边数) 。因此, 一般地说, 公路n
但是, 这些指标也有不尽人意之处。比如, 利用它们去考察图1中的两个公路网N 1和N 2的连通程度时, 各个指标值完全一样, 它似乎表示, N 1和N 2有基本一致的连通状态。其实不然, 直观上不难发现, 网络N
1
网连通度的计算公式可以比较简单(且近似程度较高) 地用公路网中的边数与节点数之比来表示, 即C ≈
(在某些文献中, 即以此为连通度的定义) 。n
定义2 网络N 的实际回路数与N 可能存在
和N
2
在结构上有着明显的不同, 其
的最大回路数之比, 称为网络N 的Α指数。
即
Α=
2n -5
最大的差异正是连通性。在网络N 1中移去任意一条边, N 1仍是连通的; 而网络N 2移去边a 后, 它是不连通的。这种网络结构上的差异, 无法通过公路网的连通性评价指标体现出来, 见表1。
在文献[4]中, 称e -n +1为网络N 的回路数。必须指出其“回路”同。为了避免歧义, 表示网络N n 3n -6, 因此, 数为2n -5。基回路数表示了网络中回路的多寡, 在一定意义上反映了网络连通程度。
Α指数是度量网络回路性的指标, 其数值变化在0—1之间。指数Α接近0时, 意味着没有回路; 指数Α接近1时, 说明网络已达到最大限度的回路数目, 作为平面网络, 其每个面都是三角形。
定义3 网络N 内每一个节点所邻接的边的平均数目, 称为N 的Β指数, 即Β=
n
N N
1
1 公路网
公路网N 1与N 2的评价指标
Α指数
77
Β指数
33
Χ指数
1212
连通度C
66
2
3 连通度评价指标的新定义
如上面的简单示例所示, 公路网连通性评价指标的传统定义不足以反映上述网络结构方面的特征。下面从一个新的角度, 引进公路网连通度的定义。
定义5 记k ij 为在网络N 中使得节点v i 、v j (i ≠j ) 不连通所要移去的最少边数, 称k ij 为点对v i 、v j 在网络N 中的连通度。定义公路网的连通度为网络N 中所有点对在网络中的连通度的平均值, 记为K , 即
K =k ij (i ≠j )
n (n -1) v i ∑, v j ∈V 式中:n 为网络N 的节点数。
在定义5中, 公路网连通度评价指标K 的物理意义是:在网络中任意两点间平均有K 条边不相交的道路相连通。笔者认为此值能较确切地从网络结构上反映公路网的连通程度。
采用网络理论的最大流算法[5], 可以得到连通度K 的一个算法如下:在网络N (V , E ) 中, 默认每条边上的容量权为1, 运用最大流算法, 可计算出点v i 、v j (i ≠j ) 之间的最大流量, 根据最大流最小截定理, 此值即为定义5中的k ij , 然后采用循环, 计算出连通度K 。此算法是一个有效算法, 复杂度为
5
O (n ) 。
Β指数是度量一个节点与其它节点联系难易程度的指标。在文献[2]中, 也称此指标为公路网的节点通达度, 它与定义1中的公路网的连通度指标有近似两倍的关系。
定义4 网络N 的实际边数与它可能存在的最大边数的比值, 称为N 的Χ指数, 即Χ=
对于连通网络来说,
3n -6
网络呈树状; 当Χ接近1时, 网络近似于最大平面网
络。
上述诸定义中的各个指标都从不同角度反映了公路网的连通程度, 它们之间有着很密切的关系。从解析表达式中可以看出, 当网络N 的节点数n 比较大时, 不难得出如下近似关系
Α≈
C ; Β≈2C ; Χ≈C 23
因此, 在精度要求不高的情况下, 计算这些指标时, 可参照上述近似公式。
第1期 徐 军, 等:公路网连通性研究 97根据此定义, 从连通度K 的量值, 即可反映出现有公路网连通性评价指标刻画不了的网络结构方面的特征。在此定义下, 图1中的网络N 1和N 2的
连通度分别为K 1=和K 2=有着明显的区别。
155
下面评价定义1与定义5中连通度概念的差异。定义1中给出的公路网连通度的概念有其不足也有其优点, 如计算简单。而定义5中的连通度K 计算起来较复杂。在反映网络布局方面, 虽然C 接近于1及K 接近于1时表示网络布局呈树状、C 接近于3及K 较大(K >5) 时表示网络布局呈三角形网状, 但是C 接近于2时网络布局呈方格网状的特征, 却不能从K 的量值中反映出来。
路网的连通性能不应该仅仅着眼于“单路连通”, 而应更多地考虑“多路连通”和在什么情况下不连通, 这正是新定义的本质所在。
其次, 民用交通的另一基本要求——均衡性和快速性, 也被国防交通的鲜明特征——运量上的非均衡性和时限上的超快速性代替。在战争爆发之初, 军事公路运输量剧增, 随着战争的进程, 不同作战方向的运输量也会在极短的时间内发生极大的改变。军事常识要求一切军事行动立足于“快”, 赢得时间就赢得胜利。因此, , 就是“超快速”。。
, , 非常慎“连通度”的。这种定义的叙述方式, 在国防交通综合网的评价指标体系中是非常关键的一个。参考文献
[1] 施耀忠, 等. 公路网规划的技术评价指标与评价标准研
4, , 决定的。, 客观地评价国防交通网络的性能, 才能更好地发挥国防交通网络在打赢高技术局部战争、应付突发事件中的战略作用。国防交通是依据国防和战争目的, 对国家交通的一种配置。国防交通网络的主体是国家交通网络。但是, 二者之间存在着明显的差异。
首先, 民用交通的基本要求——适应性和舒适性, 就被国防交通的鲜明特征——地域上的非固定性和能力上的非稳定性所代替。因为应付局部战争或突发事件, 其战役方向都在不断变化之中。同时, 随着高技术武器装备的投入使用, 使公路网(尤其是高等级公路) 面临更大程度上的威胁。这个特点使公
究[J ]. 中国公路学报, 1995, 8(增1) .
[2] 周 伟, 等. 基于模糊理论和神经网络技术的公路网综
合评价方法研究[J ]. 中国公路学报, 1997, 10(4) .
[3] 蔡良斌, 等. 公路网评价理论与方法[J ]. 陕西公路,
1996, (3) .
[4] 杨吾扬, 张国伍, 等. 交通运输地理学[M ]. 北京:商务
印书馆, 1986.
[5] 谢 政, 李建平. 网络算法与复杂性理论[M ]. 北京:国
防科技大学出版社, 1995.
本刊加入万方数据资源系统(Ch ina Info ) 数字化期刊群的声明
为了实现科技期刊编辑、出版发行工作的电子化, 推进科技信息交流的网络化进程, 《中国公路学报》现已入网“万方数据资源系统(Ch ina Info ) 数字化期刊群”, 所以, 向本刊投稿并录用的稿件文章, 将一律由编辑部统一纳入万方数据资源系统(Ch ina Info ) , 进入因特网提供信息服务。凡有不同意者, 请另投它刊。本刊所付稿酬包含刊物内容上网服务报酬, 不再另付。
“九五”重点科技攻关项目, 截止1999年7月万方数据资源系统(Ch ina Info ) 数字化期刊群是国家
已有600种期刊全文上网(网址:h ttp : www . ch inainfo . gov . cn peri odical ) , 将在年内增至1000余种科技期刊。本刊全文内容按照统一格式制作编入万方数据资源系统(Ch ina Info ) , 读者可上因特网进入万方数据资源系统(Ch ina Info ) 免费(一年后开始酌情收费) 查询浏览本刊内容, 也欢迎各界朋友通过万方数据资源系统(Ch ina Info ) 向我刊提出宝贵意见、建议, 或征订本刊。
《中国公路学报》编辑部
第13卷 第1期2000年1月
文章编号:100127372(2000) 0120095203
中 国 公 路 学 报
Ch ina Jou rnal of H ighw ay and T ran spo rt
V o l 113 N o 11Jan. 2000
公路网连通性研究
徐 军, 罗嵩龄
(中国人民解放军汽车管理学院军交运输研究室, 安徽蚌埠 233011)
摘 要:在分析现有的公路网连通性评价指标的基础上, 应用图论理论, 提出网络连通性评价指标的新定义, 并分析和比较了它与传统定义之间的差异。关键词:公路网; 评价指标; 连通性
中图分类号:U 491113 文献标识码:A
A study for network
XU Song 2ling
(T on , Peop le’sL iberati on A r m y A uto 2m anagem ent Institute , Bengbu 233011, Ch ina )
B on the analysis of the ex isting h ighw ay netw o rk connectness evaluati on indexes , acco rding to the grap h theo ry , w e p ropo se a new defin iti on of the h ighw ay netw o rk connectness evaluati on index in th is p aper , and com pare the differences betw een the o ld defin iti on s and the new one .
Key words :h ighw ay netw o rk ; evaluati on index ; connectness
1 问题的提出
为了科学、全面地评价公路网, 需要从定性和定
量分析两个方面入手, 恰当选取并准确描述评价指标。在现有的公路网评价指标体系中, 不论从什么角度确定评价指标体系, 连通度都是不可或缺的。
公路网由节点和边组成, 它们的连通方式很多, 连通性反映了网络中各节点的连通状况, 体现了网络的一种结构上的特征。只有从解析表达式上清晰地阐明公路网连通度, 才能从理论上给出网络结构性能的评价。在实际应用中, 特别是在研究国防交通网络模型时, 更体现出它所具有的意义。
在现今众多文献资料中, 刻画公路网连通性方面的指标有“连通度”、“通达度”、“回路数”、“Α指数”、“Β指数”、“Χ指数”等, 它们从不同角度反映了公路网的连通程度。在一些文献中, 存在着叙述不够严谨之处, 因此, 有统一认识的必要。笔者在研究现有的连通性指标的概念、计算方法和物理意义的基础上, 提出一个与原有概念完全不同的新定义, 从另
收稿日期:1998210227
作者简介:徐 军(19632) , 男, 副教授, 理学博士
一角度深化对公路网连通性的研究。
在本文中, 公路网络记作N (V , E ) , 其中V 为网络N 的节点集, E 为N 的边集; 所涉及到的网络均是简单连通的(不包含环和多重边) , 而未定义的概念和术语参见文献[1, 3, 4]。
2 传统定义的分析
在文献[1, 3, 4]中, 立足于网络分析所提出的反映公路网连通程度的指标有如下几个:
定义1 规划区域内各节点依靠公路相互连通的强度, 称为公路网N (V , E ) 的连通度, 记为C 。其计算式为
C =
=nH
nA
式中:L 为规划区域内公路的总里程(km ) ; A 为规
划区域面积(km 2) ; n 为规划区域内应连通的节点数; H 为相邻两节点的平均空间直线距离(km ) ; Φ为规划区域内公路网的变形系数, 定义为各节点间实际线路总里程与直线总里程之比, 其值与道路的
96 中 国 公 路 学 报 2000年歪曲情况及节点分布的几何形状有关。
理想状态时, 道路是直线形的, Φ=1, 所以C =
(式中:e 为公路网的边数) 。因此, 一般地说, 公路n
但是, 这些指标也有不尽人意之处。比如, 利用它们去考察图1中的两个公路网N 1和N 2的连通程度时, 各个指标值完全一样, 它似乎表示, N 1和N 2有基本一致的连通状态。其实不然, 直观上不难发现, 网络N
1
网连通度的计算公式可以比较简单(且近似程度较高) 地用公路网中的边数与节点数之比来表示, 即C ≈
(在某些文献中, 即以此为连通度的定义) 。n
定义2 网络N 的实际回路数与N 可能存在
和N
2
在结构上有着明显的不同, 其
的最大回路数之比, 称为网络N 的Α指数。
即
Α=
2n -5
最大的差异正是连通性。在网络N 1中移去任意一条边, N 1仍是连通的; 而网络N 2移去边a 后, 它是不连通的。这种网络结构上的差异, 无法通过公路网的连通性评价指标体现出来, 见表1。
在文献[4]中, 称e -n +1为网络N 的回路数。必须指出其“回路”同。为了避免歧义, 表示网络N n 3n -6, 因此, 数为2n -5。基回路数表示了网络中回路的多寡, 在一定意义上反映了网络连通程度。
Α指数是度量网络回路性的指标, 其数值变化在0—1之间。指数Α接近0时, 意味着没有回路; 指数Α接近1时, 说明网络已达到最大限度的回路数目, 作为平面网络, 其每个面都是三角形。
定义3 网络N 内每一个节点所邻接的边的平均数目, 称为N 的Β指数, 即Β=
n
N N
1
1 公路网
公路网N 1与N 2的评价指标
Α指数
77
Β指数
33
Χ指数
1212
连通度C
66
2
3 连通度评价指标的新定义
如上面的简单示例所示, 公路网连通性评价指标的传统定义不足以反映上述网络结构方面的特征。下面从一个新的角度, 引进公路网连通度的定义。
定义5 记k ij 为在网络N 中使得节点v i 、v j (i ≠j ) 不连通所要移去的最少边数, 称k ij 为点对v i 、v j 在网络N 中的连通度。定义公路网的连通度为网络N 中所有点对在网络中的连通度的平均值, 记为K , 即
K =k ij (i ≠j )
n (n -1) v i ∑, v j ∈V 式中:n 为网络N 的节点数。
在定义5中, 公路网连通度评价指标K 的物理意义是:在网络中任意两点间平均有K 条边不相交的道路相连通。笔者认为此值能较确切地从网络结构上反映公路网的连通程度。
采用网络理论的最大流算法[5], 可以得到连通度K 的一个算法如下:在网络N (V , E ) 中, 默认每条边上的容量权为1, 运用最大流算法, 可计算出点v i 、v j (i ≠j ) 之间的最大流量, 根据最大流最小截定理, 此值即为定义5中的k ij , 然后采用循环, 计算出连通度K 。此算法是一个有效算法, 复杂度为
5
O (n ) 。
Β指数是度量一个节点与其它节点联系难易程度的指标。在文献[2]中, 也称此指标为公路网的节点通达度, 它与定义1中的公路网的连通度指标有近似两倍的关系。
定义4 网络N 的实际边数与它可能存在的最大边数的比值, 称为N 的Χ指数, 即Χ=
对于连通网络来说,
3n -6
网络呈树状; 当Χ接近1时, 网络近似于最大平面网
络。
上述诸定义中的各个指标都从不同角度反映了公路网的连通程度, 它们之间有着很密切的关系。从解析表达式中可以看出, 当网络N 的节点数n 比较大时, 不难得出如下近似关系
Α≈
C ; Β≈2C ; Χ≈C 23
因此, 在精度要求不高的情况下, 计算这些指标时, 可参照上述近似公式。
第1期 徐 军, 等:公路网连通性研究 97根据此定义, 从连通度K 的量值, 即可反映出现有公路网连通性评价指标刻画不了的网络结构方面的特征。在此定义下, 图1中的网络N 1和N 2的
连通度分别为K 1=和K 2=有着明显的区别。
155
下面评价定义1与定义5中连通度概念的差异。定义1中给出的公路网连通度的概念有其不足也有其优点, 如计算简单。而定义5中的连通度K 计算起来较复杂。在反映网络布局方面, 虽然C 接近于1及K 接近于1时表示网络布局呈树状、C 接近于3及K 较大(K >5) 时表示网络布局呈三角形网状, 但是C 接近于2时网络布局呈方格网状的特征, 却不能从K 的量值中反映出来。
路网的连通性能不应该仅仅着眼于“单路连通”, 而应更多地考虑“多路连通”和在什么情况下不连通, 这正是新定义的本质所在。
其次, 民用交通的另一基本要求——均衡性和快速性, 也被国防交通的鲜明特征——运量上的非均衡性和时限上的超快速性代替。在战争爆发之初, 军事公路运输量剧增, 随着战争的进程, 不同作战方向的运输量也会在极短的时间内发生极大的改变。军事常识要求一切军事行动立足于“快”, 赢得时间就赢得胜利。因此, , 就是“超快速”。。
, , 非常慎“连通度”的。这种定义的叙述方式, 在国防交通综合网的评价指标体系中是非常关键的一个。参考文献
[1] 施耀忠, 等. 公路网规划的技术评价指标与评价标准研
4, , 决定的。, 客观地评价国防交通网络的性能, 才能更好地发挥国防交通网络在打赢高技术局部战争、应付突发事件中的战略作用。国防交通是依据国防和战争目的, 对国家交通的一种配置。国防交通网络的主体是国家交通网络。但是, 二者之间存在着明显的差异。
首先, 民用交通的基本要求——适应性和舒适性, 就被国防交通的鲜明特征——地域上的非固定性和能力上的非稳定性所代替。因为应付局部战争或突发事件, 其战役方向都在不断变化之中。同时, 随着高技术武器装备的投入使用, 使公路网(尤其是高等级公路) 面临更大程度上的威胁。这个特点使公
究[J ]. 中国公路学报, 1995, 8(增1) .
[2] 周 伟, 等. 基于模糊理论和神经网络技术的公路网综
合评价方法研究[J ]. 中国公路学报, 1997, 10(4) .
[3] 蔡良斌, 等. 公路网评价理论与方法[J ]. 陕西公路,
1996, (3) .
[4] 杨吾扬, 张国伍, 等. 交通运输地理学[M ]. 北京:商务
印书馆, 1986.
[5] 谢 政, 李建平. 网络算法与复杂性理论[M ]. 北京:国
防科技大学出版社, 1995.
本刊加入万方数据资源系统(Ch ina Info ) 数字化期刊群的声明
为了实现科技期刊编辑、出版发行工作的电子化, 推进科技信息交流的网络化进程, 《中国公路学报》现已入网“万方数据资源系统(Ch ina Info ) 数字化期刊群”, 所以, 向本刊投稿并录用的稿件文章, 将一律由编辑部统一纳入万方数据资源系统(Ch ina Info ) , 进入因特网提供信息服务。凡有不同意者, 请另投它刊。本刊所付稿酬包含刊物内容上网服务报酬, 不再另付。
“九五”重点科技攻关项目, 截止1999年7月万方数据资源系统(Ch ina Info ) 数字化期刊群是国家
已有600种期刊全文上网(网址:h ttp : www . ch inainfo . gov . cn peri odical ) , 将在年内增至1000余种科技期刊。本刊全文内容按照统一格式制作编入万方数据资源系统(Ch ina Info ) , 读者可上因特网进入万方数据资源系统(Ch ina Info ) 免费(一年后开始酌情收费) 查询浏览本刊内容, 也欢迎各界朋友通过万方数据资源系统(Ch ina Info ) 向我刊提出宝贵意见、建议, 或征订本刊。
《中国公路学报》编辑部