（运筹学与控制论专业论文）城市路口交通信号灯相位优化设计.pdf

原 创 性 声 明 本人郑重声明:所呈交的学位论文，是本人在导师的指导下， 独立进 行研究所取得的成果。除文中己 经注明引用的内容外，本论文不包含任何 其他个人或集体己经发表或撰写过的科研成果。对本文的研究作出重要贡 献的个人和集体，均己 在文中以明确方式标明。本声明的法律责任由本人 承担。 论文作者签名: 典 泊 一 日期 :) . ii车 关于学位论文使用授权的声明 本人完全了 解山东大学有关保留、使用学位论文的规定，同意学校保 留 或向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅 和借阅; 本人授权山东大学可以 将本学位论文的全部或部分内 容编入有关 数据库进行检索，可以采用影印、缩印或其他复制手段保存论文和汇编本 学位论文。 ( 保密论 文 在解密后 应遵守 此规定 ) 论 文 作 者 签 名 : 卫 ha 一 导 师 签 名 : 脾 日 期 : . ， ! 9 山东大学硕士学位论文 城市路口 交通信号灯相位优化设计 尹丽子 山东大学数学与系统科学学院 摘要 若 s 是 一 有 限 集 ， 我 们 用 is i 表 示 s 中 元 素 的 个 数 。 对 于 实 数 二 ， 用 卜 表 示 不 大 于 实 数 二 的 最 大 整 数 ， 用 r x l 表 示 不 小 于 实 数 二 的 最 小 整 数 。 除 非 特 别 指 出 ， 本 文 所 考 虑 的 图 均 是 有限 无向 简 单 图 。 我 们 用v 仁 ) 和e 沁 ) 分 别 表 示 图g 的 顶 点 集 合 和 边 集 合。 g ( v ) 表 示g 的 由 顶 点 子 集v 导 出 的 子 图 ， g ( e ) 表 示g 的由 边 子 集 e 导 出 的 子 图 。 k ， 表 示 。 个 顶 点 的 完 全 图 。 戈， 表 示 具 有 二 分 类( x , 约 的 完 全 偶 图 ， 其 中 !川= m , 冈 = 。 。 x 佑 ) 表 示 g 的 色 数 。 文 中 所 用 术 语 与 符 号 基 本与 文 献 1 ) 中 一致。 定义 1 .2 . 1 设c 是长度为， 的圆周.图g的一个 r 一 圆染色是一个映射 c : x e v ( g ) hc上的一段单位长度的开弧c ( x ) ， 使得当( x , y ) e e ( g ) 时， , ( x ) - c ( y ) = 0 。 如果g 有 ; 一 圆 染 色 ， 我 们 就 称g 是 : 一 圆 可 染 色 的 。 图 g 的 圆 色 数 记 作x , ( g ) ， 定 义 为: x , ( g ) 一 in f r : g 是 ， 一 圆 可 染 色 的 图 g 的 圆 色 数x c 沁 ) 最 初 是v in c e 在1 9 8 8 年 由 提 出 来 的 ， 当 时 称 之 为“ 星 色数” ， 上 面 给出的不是v i n c 。 原 始定 义， 是z h u x u d in g 在文献 2 中 给出 的等 价定义。v i n c e 的定义是这样的: 定 义1 .2 .2对于 两 个 正 整 数k , d ,l : d 5 k ， 图 g 的 一 个仓 , d 卜染 色 是 一 个 染 色c ， 所 用 颜 色 集 合 为( 0 ,1 , . . . , k 一 1 ) ， 使 得 (x , y ) e e (g ) d :5 ic (x ) 一 c (y 5 k 一 d 圆色数定义为: z 山东大学硕士学位论文 x j g ) = in f k : 存 在 、(k , d ) 一 染 色 不 。 t 口1 图 的圆 染色的另一个 等价定 义 是g o d d y n , t a r s i 和z h a n g 由 在 文献【 3 中 提出 来 的 ， 这 个 定 义 将图 的 染 色 与 网 络 的 流 联 系 起 来。 给 定图 g 的 一 个( k , 刃一染 色 ，我们得到余圈拟阵m ( g ) 的一个整数流f，给g任意定向， 令 a ? ) = , (x ) - , ( y ) ，这儿。 = ( , y ) 是从二 。 y的一条边，此流满足 d h o f n a n 的 一 个 引 理 14 ) 表 明 : 余 圈 拟 阵 m ( g ) 有 一 个 满 足 d 引 川 _ k - d 的 整 数 流 f 当 且 仅 当 存 在g 的 一 个 定 向 ， 使 得 对g 的 每 一个圈c，有 k一d 竺兰 d 这里c 是沿c 的正向的边集合，c 一 是沿c 的负向的边集合， 所以得到图的圆色数 的如下定义: 定义1 .2 .3 对g的任意定向d ，设 c(d ) = max借 iciic : c 是d的有向圈 则 x , ( g ) 一 m in 仁 佃 ) 二 d 为 g 的 一 个 定 向 弘 图的染色研究正是从这三个等价定义出 发得到一系列结果。 另 外 ， 范 更 华 在 文 献 7 ) 中 将 图 的 认 ， 刃 一 染 色 等 价 于v 佑 ) 的 一 个 划 分 。 c 的 一个( k , d一划分是v ( g ) 的一个划分( x a , x., x ,t- , ) ，使得对每一 j ,0 :5 j :5 k 一 1 , x j u x , v . v 戈+ 一 ， 山东大学硕士学位论文 是 中 一 个 独立 集， 其中 下 标 对 模k 取 余( 戈可以 为 空 集) ， 易 见，g 的 一 个 ( k , 刃一 划 分 实 际 上 是g 的(k , 刃一 染 色 的 色 类 的 划 分。 范 更 华 的 这 一 等 价 问 题 的 提出 揭 示 了 ( k , d ) 一 染 色 的 实 质， 又 给 圆 染 色的 研 究 提 供了 新 的 工 具 。 考虑这样一个问题:如何在城市交叉路口 处设计一个交通控制系统?我们 需要给每一个交通流分配一段时间， 在这段时间里它有权通过路口，也就是说 它面对的是绿灯。一个交通周期就是一个时间段，在此期间每一交通流都有一 次通过路口的机会。 我们需要设计一 个红一 绿灯模式， 而且这种模式要不断的重 复进行。假设每一绿灯区间 ( 也就是允许某一些交通流通过的时间段)是单位 长度。我们的目 的就是使交通周期的长度达到最小。 图是解决这一问题的理想模型。每一交通流用一个顶点来表示，而且两个 顶点相邻当且仅当它们所对应的交通流是不相容的。 很自 然地想到可以用点染色解决前面提出的问题:把图g的顶点划分成最 少的点独立集，然后把在同一个点独立集中所对应的车流划分到一个相位中， 也 就 是 说 这 种 方 法 划 分 相 位 个 数 其 实 就 是g 的 点 色 数x 仁) ，然 而 这 种 方 法 不 能 提供一个最优解. 我们可以将一个交通周期看作一个圆周c，分配给每一个顶点 ( 即每一交 通流)c上一段单位长度的区间，这就是相应的交通流拥有绿灯的时间段。因 此，图的相邻顶点有不相交的c 上的区间，则我们的目 标就是最小化c 的总长 度，即图g的圆色数。这样我们将交叉路口交通信号灯的最优相位个数就归结 为其交通流模型图的圆色数。 在城市中对路口进行相位优化即用最少的相位分开冲突车流是一项很有意 义的工作，因为如果能找到最优的相位划分方式，就能使得周期变短、 循环加 快， 从而使得再尽可能短的时间内 通过尽可能多的车流。 为此我们分别在第二章，第三章，第四章给出了 三交叉路口，四交叉路口 及五交叉路口 交通信号灯最优的相位个数。 在第二章中分六种情况讨论了 三交叉路口 交通信号灯最优相位个数，得到 定 理a : x ( g ) = 3 ， x j g j= 3 ， x , ( g , ) = 3 ， x j g ) = -2 x (g 3s ) = 2 , x , ( g , ) = 3 。 山东大学硕士学位论文 在第三章中分八种情况讨论了四交叉路口 交通信号灯最优相位个数， 得到 定 理 3 : x j g ) = 4 ,x , (g , ) = 4 ,x , (g , ) = 形 ,x j g ) = 3 ,x j g ,e ) = 3 ， z j g ,6 ) 一 3 ,x , (g) 一 %， x (g as ) 一 3 第四章讨论了五交叉路口交通信号灯最优相位个数，由于情形比较复杂， 我们分为七小节分别介绍。 第一节我们分六种情况讨论了 没有向相对路口 左拐车流的五交叉路口交通 信号灯最优相位个数，得到 定 理4 . 1 : x , ( g 5 , ) 二 2 .5 ， x j g j = 3 ， x , ( g , , ) = 2 .5 ， x , ( g 5 , ) = 3， x , (g 55) = 警 ， x (g j = 誉 。 第二节我们分六种情况讨论了其中一个路口 有相对左拐车流的五交叉路口 交通信号灯最优相位个数，得到 定 理 2 : x , (t 5,) 一 2 .5 x a . ) = 蚤 ， x . (t,) = 号 ， x ,(t5,) = 3 , - ,(t,) = 4 , x . ( t s a ) = 4 e 第三节我们分十二种情况讨论了其中有两个路口 有相对左拐车流的五交叉 路口 交通信号灯最优相位个数，得到 定 理 3 : x ,(r 5,) 一 号 x , ( r j= 3 , x j r 5 ) = 4 , ， x , ( r 5z ) = x , ( r 5 , ) = 3 母 , x , (r ,)一 ， ， x (r 5,)一 ， x (r 55 ) _ 号 ， ， x , ( r 5 e ) 一 3 ， x j r 5e ) = 4 , x j r 5 w ) = 4 , x ( r 5 ,2 ) = 4 , 第四节我们分八种情况讨论了其中 有三个路口有相对左拐车流的五交叉路 口 交通信号灯最优相位个数，得到 定 理4 . 4 . x c ( s j = 3 ， x , ( s , ) = 4 ， x . ( s 5 5 ) = 3 ， x c ( s , , ) = 3 ， x ( s 5, ) = 3 , x , (s 5. ) = 3 x , (s . ) = 4 ， x j s , ) 二 3 ， 第五节我们分四种情况讨论了其中有四个路口有相对左拐车流的五交叉路 口交通信号灯最优相位个数，得到 山东大学硕士学位论文 定 理4 . 5 -. x , 伽， ) 一 4 , x 沁52 ) = 4 , x , (m 5, ) = 4 , x 加54 ) = 4 0 第六节我们分两种情况讨论了五个路口都有相对左拐车流的五交叉路口交 通信号灯最优相位个数，得到 定 理4 . 6 : x , 仇1 ) = 5 ， x 仇 , ) = 5 - 第七节我们分三种情形讨论了具有单行线的五交叉路口交通信号灯最优相 位个数，得到 定 理 4 .7 : z , ( n , ) 一 4 ， x , (n j = 粤 ， x , k 3 ) 一 ; 。 l 关键词:圆染色，圆色数，最优相位 山东大学硕士学位论文 op ti mi zat i on des i gn f or the amount of traf f i c s i gi nal p has e of i nters ecti on i n ci ty yi n l i z ma t h e m a t i c s a n d s y s t e m s c ie n c e c o l l e g e o f s h a n g d o n g u n i v e r s i t y ab s t r a c t i f s is a fin ite s e t,w e d e n o te b y is i th e n u m b e r o f th e e le m e n ts in s . w e u s e 卜 f o r th e m a x im u m in t e r w h i c h i s n o m o r e th a n th e r e a l n u m b e r x a n d u s e f x l f o r t h e m i n i m u m i n t e r w h i c h i s n o l e s s t h a n t h e r e a l n u m b e r x . a l l g r a p h s c o n s i d e re d a r e f in it e a n d s im p le . f o r a g r a p h g， w e d e n o t e b y v ( g ) a n d e ( g ) t h e v e rt e x s e t a n d t h e e d g e s e t o f ， r e s p e c t iv e l y .l e t g ( v ) d e n o t e t h e in d u c e d s u b g r a p h o f g w i th v e rt e x s e t v a n d g ( e ) d e n o t e th e in d u c e d s u b g r a p h o f g w it h e d g e s e t e . w e d e n o t e b y k t h e c o m p l e t e g r a p h o n n v e rt i c e s a n d d e n o t e b y k . .二t h e c o m p le te b ip a r tite g r a p h w ith b ip a r titio n (x , y ) w h e r e ix 一 二 ， iy i = n . t h e c h r o m a t ic n u m b e r o f g i s d e n o t e d b y x ( g ) . n o t a t io n s a n d d e fi n i tio n s n o t g i v e n in t h i s p a p e r c a n b e f o u n d i n i ) d e f i n i t i o n 1 . 2 . 1 l e t c b e a c i r c l e o f ( e u c li d e a n ) l e n g t h/ a n r - c i r c u l a r c o l o r i n g o f a g r a p h g i s a m a p p i n g c w h i c h a s s i g n s t o e a c h v e rt e x x o f g a n o p e n u n i t le n g th a r c c ( x ) o f c , s u c h t h a t fb r e v e ry e d g y (x , y ) o f g , c (x ) n c ( y ) = o . w e s a y a g r a p h g i s r - c i r c u l a r c o l o r a b l e i f t h e r e i s a n r - c i r c u l a r c o l o r a b l e o f g . t h e c ir c la r c h r o m a t ic n u m b e r o f a g r a p h , d e n o t e d b y x , ( g ) ,is d e f in e d a s x , ( g ) = in f i r : g is r - c i r c u la r c o lo r a b le ) t h e c ir c ia r c h r o m a t i c n u m b e r x , ( g ) o f a g r a p h g w a s in tr o d u c e d b y v in c e 山东大学硕士学位论文 i n 1 9 8 8 , a s s t a r c h r o m a t i c n u m b e r . h o w e v e r , th e a b o v e d e f i n it io n i s n o t t h e o r i g i n a l d e f i n i t i o n o f v i n c e ,b u t a n e q u i v a l e n t d e f i n i t i o n g iv e n b y z h u x u d i n g i n 2 . t h e o r i g i n a l d e f in i t i o n o f v i n c e i s a s f o l l o w s : d e fi n i t i o n 1 .2 .2 f o r t w o in t e g e r s 1 : d k ,a ( k , d ) - c o lo r in g o f a g r a p h g is a c o lo r in g。o f t h e v e r ti c e s o f g w i th c o lo r s ( 0 ,1 , 2 , . 。 、 一 1 s u c h t h a t (x , y ) e e ( g ) 二d _ ic ( x ) 一 c (y ) _ k 一 d t h e c i r c u l a r c h r o ma t i c n u mb e r i s d e f i n e d a s x , ( g ) = in f i k 1 d : th e r e is a ( k , d ) - c o lo r in g o f g a n o t h e r e q u i v a l e n t d e fi n i t i o n o f t h e c i r c la r c h r o m a t i c n u m b e r w a s g i v e n b y g o d d y n ,t a r s i a n d z h a n g l l . t h i s d e fi n i ti o n r e l a t e s t h e c i r c l a r c h r o m a ti c n u m b e r to n o w h e r e - z e r o - f lo w s o f a g r a p h . g iv e n a ( k , d ) - c o lo u r in g o f a g r a p h g ， w e o b t a in a n in t e g e r fl o w f o f t h e c o c y c li c m a tr o id m ( g ) ,b y g iv i n g a n a r b itr a ry o r ie n t a t io n o f q a n d th e n b y le t t in g f ( e ) = c ( x ) 一 c ( y ) , w h e r e e = ( x , y ) i s a n e d g e o r i e n t e d fr o m x t o y .t h i s fl o w h a s t h e p r o p e r t y t h a t t h e a b s o l u t e v a l u e o f t h e fl o w r a n g e s b e t w e e n d a n d k 一 d.t h i s p r o c e s s c a n b e r e v e r s e d t o o b t a i n a ( k , d ) - c o lo r in g o f g fr o m a n y i n t e g e r fl o w f o f m * ( g ) w it h a b s o lu te v a lu e r a n g e s b e tw e e n d a n d、 一 d . t h u s a g r a p h g h a s a ( k , d ) - c o lo r in g if a n d o n ly if t h e c o c y c li c m a tr o i d m* ( g ) h a s a n in t e g e r fl o w w it h a b s o lu t e v a lu e r a n g e s b e t w e e n d a n d k 一 d . i t f o llo w s f r o m a le m m a o f h o f f m a n l0 l th a t t h e c o c y c lic m a tro id m * ( g ) a d m it s a n in te g e r fl o w w it h a b s o lu te r a n g e s b e t w e e n d a n d k 一 d if a n d o n l y i f t h e r e i s a n o r i e n t a t i o n o f g s u c h t h a t f o r e v e ry c y c le c o f g， d _ 回 _ * 一 d k - d ic - 1 d w h e r e c i s t h e s e t o f e d g e s o f c o f p o s i t i v e o r i e n t a t i o n ,a n d c - i s t h e s e t o f e d g e s o f c o f n e g a t i v e o r ie n t a t i o n , a l o n g a n a r b i t r a ry t r a v e r s a l o f c . t h e r e f o re w e o b t a i n t h e 8 山东大学硕士学位论文 f o l l o w in g e q u i v a l e n t d e fi n i t i o n o f t h e c i r c u l a r c h r o m a t i c n u m b e r o f a g r a p h d e fi n i t i o n 1 .2 .3 f o r a n a r b i t r a ry o ri e n t a t i o n d o f a g r a p h g ，l e t i s a n o r i e n t a t i o n o f g ) th e n x , (g ) = m in s (d ) : d is a n o r i e n ta tio n o f g t h e s tu d y o f c ir c l a r c o l o ri n g f o r g r a p h s i s b a s e d o n t h e t h r e e e q u i v a l e n t d e f i n i t i o n s . f a n h l c o n s i d e r e d a ( k , d ) - c o lo r in g o f a g r a p h g a s a p a rt it io n o f v ( g ) . a ( k , d ) - p a rt it io n o f g i s a p a rt it i o n ( x , , x : . x , _ , ) o f v ( g ) s u c h th a t f o r e a c h j ,0 5 j _ k 一 1 , x i u x , v . . . v x j , 一 ， i s a n i n d e p e n d e n t s e t i n g， w h e r e t h e a d d i t i o n o f i n d i c e s i s t a k e n m o d k ( h e r e i t i s a l lo w e d th a t x ; = 0 ) . i t is e a s y to s e e th a t a ( k , d ) - p a rt it i o n o f g is s i m p l y t h e c o lo r c la s s e s p a rt it io n o f a ( k , d ) - c o lo ri n g o f . t h is o p in i o n r e v e a l th e n a t u r e o f ( k , d ) - c o lo ri n g a n d p r o v i d e a n e w m e t h o d f o r t h e r e s e a r c h o f c ir c u la r c o lo ri n g . c o n s i d e r t h e p r o b l e m o f d e s i g n i n g a t r a f f i c s y s t e m a t a r o a d i n t e r s e c t i o n . w e n e e d t o a s s i g n t o e a c h t r a ff i c fl o w a n i n t e r v a l o f t i m e d u r i n g w h i c h i t h a s t h e l i g h t o f t h e r o a d , i .e ., i t f a c e s a g r e e n l i g h t . a c o m p le t e t r a ff i c p e r i o d i s a t i m e i n t e r v a l d u ri n g w h i c h e a c h t r a f f i c fl o w g e t s a t u rn o f g r e e n l i g h t . w e n e e d t o d e s i g n a re d - g r e e n l i g h t p a tt e rn f o r a c o m p l e t e t r a ff i c p e ri o d a n d t h e p a tt e rn w i l l b e r e p e a t e d f o r e v e r . s u p p o s e e a c h i n t e r v a l o f g r e e n l i g h t i s o f u n i t l e n g t h . o u r o b j e c t i v e i s t o m i n i m i s e t h e t o t a l l e n g t h o f a c o m p l e t e t r a ffic p e ri o d . g r a p h i s a n i d e a l m o d e l f o r t h i s p ro b l e m . e a c h t r a ff i c fl o w i s r e p r e s e n t e d b y a v e rt e x , a n d t w o v e r t i c e s a r e a d j a c e n t i f t h e c o r re s p o n d i n g t r a f f i c fl o w s a r e n o t c o m p a t i b l e , i . e . t h e ir g re e n l i g h t i n t e r v a l s m u s t n o t o v e r l a p . i t s e e m s n a t u r a l t o s o l v e t h e t r a ff i c c o n t r o l p ro b l e m b y f in g i n g t h e c h r o m a t i c 山东大学硕士学位论文 n u m b e r o f t h e c o r re s p o n d i n g g r a p h g . w e p a rt i t i o n t h e g r a p h i n t o m i n i m u m n u m b e r o f i n d e p e n d e n t s e t s a n d t h e n a s s i g n t o e a c h i n d e p e n d e n t s e t a u n i t l e n g t h i n t e r v a l o f g r e e n l i g h t s u c h t h a t d is t i n c t i n d e p e n d e n t s e t s c o r r e s p o n d t o d i s j o i n t i n t e r v a l s . t h e n t h e t o t a l le n g th o f a c o m p l e t e t r a f f i c p e r io d i s j u s t t h e c h r o m a t i c n u m b e r o f t h e g r a p h g . h o w e v e r , w e s h a l l s e e t h a t t h i s m e t h o d d o e s n o t p r o v i d e th e o p t i m a l s o l u t i o n . we m a y v i e w a c o m p l e t e t r a f f i c p e r io d a s a c i r c l e c , a n d e a c h v e rt e x ( i .e . , e a c h tr a ff i c fl o w ) i s a s s i g n e d a n i n t e r v a l o f c o f u n i t le n g t h , w h i c h i s t h e t i m e i n t e r v a l d u r i n g w h i c h t h e c o r r e s p o n d i n g t r a ff i c fl o w h a s t h e g r e e n l ig h t . t h u s a d j a c e n t v e rt i c e s o f t h e g r a p h a r e a s s i g n e d t o d i s j o i n t i n t e r v a l s o f c , a n d o u r o b j e c t i v e i s t o m i n i m i z e t h e t o t l e l e n g t h o f t h e c i r c l e c , w h i c h i s t h e c h r o m a t i c n u m b e r o f g r a p h g . s o t h e o p t i m iz a t i o n p h a s e a m o u n t s o f i n t e r s e c t i o n s u m u p t h e c i r c u l a r c h r o m a t i c n u m b e r o f m o d e l g r a p h s o f tr a f f i c fl o w . i n a m o d e r n c i t y t r a f fi c c o n g e s t i o n h a s b e c o m e a p r o b l e m u r g e n t t o b e s o l v e d . n o o n e w i l l b e h a p p y i f h e h a s t o b e w a i t i n g f o r a lo n g t im e w h e n h e c o m e s t o a n i n t e r s e c t io n . we h o p e t o r e d u c e t h e w a i t i n g t i m e b y i m p r o v i n g t h e c i r c l e e f f i c i e n c y o f t r a f f i c l i g h t . t h e r e f o r e , w e p r o v i d e in c h a p t e r 2 , c h a p t e r 3 , a n d c h a p t e r 4 t h e o p t i m i z a t io n p h a s e a m o u n t s o f t h e t r a ff i c li g h t s o f t h e t - r o a d s , c r o s s ro a d s a n d fi v e - d i r e c t i o n c r o s s r o a d s r e s p e c t i v e l y . i n c h a p t e r 2 , w e d i s c u s s t h e o p t i m i z a t i o n p h a s e a m o u n t s o f t h e tr a f f i c l i g h t s o f t h e t ro a d s u n d e r s i x k i n d s o f c i r c u m s t a n c e s , a n d w e g e t t h e o r e m 2 : x , 低i ) 一 3 , - , (g) 一 3 , x , ( g 33 ) 一 3 , x , (g , ) 二 2 , x , ( g a s ) = 2 , x , ( g ,e ) = 3 . i n c h a p t e r 3 , w e d i s c u s s t h e o p t i m i z a t i o n p h as e a m o u n t s o f t h e t r a f f i c l i g h t s o f t h e c r o s s ro a d s u n d e r e i g h t k i n d s o f c ir c u m s t a n c e s , a n d w e g e t t h e o r e m 3 : x (g ) 一 4 , x , (g ez ) 一 4 , x (g 4, ) 一 % , x , (g) 一 3 ,x , (g 4s ) = 3 ， x (g . ) = 3 , x , (g , ) 一 %， 、 (g ,$ ) = 3 1 0 山东大学硕士学位论文 i n c h a p t e r 4 , w e d i s c u s s t h e fi v e - d i r e c t i o n c r o s s r o a d s t h e o p t im i z a t i o n p h a s e d u e t o t h e c o m p l i c a t e d a m o u n t s o f t h e t r a ff i c li g h t s o f s i t u a t i o n , t h i s c h a p t e r i s d i v i d e d i n t o s e v e n s e c t i o n s : i n s e c t i o n 1 , w e d i s c u s s t h e o p t i m i z a t i o n p h a s e a m o u n t s o f t h e t r a ff i c li g h t s o f t h e fi v e - d i re c t i o n c r o s s r o a d s w h e r e t h e r e a r e n o l e ft - t u r n v e h i c l e s t o t h e o p p o s i t e r o a d s u n d e r s i xk i n d s o f c i r c u ms t a n c e s , a n d w e g e t 4 . 1 : x , 帆. ) = 2 .5 ， x , ( g s, ) = 3 ， x , 帆, ) = 2 .5 ， x , 帆; ) = 3 x , 1g 55) 一 _103 ， x , g 56)一 _103 知s e c t i o n 2 , w e d i s c u s s t h e o p t i m i z a t i o n p h a s e a m o u n t s o f t h e f iv e - d i r e c t i o n c r o s s r o a d s w h e r e t h e re a r e l e ft - t u rn v e h i c l e s t o t h e o p p o s i t e t w o d ir e c t i o n s o n o n e o f t h e fi v e c r o s s i n g s u n d e r s i x k i n d s o f c i r c u m s t a n c e s , a n d w e g e t ， _ _ _a ， _i -、 ，t - 、 7 f - 、 5， _ 、 _， _、 1 v g v i g p ， 一、 c 11 51 ) 一 ， ， x 5 = 2 ， x = 2 z a 5 11 = 3 , x , 17 55 1 = 4 , x . 仇 s ) = 4 . i n s e c t i o n 3 , w e d i s c u s s t h e o p t i m i z a t i o n p h as e a m o u n t s o f t h e t r a f f i c l i g h t s o f t h e fi v e - d i r e c t i o n c r o s s r o a d s t h e r e a r e l e ft - t u rn v e h i c l e s t o t h e o p p o s i t e t w o d i r e c t i o n s o n t w o o f t h e c r o s s i n g s u n d e r t w e l v e k i n d s o f c i r c u m s t a n c e s , a n d w e g e t t h e o r e m 4 .3 : x j r 51) = 5 ， x z (r 52 ) 一 7 ， x r 53 ) 一 3 ， x , (r 1 8 - _ _ _ _ _山东 大 学 硕士学位论文 第一章引 言 本章第一节介绍常用的一些基本图论术语， 第二节介绍圆染色理论的历史和 发展状况。 1 . 1 基 本概念 若 s 是 一 有 限 集 ， 我 们 用 同 表 示 s 中 元 素 的 个 数 。 对 于 实 数 x ， 用 卜 表 示 不 大 于 实 数 x 的 最 大 整 数 ， 用 爪 了 表 示 不 小 于 实 数 二 的 最 小 整 数 。 给 定 正 整 数 i , j , 我 们 用g c d ( i , j 表 示 与1 的 最 大 公 约 数。 一 个 图 g 是 一 个 有 序 数 组 ( v ( g ), e ( g ) , y r ( g ) ) ， 其 中 v ( g ) 中 的 元 素 称 为 顶 点 ; 州 台 ) 是 边 的 集 合 ， e 佑 ) 中 的 元 素 称 为 边 ; v/ 沁 ) 是 关 联 函 数 ， 其 定 义 域 是 e 佑 ) ， 对。 。 e ( g ) ， 存 在 唯 一 的 一 对 顶 点 u , v e 以 g ) ( 。 ， ， 未 必 相 异) 使 得v . ( e ) = u , a 当u , v 无序时，g称为无向图，当。 ， ， 有序时，g称为有向图。我们通常记 g = ( v , 劝。 图 g 的 阶 是 v 佑 ) 的 元 素 个 数 以 g 戈 ， 图 g 的 边 数 是 e ( g