几类城市路口交通信号灯相位优化设计.docVIP

几类城市路口交通信号灯相位优化设计 第25卷第3期 2011年7月 济南大学(自然科学版) JOURNALOFUNIVERSITYOFJINAN(Sci.andTech. Vol_25No.3 JuI_2011 文章编号:1671—3559(2011)03—0315—04 几类城市路口交通信号灯相位优化设计 尹丽子, (1.山东师范大学管理与经济学院,山东济南250014;2.济南大学理学院,山东济南250022) 摘要:通过引入图论中圆染色的概念,将城市路口交通信号灯最优相位个数归结为其交通流模型图的圆色数.以几 种特殊的五交叉路口交通流状况为例,由车流的冲突关系给出交通流模型图,并求出这些图的圆色数.图的圆色数即为对应 交通信号灯的最优相位个数. 关键词:相位优化;圆染色;圆色数 中图分类号:0157.6文献标志码:A OptimizationDesignfortheCrossroadTrafficSignalPhaseinaCity (1.SchoolofManagementandEconomics,ShandongNormalUniversity,Jinan250014,China 2.SchoolofScience,UniversityofJinan,Jinan250022,China) Abstract:Theconceptofcircularcoloringisintroducedandthenumberofoptimizedphaseoftrafficflowsignalatanintersection inacityisboileddowntothecircularchromaticnumberofthetrafficflowmodelgraphs.Thetrafficconditionsonafewclassesofspe— eialcrossroadsareanalyzedand,fromtheconflictionrelationsoftrafficflowwecangetthetrafficflowmodelgraphsandtheircircular chromaticnumbers,namely,theoptimizationphasenumberofcorrespondingtrafficsigna1. Keywords:phaseoptimization;circularcoloring;circularchromaticnumber 在城市交叉路口,用一个顶点来表示一交通流, 若两交通流不相容,则两顶点之间有一连线,交叉路 口的交通流就可用图来表示,ZhuXuding在文献 [1]中提出圆色数定义,可将其应用于交通信号灯 最优相位优化中. Vince2在1988年给出图G的圆色数(G)的 定义,称之为星色数. 定义1两个正整数k,d,1≤d≤k,图G的一个 (k,d)一染色是一个染色c,颜色集合为{0,1,…, k一1},使得 (,Y)∈E(G)jd≤lC()一C(Y)I≤一d 圆色数定义为 (G)=inf{号:存在G的(,d)一染色},LJ 显然,对任意整数k,G的(k,1)染色恰为G的k一染 色,则有.(G)(G). ZhuXuding在文献[1]中对圆色数定义如下: 定义2设C是长度为r的圆周,图G的一个 r一圆染色是一个映射c:∈(G)c上的一段单 位长度的开弧c(),且当(,Y)∈E(G)时,C()n C()=.如果G有r一圆染色,我们就称G是r一 圆可染色的.图G的圆色数记作(G),定义为 (G)=inf{r:G是r一圆可染色的), 显然,对任意r(G),G是r一圆可染色的,且若日 收稿日期:2010—07—05网络出版时间:2011—01—0712:23 基金项目:山东省科技攻关计划(2008G;山东省自然科学基金(ZR2010AL016;Y2008A29) 作者简介:尹丽子(1973一),女,山东威海人,副教授,山东师范大学博士生. 网络出版地址:/kcms/detail/37.1378.N1223.007.html 316济南大学(自然科学版)第25卷 是G的子图,则(G)().他还给出一些平面 图的圆色数[4]. 下面给出文中用到的图的圆染色基本结 果一. 定理1对任意图G,(G)一1lt;(G)≤ (G). 定理2(Kn)=n. 定理3(C+)=2+÷. 定理4对任意整数凡≥6,n=6h+5(h≥1), (=;否则:.其中 为在圈C=(,一,)上连接和Ui+2所得到 的图. 符号说明(G)表示图G的色数(G)表示图 G的圆色数;C表示长为n的圈;表示/7,个顶点 的完全图. 此前作者对交通信号灯的最优设计进行了研 究,得出一些结论