菏泽学院本科生毕业设计（论文）
vil可能相同外）各异，所有边也各异，则称?为初级通路或路径，此时又若vi0=vil，则称?为初级回路或圈，将长度为奇数的圈称为奇圈，长度为偶数的圈称为偶圈．
定义2.4.2[19] 对无环图G的每个顶点涂上一种颜色，使相邻的顶点涂不同的颜色，称为对图G的一种着色．若能用k种颜色给G的顶点着色，就称对G进行了k着色，也称G是k—可着色的．若G是k—可着色的，但不是?k?1?—可着色的，就称G是k色图，并称这样的k为G的色数，记作??G??k．
定义2.4.3[20] 在n?1（n?4）边形Cn?1内放置一个顶点，使这个顶点与Cn?1上的所有顶点均相邻，所得n阶简单图称为n阶轮图．n为奇数的轮图称为奇阶轮图，n为偶数的轮图称为偶阶轮图．
定理2.4.1（四色定理）[21] 每个平面的色数至多是4．
定理2.4.2[19] 奇圈和奇阶轮图的色数均为3，而偶阶轮图的色数为4． 2．4．2 应用举例
例1[22] 在期末考试周期间，一所学院的8名选修数学的学生得到许可去参加大学生科研讨论会．假设他们回来之后需要在星期一对所错过的考试进行补考，星期一安排这些考试的可能时间段为：
⑴8:00——10:00 ⑵10:15——12:15 ⑶12:30——2:30 ⑷2:45——4:45 ⑸5:00——7:00 ⑹7:15——9:15
应用图论的相关知识，确定这8名学生完成考试的最早时间．要求：如果有某个学生必须要参加某两门课的考试，那么，这两门课程就不能安排在同一时间段内．这8名学生以及他们选修的课程：高等微积分（AC）、微分方程（DE）、几何学（G）、图论（GT）、线性规划（LP）、近世代数（MA）、统计学（S）、拓扑学（T），列表如下： Alicia：AC，DE，LP Brian ：AC，G，LP
Carla ：G，LP，MA Diane ：GT，LP，MA Edward ：DE，GT，LP Faith ：DE，GT，T Grance ：DE，S，T Henry：AC，DE，S
解 首先构造图2.4.1，其顶点为这8门课程，如果有某个学生同时考两门课程则在这两个顶点间连一条边．1、2、3、4表示四种不同的颜色，如S1表示S用第一种颜色着色．
11
张佳丽：图论的发展及其在生活中的应用
记最小的时间段数为??G?，由于G中含有奇圈AC，S，T，GT，LP，AC，由定理2知，需要3种颜色为该图上的顶点着色．由于DE与该图上的所有顶点都邻接，所以需要用第四种颜色来为DE染色．因此??G?≥4；又由定理1知??G?≤4，因而??G?＝4．
AC 2S 1T 2DE 3MA 3GT 1LP 4图2.4.1
G 1
故在四个时间段内可安排这8门课程的考试，安排方法为：
时间段1：统计学、几何学、图论 时间段2：高等微积分、拓扑学 时间段3：微分方程、近世代数 时间段4：线性规划
故可在安排时间段(1) 8:00—10:00 (2) 10:15—12:15
(3) 12:30—2：30 (4) 2:45—4:45
故完成考试的最短时间为4:45．
例2[22] 有8种化学药品需要空运飞越整个国家.运费根据运送的容器数量来确定.运送一个容器需要125元.某些药品之间可以发生化学反应,所以把它们放在同一个容器中是很危险的.这些化学药品被标记成A,B,C,D,E,F, G,H.下面列出的是与某个给定药品能够发生反应的其他药品名称:
A:B,E,F B: A,C,E,G
C: B,D,G D: C,F,G,H E: A,B,F,G,H F: A,D,E,H
G: B,C,D,E,H H: D,E,F,G
这些化学药品应该如何放置于那些容器中使得运送这些化学药品所需的费用最少?最少是多少?
解 首先构造图2.4.2,其顶点为这8种化学药品.如果某两种药品能发生化学反应
12
菏泽学院本科生毕业设计（论文）
就在这两个顶点间连一条边.1，2，3，4表示四种不同的颜色，如A1表示A用第一种颜色着色．
记最小的容器数为??H?，由于G中含有奇圈A,B,G,H，F,A由定理2知，需要3种颜色为该图上的顶点着色．由于E与该图上的所有顶点都邻接，所以需要用第四种颜色来为E染色．因此??H?≥4；又由定理1知??H?≤4，因而??H?＝4．
D 1C 2H 4F 2G 3B 4E 1A 3图2.4.2
故将这8种化学药品放置在四个容器内,安排方法为： 第一个容器: D,E 第二个容器: C,F 第三个容器: A,G 第四个容器: B,H
最少费用为4×125＝500.
2．5 用边染色解决安排问题 2.5.1 基本理论
定义2.5.1[23] 非空图G的一个边染色是指给G的边分配颜色，每条边分配一种颜色，使得邻接的边分配不同的颜色．对G的边染色所需的最少颜色数称为是边色数，记为?1?G?．应用k种颜色的边染色称为是k边染色．
定义2.5.2[24] 设G?V,E为一无向图，?v?V，称v作为边的端点次数之和为
v的度数，简记为度，记作dG?v?，在不发生混淆时，简记为d?v?．
定理2.5.1[23] 对于任意非空图G，
?1?G?＝??G?或者?1?G??1???G?．
定理2.5.2[23] 设G是一个阶为n，边数为m的图．若
13
张佳丽：图论的发展及其在生活中的应用
(n?1)??G?m?
2则?1?G??1???G?． 2.5.2 应用举例
例1[23] Alvin (A)曾邀请3对夫妇到他的避暑别墅住一个星期,他们是Bob (B)和Carrie (C)Hanson,David (D)和Edith (E)Irwin,Frank (F)和Gena (G)Jackson．由于这6位客人都喜欢网球运动,所以他决定进行一些网球比赛．6位客人中的每一位都要与其配偶之外的每位客人比赛．另外, Alvin将分别与David,Edith ,
Frank , Gena进行一场比赛．若没有人在同一天进行两场比赛,则要在最少天数完成
比赛,该如何安排?
解 首先构造图2.5.1,其顶点为住在Alvin的避暑别墅的人,因此
H中的两个顶点是邻接的,如果这两个顶点(人)需要进行V?H???,A,BC,D,E,?F,, G一场比赛．为了解答这个问题,我们需要确定H的边色数．
B14462A图2.5.1
25DG31C324E635F1
易见, ??H??5．根据定理2．5．1, ?1?H??5或者?1?H??6．此外, H的阶为
n?7,边数为m?16．由于
m?16?15?(7?1)?5(n?1)??H??
22由定理2．5．2,可知?1?H??6．图H列出了H的一个6边染色,从而也给出了一个具有最少天数(6)的时间安排表．
14
菏泽学院本科生毕业设计（论文）
第一天: Bob—Gena Carrie—Edith David—Frank 第二天: Alvin—Frank Bob—David Edith—Gena 第三天: Alvin—Edith Bob—Frank Carrie—Gena 第四天: Alvin—Gena Edith—Bob Carrie—David 第五天: David—Gena Edith—Frank
第六天: Alvin—David Carrie—Frank
例2[25] 来自亚特兰大、波士顿、芝加哥、丹佛、路易维尔、迈阿密以及纳什维尔的7支垒球队受邀请参加比赛，其中每只队都被安排与一些其他队比赛，如下：
亚特兰大（A）：波士顿，芝加哥，迈阿密，纳什维尔 波士顿（B）：亚特兰大，芝加哥，纳什维尔 芝加哥（C）：亚特兰大，波士顿，丹佛，路易维尔 丹佛(D)：芝加哥，路易维尔，迈阿密，纳什维尔 路易维尔(E)：芝加哥，丹佛，迈阿密
迈阿密(F)：亚特兰大，丹佛，路易维尔，纳什维尔 纳什维尔(G)：亚特兰大，波士顿，丹佛，迈阿密
每支队在同一天最多只能进行一场比赛。建立一个具有最少天数的比赛时间表.
解 首先构造图2.5.2,其顶点为7支球队,因此V?G???A,B,C,D,E,F,G?, G中的两个顶点是邻接的,如果这两个顶点需要进行一场比赛．为了解答这个问题,我们需要确定G的边色数．
3
图2.5.2
易见, ??G??4．根据定理2．5．1, ?1?G??4或者?1?G??5．此外, H的阶为
n?7,边数为m?13．由于
15