城市交叉口交通流模型图的圆色数

城市交叉口交通流模型图的圆色数

在城市地区优化交叉口交通红灯的相位，这是非常重要的。如果我们找到最合适的相位划分方法，我们就可以缩短循环，加快循环，并在尽可能短的时间内通过尽量多的速度。为了在城市的交叉口设计一个交通控制系统，我们需要分配每个交通流一个周期。一个交通周期是一个周期。在此期间，每个交通流都有通过交叉口的机会。在这种情况下，需要设计红色信号转换模式。假设每个绿灯间隔（允许一家交通行业）为单位长度，并最小化交通周期。这是解决这一问题的理想模型。每个交通流以一个点表示，并且两个点相邻。即使它的对应交通路径是错误的。在文献中，提出了等式圆形的等效定义。交通周期可以视为c的周期方向，每个点可以在c上分配一段单位长度的间隔，这是相应交通流中蓝色信号的区域。因此，如果相邻点有不相交的c段，我们的目标是将c段的长度设置为无限的范围，即图的圆色数。这是robot中视野中色彩优化的一个好应用背景。在现实生活中常见的五交叉路口通常是以某一个或几个路口为单行线的形式出现的.本文比较系统地给出了具有单行线的五交叉路口的交通流示意图的圆色数,由车流的冲突关系给出了交通流模型图,并求出它们的圆色数,即对应交通信号灯的最优相位个数.1dc-cg-k-d-染色符号说明:χ(G)表示图G的色数;χc(G)表示图G的圆色数;Kn表示具有n个顶点的完全图.图G的圆色数χc(G)最初由Vince在1988年提出,当时称之为“星色数”.Vince给出的定义是定义1对于两个正整数k,d,1≤d≤k,图G的一个(k,d)-染色是一个染色c,所用颜色集合为{0,1,…,k-1},使得(x,y)∈E(G)⇒d≤|c(x)-c(y)|≤k-d.圆色数定义为χc(G)=inf{kd:存在G的(k,d)-染色}.χc(G)=inf{kd:存在G的(k,d)−染色}.显然,对任意正整数k,G的(k,1)-染色恰为G的k-染色,则有xc(G)≤χ(G).文献给出的圆染色的等价定义为定义2设C是长度为r的圆周,图G的一个r-圆染色是一个映射c:x∈V(G)→C上的一段单位长度的开弧c(x),且当(x,y)∈E(G)时,c(x)∩c(y)=ϕ.如果G有r-圆染色,我们就称G是r-圆可染色的.图G的圆色数记作χc(G),定义为χc(G)=inf{r:G是r-圆可染色的}.显然,对任意r≥χc(G),G是r-圆可染色的,且若H是G的子图,则χc(G)≥χc(H).2有旋转轴c3g2引理2对任意图G,χ(G)-1<χc(G)≤χ(G).对以下各种情形都不考虑行人.情形1见图1中a,有一个路口为单行线,其余路口的车流向相邻路口右拐和左拐以及向相对路口右拐和左拐,由车流的冲突关系导出图1中b模型图G51;情形2见图2中a,有两个相邻路口为单行线,其余路口的车流向相邻路口右拐和左拐以及向相对路口右拐和左拐,由车流的冲突关系导出图2中b模型图G52;情形3见图3中a,有两个不相邻路口为单行线,其余路口的车流向相邻路口右拐和左拐以及向相对路口右拐和左拐,由车流的冲突关系导出图3中b模型图G53.定理χc(G51)=4,χc(G52)=72,χc(G53)=4.χc(G51)=4,χc(G52)=72,χc(G53)=4.证明在图G51中,由顶点3,8,13,18导出的子图为K4,由引理1可知χc(G51)≥χc(K4)=4.可以找到G51的一个独立集划分:{2,3,4},{7,8,9},{12,13,14},{17,18,19},则由引理2得χc(G51)≤χ(G51)≤4,所以χc(G51)=4.对于图G52,由顶点3,6,15导出的子图为K3,根据引理1可知χc(G52)≥χc(K3)=3.图G52是图G51的子图,则有χc(G52)≤χc(G51)=4,所以3≤χc(G52)≤4.由圆染色的定义可知,它可能的圆色数为3‚27,103,43‚27,103,4.下面证明χc(G52)>103.χc(G52)>103.假设χc(G52)=103χc(G52)=103.则图G52是(10,3)-可染色的.令c:V→{0,1,2,3,4,5,6,7,8,9}是G52图的一个(10,3)-染色.不失一般性,令c(v15)=0,则c(v3),c(v6),c(v7),c(v11),c(v12)∈{3,4,5,6,7}.因为v3又与v6,v7相邻,v11又与v7相邻,则c(v3),c(v6),c(v7),c(v11)均不等于5,否则无法进行正常的(10,3)-染色.所以c(v3),c(v6),c(v7),c(v11)∈{3,4,6,7}.若c(v3)∈{3,4},则有c(v6),c(v7)∈{6,7},c(v11)∈{3,4}.因为v10与v3,v6相邻,则c(v10)∈{1,0,9};因为v2与v6,v11相邻,则c(v2)∈{1,0,9};因为v16与v2,v7相邻,则c(v16)∈{2,3,4};因为v14与v10,v11相邻,则c(v14)∈{6,7,8};因为v12与v15,v16相邻,则c(v12)∈{5,6,7};因v12与v14相邻,则c(v12)=5,c(v14)=8;v12与v16相邻,则c(v16)=2,v2与v16相邻,则c(v2)=9,v10与v14相邻,则c(v10)=1,v3与v10相邻,则c(v3)=4,v6与v3相邻,则c(v6)=7.又因v2与v6相邻,有|c(v2)-c(v6)|≥3与c(v2)=9,c(v6)=7矛盾.所以无法进行正常的(10,3)-染色.若c(v3)∈{6,7},则有c(v6),c(v7)∈{3,4},c(v11)∈{6,7}.因为v10与v3,v6相邻,则c(v10)∈{1,0,9};因为v2与v6,v11相邻,则c(v2)∈{1,0,9};因为v16与v2,v7相邻,则c(v16)∈{6,7,8};因为v14与v10,v11相邻,则c(v14)∈{2,3,4};因为v12与v15,v16相邻,则c(v12)∈{3,4,5};因v12与v14相邻,则c(v12)=5,c(v14)=2,v16与v12相邻,则c(v16)=8,v2与v16相邻,则c(v2)=1,v10与v14相邻,则c(v10)=9,v3与v10相邻,则c(v3)=6,v6与v3相邻,则c(v6)=3.又因v2与v6相邻有|c(v2)-c(v6)|≥3与c(v2)=1,c(v6)=3矛盾.所以无法进行正常的(10,3)-染色.由以上的分析可知χc(G52)>103χc(G52)>103,即χc(G52)≥72;可以找到图G52的一个(7,2)-染色(如图4)χc(G52)≤72,所以χc(G52)=72.在图G53中,由顶点3,7,11,15导出的子图为K4,由引理1可知χc(G53)≥χc(K4)=4.可以找到G53的一个独立集划分:{2,3},{6,7,8},{10,11,12},{15,16},则由引理2得χc(G53)≤χ(G53)≤4,所以χc(G5