i 1 i n
图和树
d (v ) 2m
i 1 i n
vve
d (v) d (v) 2m
vv0
vv0
d (v) 2m d (v)
vve
图和树
例题1：晚会上朋友们握手言欢，则握过奇次手的人数 是偶数. 解：以晚会每个参加者为顶点，仅当二人握手时，在 相应的二顶间连一条边，如此构作一图G，于是每个 人V的握手次数即G中此顶的次数d(v),由推论知握了奇 数次手的人数，即G的奇次顶的顶数是偶数。
统筹法
洗烧水壶
0 0 2
烧水
15
洗茶壶
4 4
请客喝茶
s
0 0
泡茶
t
洗茶碗
2
拿茶叶
统筹法
统筹法
2.关键工序、关键路和工序的最早可开工时间
2
0 0 0 4 0 4 0 2 0+2=2 15
s
0
0 0
t
15+2=17
0
统筹法
关键路算法（critical path method (CPM)）
(1)标志s为 ( s ) 0, 其他顶未标志. (2)找统筹图中的一个顶v, v未标志，而以v为头的有向边之尾 都已标志，把v标成 (v), (v)是{l (u1v) (u1 ), l (u2v) (u2 ),..., l (uk0 v) (uk0 )}中的最大值，其中u1v, u2v,..., uk0 v是以v为头的一 切有向边.如果 (v) l (uk1 v) (uk1 ), 则把有向边uk1 v染成红色 ，其中1 k1 k0 . (3)v t时，执行完(2)时止，从s到t的有向红色路即为一条关 键路， (t )为竣工需要的最短时间若 . v t , 则转而再执行（2）
统筹法
1.统筹问题实例与统筹图
实例1:午夜急诊问题。
20 35
赵医生家
医院
钱医生家
关键路径
筹法
实例2：请客喝茶问题
方式1 先去洗烧水壶和茶壶茶碗，拿来茶叶，一切就绪后， 再拿烧水壶灌水去烧，等烧开后再泡茶。
方式2 洗净烧水壶，灌上凉水去烧水，坐等水烧开后才急匆 匆找茶叶和洗茶壶茶碗。 方式3 洗净烧水壶，灌上凉水，放在煤气灶上烧，在等待水 开的时间内去找茶叶和清洗茶壶茶碗。
（2）把图G的每条边都染上颜色，且禁止邻边（有公共 端点的边）同色，则称其为对G的边进行正常着色，边正 ' 常着色时使用颜色的最少数目称为G的边色数，记成 (G )
染色
例： (7顶轮)=？
解：如右图，用三种颜色可对 7顶轮顶进行正常着色， 所以， (7顶轮) 3. 又7顶轮中有三角形，所以 (7顶轮) 3. (7顶轮)=3. 于是：
统筹法与图论初步
主要内容
1 2 3
统筹法 图和树
其他图论问题
一、统筹法
在错综复杂的工艺过程中，任务 多了，几百几千甚至有好几万个； 关系多了，千头万绪。往往由于一 两个零件没有完成，耽误了一架复 杂机器的出厂时间；也往往抓得不 是关键，联夜三班，急急忙忙，完 成这一环节之后，还得等待旁的部 件才能装配。 ——华罗庚《统筹法平话》
统筹法
统筹法
例：有11个工件在一台机床上加工，某些工件的加工必 须安排在另一些工件加工完成之后才能进行，各工件加 工时间和紧前工件如下表所列:
工件
加工时间 （分）
紧前工件
3
5
7
9
2
4
6
8
1
2
3
试确定一个加工次序，使各工件的完成时间（含加工 等待时间）之和最小.
统筹法
s
t
图和树
图论仗恃她的美丽、灵巧、深刻和妙用， 在现代数学中异军突起，备受关爱。 她能显示关系，她能统筹网络， 千言万语不及一张图。 树是最得人心的植物， 树是最受欢迎的图类； 我们无力生成图的每一棵树， 我们能够生成一棵最好的树。
统筹法
3.工序的最迟必须开工时间和时差
2
洗烧水壶
0 0
烧水
15
洗茶壶
4 4
请客喝茶
s
0
0
泡茶
t
洗茶碗
2
拿茶叶
统筹法
各工序的最迟必须开工时间算法： (1)在以s为起点以t为止点的统筹图上用求关键路的算法 求得 (t ) (2)在以s为起点以t为止点的统筹图上任取一顶v,由t开始 逆箭头寻求出从t到v的最长路p (v, t ). (3)求p (v, t )上各边权之和 (v). (4) (t ) [ (v) l (e)]为工序e最迟必须开工的时间，其中 e以v为头.
图和树
1.哥尼斯堡七桥问题
过每桥恰一次，再回到出发点， 是否可能？
D
B A
C
图和树
2.什么是图？
图和树
V { A, B, C , D} E { AB, AC , AD, BC , BC , BD, BD}
___ ___
D
B A
C
图和树
D
B A
C
图和树
图和树
图和树
图和树
d (v ) 2m
图和树
图和树
其他图论问题
1.匹配 2.欧拉图与一笔画 3.中国邮路问题 4.周游世界玩具与和哈密顿图 5.竞赛图 6.染色
染色
（1）把图G的每个顶都染上颜色，且禁止邻顶同色，则称 其为对G的顶集进行正常着色，顶正常着色时使用颜色的 最少数目称为G的顶色数，记成 G , (G) k时，称G为k色图.