图论与网络模型 (五 )
一、关键路径分析技术与计划评审技术一项工程包括若干工序，完成每道工序需要一定的时间，工序之间存在先后顺序关系，那么如果安排各工序的开工时间和顺序，才能使工程尽可能早完成？
关键路径分析就是借助图的技术来求解此问题的一个方法。它告诉我们哪些工序是影响工程的关键，它们的提前或推后完工，
都必然影响工程的完工。
1.关键路径分析例题：设某项工程的各个工序与所需时间以及它们之间的相互关系如下表所示：
工 序 工序代号 所需时间（天） 紧后工序产品设计 a 60 b,c,d,e
外购配套件 b 45 l
下料、锻件 c 10 f
工装制造 1 d 20 g,h
木模 e 40 h
机械加工 1 f 18 l
工装制造 2 g 30 k
机械加工 2 h 15 l
机械加工 3 k 25 l
装配调试 l 35 /
现在我们要编制该工程的网络计划，确定各工序的开工时间等，特别是确定关键工序。
首先根据上面表所给出的内容，绘制网络图。
所谓 网络图 是由点（结点）、弧及权所构成的有向图。即有向赋权图。
在这里，一个 点表示一个事项 （或事件），
它是一个或若干个工序的开始或结束，是相邻工序在时间上的分界点。 点用圆圈和其里面的数字表示，数字表示点的编号，如
…
弧表示一个工序,用箭线,?”表示。 权表示完成某工序所需的时间,用 T(i,j)表示 。
上述问题对应的网络图：
a
60
b
45c
10
d
20
e
40
f
18
g
30
h
15
k
25
l
35
i j
箭尾事项 箭头事项
i紧前工序紧后工序有关网络图的构造请进一步参考有关书籍事项的时间：
（ 1）事项最早时间 TE(j)：
若事项为某些工序的箭尾事项，事项最早时间为各工序的最早可能的开始时间；
若事项为某些工序的箭头事项，事项最早时间为各工序的最早可能的结束时间
j
事项工序 工序
j
事项工序 i
TE(j)的计算,
TE(1)=0
TE(j)=max{ TE(i) + T(i,j) }
j=2,3,…,n
计算结果写入事项左下方的?内。如下：
a
60
b
45c
10
d
20
e
40
f
18
g
30
h
15
k
25
l
350 60 80
70
100
110 135 170
事项的时间：
（ 2）事项最迟时间 TL(i)：
箭头事项各工序的最迟必须结束的时间；
或 箭尾事项各工序的最迟必须开始的时间。
i
事项工序 工序
i
事项工序事项最迟时间的计算从终点开始：
TL(n)=TE(n)
TL(i)=min{ TL(j) - T(i,j) }
i=n-1,n-2,…,1
计算结果写入事项右下方的?内。
a
60
b
45c
10
d
20
e
40
f
18
g
30
h
15
k
25
l
350 60 80
70
100
110 135 170 170135110
120
117
80600
工序的时间,
（ 1）工序的最早开始时间 TES(i,j)
任何工序都必须在其紧前工序结束后才能开始。紧前工序最早结束时间即为工序最早可能开始时间，简称为工序最早开始时间。
最早开始时间等于该工序箭尾事项的最早时间，即
TES(i,j)＝ TE(i),
i j
TES (i,j)
工序的时间,
（ 2）工序的最早结束时间 TEF(i,j)
工序最早结束时间是工序最早可能结束的时间的简称。
最早结束时间等于该工序最早开始时间加上该工序的作业时间，即
TEF(i,j)＝ TES(i,j) +T(i,j).
i jT(i,j)
TES(i,j) TEF(i,j)
工序的时间,
（ 3）工序的最迟结束时间 TLF(i,j)
在不影响工程最早结束时间的条件下，
工序最迟必须结束的时间，简称为工序最迟结束时间。
最迟结束时间等于该工序箭头事项的最迟时间，即
TLF(i,j)＝ TL(j),
i j
TLF(i,j)
工序的时间,
（ 4）工序的最迟开始时间 TLS(i,j)
工序最迟开始时间是在不影响工程最早结束时间条件下，工序最迟必须开始的时间。
最迟开始时间等于该工序最迟结束时间减去该工序的作业时间，即
TLS(i,j)＝ TLF(i,j) -T(i,j).
i jT(i,j)
TLS(i,j) TLF(i,j)
工序的时间,
（ 5）工序的总时差 TF(i,j)
在不影响工程最早结束时间条件下，工序最早开始（或结束）时间可以推迟的时间，称为该工序的总时差。
TF(i,j) = TLS(i,j) -TES(i,j) = TLF(i,j) -TEF(i,j)
= TL(j) -TE(i)-T(i,j).
总时差为零的工序，开始和结束的时间没有一点机动的余地。
由这些弧线组成的路线就是网络中的关键路线，
这些工序就是关键工序,我们用红色的?表示 。
a
60
b
45
c
10
d
20
e
40
f
18
g
30
h
15
k
25
l
350 60 80
70
100
110 135 170 170135110
120
117
80600
箭尾事件的最早开始时间 (方框内 )为工序的最早开始时间,箭头事件的最迟结束时间 (三角内 )为工序的最迟结束时间,工序 c,f
线的总时差为 47,工序 e,h线的总时差为 20,工序 b的总时差为 30.
当然,象我们书上那样画图处理也可以,
2、计划评审技术由于完成每道工序需要的时间一般难以准确估计，因此不同的人员有不同的估计,这就使得关键路径不能准确确定,这正是关键路径分析技术的缺点,
计划评审技术把各项工序的延续时间视为彼此独立的随机变量,随机变量的任一组取值表示一种可能的具体情况,而且它采用如下简便方法,对每一项工序,要求给出三个时间,分别为最可能的延续时间 (m),最乐观 (最短 )时间 (n),最悲观 (最长 )时间 (b).并计算出每一项工序的延续时间的期望值 E和方差 σ2.其公式为
E=(4m+a+b)/6,σ2 =(b-a)2/36.
工 序 工序代号 所需时间 m,a,b（天） 紧后工序产品设计 a 60,44,100 b,c,d,e
外购配套件 b 45,35,55 l
下料、锻件 c 10,9,11 f
工装制造 1 d 20,16,24 g,h
木模 e 40,35,45 h
机械加工 1 f 18,15,21 l
工装制造 2 g 30,27,33 k
机械加工 2 h 15,13,17 l
机械加工 3 k 25,20,30 l
装配调试 l 35,30,46 /
工序 a b c d e f g h k l
E 64 45 10 20 40 18 30 15 25 36
σ2 87.
111
11.
11
1.1
11
1.7
78
2.7
78
1 1 0.44
4
2.7
78
7.11
1
我们把计算出的结果列表如下,
由于工序 b到 k的期望值 E与原来的值一样,因此我们以 E来进行关键路径分析时,工序 adgkl形成的路径依然是关键路径,不过由于工序 a和 l的数值发生了变化,表中的 TE(i)也发生了变化,因此新的关键路径分析结果如下表,
a
64
b
45
c
10
d
20
e
40
f
18
g
30
h
15
k
25
l
360 64 84
74
104
114 139 175 175139114
124
121
84640
由于每个工序的延续时间是独立的随机变量,因此各个结点,即事件也是各随机变量,
记为 ζi,相应地我们取新的随机变量 Zi=(ζi -
TE(i) )/σi,这里 σi2是同一路径上直到第个事件的方差的和,故 Zi服从标准正态分布,
iZ
dxesP xii
~
2 2/
2
1)(
这里 si是第 i各事件的实际计划开始时间,
我们来对此进行评审,简单说,若上面的这个概率太大,表明计划时间不恰当,应该推迟,下表是我们的评审结果,
i
Ei
i
iTz
)(~
事件 TE(i) σi2 si ~Zi P(ζi >si)
1 0 0 0 / 0.000
2 64 87.111 60 -0.429 0.666
3 74 88.222 70 -0.426 0.665
4 84 88.889 80 -0.424 0.664
5 104 89.889 100 -0.422 0.664
6 114 89.889 110 -0.422 0.664
7 139 92.667 135 -0.416 0.661
8 174 99.778 170 -0.400 0.655
总的来说,第二个事件安排得太早,因此应该调整,比如调整为 64,则后面的每一个事件也相应地推后 4天,这样,每个概率都是 0.5,大致可以付诸实施,
3、冈特流程图当一项工程已经被关键路径分析或计划评审之后,所得到的部分结果可由冈特流程图形象地加以表示,
再根据此图,
进一步作出人力,物力随时间的安排图,直观明了,
易于安排和调配使用,
a
b c
d
h
l
e
g
f
k
t
工序二、监狱看守问题与图的覆盖一座监狱的几间牢房有道路相连,设如图所示,监狱看守要设在通过道路年直接监视所有牢房的地方,如果看守不得走动,那么他们应呆在某些牢房 (即路口 )所在地,问至少需要几名看守才能完成监视任务?
v1
v2
v4
v3 v5
e1 e2
e3e
4
e5
e6
e7
若图 G的每条边都至少有一个端点在顶点集 V
的一个子集 K中,则称 K为 G的 覆盖,
极小覆盖,一覆盖,若减少其中任一顶点则不成为覆盖,
最小覆盖,含顶点个数最少的覆盖,
覆盖数,最小覆盖中顶点的个数,记为,?(G)
由此我们看到,上面的监狱看守问题实际上就是图的最小覆盖问题,
方法一,为了讨论覆盖数的计算,我们先介绍图的,关联矩阵,的概念
.1
0,
,,1
r:
),m,(n)(
ij
ijji
kijk
mnij
rev
vveVv
rR
时为顶点的邻边是即仅当以其他若存在使若存在其中为边数为顶点数图的关联矩阵关联矩阵为 5
4
3
2
1
1110000
1001100
0100110
0010011
0001001
v
v
v
v
v
R
7654321 eeeeeee
v2
v4
v3 v5
e1 e2
e3e
4
e5
e6
e7
υ1
v1
v2
v3
v4
v5
v6
e1 e2
e3
e4
e5 e
6
e7 e
8
关联矩阵
6
5
4
3
2
1
10010000
11000100
01100010
00101000
00011001
00000111
v
v
v
v
v
v
R
87654321 eeeeeeee
v1
v2v3
v4 v5
e1e2
e3 e
4 5
4
3
2
1
1000
0100
0010
0001
1111
v
v
v
v
v
R
4321 eeee
利用关联矩阵可以求极小覆盖,下面以此关联矩阵为例说明其步骤,
5
4
3
2
1
1110000
1001100
0100110
0010011
0001001
v
v
v
v
v
R
7654321 eeeeeee
1)在关联矩阵中取恰有两个 1的那一列中 1所在的行,
如 v3行,令 v3?K.
划去 v3行及 v3行中元素 1所在的 e1,e3,e6列,得矩阵,
5
4
2
1
1100
1010
0101
0011
v
v
v
v
7541 eeee
2)在上述矩阵中去恰有两个 1的那一列中 1所在的行,
如 v5行,令 v5?K,此时 K={v3,v5}
划去 v5行及 v5行中元素 1所在的 e5,e7列,得矩阵,
4
2
1
10
01
11
v
v
v
41 ee
3)由于 v1与 v2,v4相邻,划去 v2,v4行,v1?K,过程结束,此时 K={v1,v3,v5}
6
5
4
3
2
1
10010000
11000100
01100010
00101000
00011001
00000111
v
v
v
v
v
v
R
87654321 eeeeeeee
K={v2,
v4,v5 }
以上我们介绍的是求极小覆盖的方法,我们求出所有的极小覆盖后从中找出最小覆盖,
方法二,下面我们介绍一种可以用逻辑运算来进行计算极小覆盖的方法,
两个基本的逻辑运算,逻辑 + 和逻辑乘 ·,运算规律为,
(1)交换律 A+B=B+A,A·B=B·A.
(2)结合律 (A+B)+C=A+(B+C),(A·B)·C=A·(B·C).
(3)分配律 A·(B+C)=A·B+A·C,
A+B·C=(A+B)·(A+C).
(4)等幂律 A+A=A,A·A=A.
(5)吸收律 A+AB=A,A·(A+B)=A.
极小覆盖集的计算公式是,
)(),,,(
)(1
21
ivNu
n
i
in uvvvv
v2
v4
v3 v5v1
我们求前面例子的最小覆盖,
542432531 vvvvvvvvv
))()()((
))()()()((
),,,(
432553145423543214253121
4325531454235312421
21
vvvvvvvvvvvvvvvvvvvvvvvv
vvvvvvvvvvvvvvvvvvv
vvv n
))()(( 4325542531434253121 vvvvvvvvvvvvvvvvvvv
))(( 4325542531432 vvvvvvvvvvvv
从上面的计算我们得到,有 3个极小覆盖,且都为最小覆盖,?(G)=3.
练习,求下图的极小覆盖和最小覆盖,
v5
v1
v2
v3
v6
v4
答案,
有 5个极小覆盖,分别是
v1v3v4,v1v2v4v6,v1v3v5v6,
v2v3v5v6,v2v4v5v6.
其中 v1v3v4为最小覆盖,所以?(G)=3.
三、化学制品的存放与图的着色
1.问题,一家公司生产若干种化学制品,其中某些制品互不相容,存放在一起可能发生化学反应,
引起危险,因此公司必须把仓库分成相互隔离的若干区,以便把相不互容的制品分开存放,问至少要多少小区,怎样存放才能保证安全?
考虑比较简化的实例,设只有七种化学制品,用 a,b、
c,d,e,f,g表示,其中不能存放在一起的有,
a
b
c
d
e f g
图中把不能存放在一起的制品用边连接起来,
(a,b),(a,d),(b,c),(b,e),(b,g),(c,d),(c,e),(c,f),
(d,e),(d,g),(e,f),(f,g),用图来表示这种关系,
反之,没有边连接的制品 (点 )可以存放在一起,
2.图的点着色用若干种颜色给图的点着色,使相邻的点有不同的颜色,这称为图的点着色,
).(
,)2(;..,)1(
),.,.,2,1(),,(
21
点着色划分的一个则称此划分为使划分为将对图
kkV
VV
VVVV
kiVVEVG
ji
n
i
a
b
c
d
e f g?
3.图的色数在所有的着色中,所用颜色的最少数目,称为图的 色数,
}m in {)( 着色存在 kGkG
.2)4(
.3;2)3(
.)(:)2(
.0)(1)()1(
:
有边的树的色数是奇圈的色数是偶圈的色数是对完全图果关于图的色数的若干结
nK
GEG
n
图的色数目前还没有有效的计算方法,
一、关键路径分析技术与计划评审技术一项工程包括若干工序，完成每道工序需要一定的时间，工序之间存在先后顺序关系，那么如果安排各工序的开工时间和顺序，才能使工程尽可能早完成？
关键路径分析就是借助图的技术来求解此问题的一个方法。它告诉我们哪些工序是影响工程的关键，它们的提前或推后完工，
都必然影响工程的完工。
1.关键路径分析例题：设某项工程的各个工序与所需时间以及它们之间的相互关系如下表所示：
工 序 工序代号 所需时间（天） 紧后工序产品设计 a 60 b,c,d,e
外购配套件 b 45 l
下料、锻件 c 10 f
工装制造 1 d 20 g,h
木模 e 40 h
机械加工 1 f 18 l
工装制造 2 g 30 k
机械加工 2 h 15 l
机械加工 3 k 25 l
装配调试 l 35 /
现在我们要编制该工程的网络计划，确定各工序的开工时间等，特别是确定关键工序。
首先根据上面表所给出的内容，绘制网络图。
所谓 网络图 是由点（结点）、弧及权所构成的有向图。即有向赋权图。
在这里，一个 点表示一个事项 （或事件），
它是一个或若干个工序的开始或结束，是相邻工序在时间上的分界点。 点用圆圈和其里面的数字表示，数字表示点的编号，如
…
弧表示一个工序,用箭线,?”表示。 权表示完成某工序所需的时间,用 T(i,j)表示 。
上述问题对应的网络图：
a
60
b
45c
10
d
20
e
40
f
18
g
30
h
15
k
25
l
35
i j
箭尾事项 箭头事项
i紧前工序紧后工序有关网络图的构造请进一步参考有关书籍事项的时间：
（ 1）事项最早时间 TE(j)：
若事项为某些工序的箭尾事项，事项最早时间为各工序的最早可能的开始时间；
若事项为某些工序的箭头事项，事项最早时间为各工序的最早可能的结束时间
j
事项工序 工序
j
事项工序 i
TE(j)的计算,
TE(1)=0
TE(j)=max{ TE(i) + T(i,j) }
j=2,3,…,n
计算结果写入事项左下方的?内。如下：
a
60
b
45c
10
d
20
e
40
f
18
g
30
h
15
k
25
l
350 60 80
70
100
110 135 170
事项的时间：
（ 2）事项最迟时间 TL(i)：
箭头事项各工序的最迟必须结束的时间；
或 箭尾事项各工序的最迟必须开始的时间。
i
事项工序 工序
i
事项工序事项最迟时间的计算从终点开始：
TL(n)=TE(n)
TL(i)=min{ TL(j) - T(i,j) }
i=n-1,n-2,…,1
计算结果写入事项右下方的?内。
a
60
b
45c
10
d
20
e
40
f
18
g
30
h
15
k
25
l
350 60 80
70
100
110 135 170 170135110
120
117
80600
工序的时间,
（ 1）工序的最早开始时间 TES(i,j)
任何工序都必须在其紧前工序结束后才能开始。紧前工序最早结束时间即为工序最早可能开始时间，简称为工序最早开始时间。
最早开始时间等于该工序箭尾事项的最早时间，即
TES(i,j)＝ TE(i),
i j
TES (i,j)
工序的时间,
（ 2）工序的最早结束时间 TEF(i,j)
工序最早结束时间是工序最早可能结束的时间的简称。
最早结束时间等于该工序最早开始时间加上该工序的作业时间，即
TEF(i,j)＝ TES(i,j) +T(i,j).
i jT(i,j)
TES(i,j) TEF(i,j)
工序的时间,
（ 3）工序的最迟结束时间 TLF(i,j)
在不影响工程最早结束时间的条件下，
工序最迟必须结束的时间，简称为工序最迟结束时间。
最迟结束时间等于该工序箭头事项的最迟时间，即
TLF(i,j)＝ TL(j),
i j
TLF(i,j)
工序的时间,
（ 4）工序的最迟开始时间 TLS(i,j)
工序最迟开始时间是在不影响工程最早结束时间条件下，工序最迟必须开始的时间。
最迟开始时间等于该工序最迟结束时间减去该工序的作业时间，即
TLS(i,j)＝ TLF(i,j) -T(i,j).
i jT(i,j)
TLS(i,j) TLF(i,j)
工序的时间,
（ 5）工序的总时差 TF(i,j)
在不影响工程最早结束时间条件下，工序最早开始（或结束）时间可以推迟的时间，称为该工序的总时差。
TF(i,j) = TLS(i,j) -TES(i,j) = TLF(i,j) -TEF(i,j)
= TL(j) -TE(i)-T(i,j).
总时差为零的工序，开始和结束的时间没有一点机动的余地。
由这些弧线组成的路线就是网络中的关键路线，
这些工序就是关键工序,我们用红色的?表示 。
a
60
b
45
c
10
d
20
e
40
f
18
g
30
h
15
k
25
l
350 60 80
70
100
110 135 170 170135110
120
117
80600
箭尾事件的最早开始时间 (方框内 )为工序的最早开始时间,箭头事件的最迟结束时间 (三角内 )为工序的最迟结束时间,工序 c,f
线的总时差为 47,工序 e,h线的总时差为 20,工序 b的总时差为 30.
当然,象我们书上那样画图处理也可以,
2、计划评审技术由于完成每道工序需要的时间一般难以准确估计，因此不同的人员有不同的估计,这就使得关键路径不能准确确定,这正是关键路径分析技术的缺点,
计划评审技术把各项工序的延续时间视为彼此独立的随机变量,随机变量的任一组取值表示一种可能的具体情况,而且它采用如下简便方法,对每一项工序,要求给出三个时间,分别为最可能的延续时间 (m),最乐观 (最短 )时间 (n),最悲观 (最长 )时间 (b).并计算出每一项工序的延续时间的期望值 E和方差 σ2.其公式为
E=(4m+a+b)/6,σ2 =(b-a)2/36.
工 序 工序代号 所需时间 m,a,b（天） 紧后工序产品设计 a 60,44,100 b,c,d,e
外购配套件 b 45,35,55 l
下料、锻件 c 10,9,11 f
工装制造 1 d 20,16,24 g,h
木模 e 40,35,45 h
机械加工 1 f 18,15,21 l
工装制造 2 g 30,27,33 k
机械加工 2 h 15,13,17 l
机械加工 3 k 25,20,30 l
装配调试 l 35,30,46 /
工序 a b c d e f g h k l
E 64 45 10 20 40 18 30 15 25 36
σ2 87.
111
11.
11
1.1
11
1.7
78
2.7
78
1 1 0.44
4
2.7
78
7.11
1
我们把计算出的结果列表如下,
由于工序 b到 k的期望值 E与原来的值一样,因此我们以 E来进行关键路径分析时,工序 adgkl形成的路径依然是关键路径,不过由于工序 a和 l的数值发生了变化,表中的 TE(i)也发生了变化,因此新的关键路径分析结果如下表,
a
64
b
45
c
10
d
20
e
40
f
18
g
30
h
15
k
25
l
360 64 84
74
104
114 139 175 175139114
124
121
84640
由于每个工序的延续时间是独立的随机变量,因此各个结点,即事件也是各随机变量,
记为 ζi,相应地我们取新的随机变量 Zi=(ζi -
TE(i) )/σi,这里 σi2是同一路径上直到第个事件的方差的和,故 Zi服从标准正态分布,
iZ
dxesP xii
~
2 2/
2
1)(
这里 si是第 i各事件的实际计划开始时间,
我们来对此进行评审,简单说,若上面的这个概率太大,表明计划时间不恰当,应该推迟,下表是我们的评审结果,
i
Ei
i
iTz
)(~
事件 TE(i) σi2 si ~Zi P(ζi >si)
1 0 0 0 / 0.000
2 64 87.111 60 -0.429 0.666
3 74 88.222 70 -0.426 0.665
4 84 88.889 80 -0.424 0.664
5 104 89.889 100 -0.422 0.664
6 114 89.889 110 -0.422 0.664
7 139 92.667 135 -0.416 0.661
8 174 99.778 170 -0.400 0.655
总的来说,第二个事件安排得太早,因此应该调整,比如调整为 64,则后面的每一个事件也相应地推后 4天,这样,每个概率都是 0.5,大致可以付诸实施,
3、冈特流程图当一项工程已经被关键路径分析或计划评审之后,所得到的部分结果可由冈特流程图形象地加以表示,
再根据此图,
进一步作出人力,物力随时间的安排图,直观明了,
易于安排和调配使用,
a
b c
d
h
l
e
g
f
k
t
工序二、监狱看守问题与图的覆盖一座监狱的几间牢房有道路相连,设如图所示,监狱看守要设在通过道路年直接监视所有牢房的地方,如果看守不得走动,那么他们应呆在某些牢房 (即路口 )所在地,问至少需要几名看守才能完成监视任务?
v1
v2
v4
v3 v5
e1 e2
e3e
4
e5
e6
e7
若图 G的每条边都至少有一个端点在顶点集 V
的一个子集 K中,则称 K为 G的 覆盖,
极小覆盖,一覆盖,若减少其中任一顶点则不成为覆盖,
最小覆盖,含顶点个数最少的覆盖,
覆盖数,最小覆盖中顶点的个数,记为,?(G)
由此我们看到,上面的监狱看守问题实际上就是图的最小覆盖问题,
方法一,为了讨论覆盖数的计算,我们先介绍图的,关联矩阵,的概念
.1
0,
,,1
r:
),m,(n)(
ij
ijji
kijk
mnij
rev
vveVv
rR
时为顶点的邻边是即仅当以其他若存在使若存在其中为边数为顶点数图的关联矩阵关联矩阵为 5
4
3
2
1
1110000
1001100
0100110
0010011
0001001
v
v
v
v
v
R
7654321 eeeeeee
v2
v4
v3 v5
e1 e2
e3e
4
e5
e6
e7
υ1
v1
v2
v3
v4
v5
v6
e1 e2
e3
e4
e5 e
6
e7 e
8
关联矩阵
6
5
4
3
2
1
10010000
11000100
01100010
00101000
00011001
00000111
v
v
v
v
v
v
R
87654321 eeeeeeee
v1
v2v3
v4 v5
e1e2
e3 e
4 5
4
3
2
1
1000
0100
0010
0001
1111
v
v
v
v
v
R
4321 eeee
利用关联矩阵可以求极小覆盖,下面以此关联矩阵为例说明其步骤,
5
4
3
2
1
1110000
1001100
0100110
0010011
0001001
v
v
v
v
v
R
7654321 eeeeeee
1)在关联矩阵中取恰有两个 1的那一列中 1所在的行,
如 v3行,令 v3?K.
划去 v3行及 v3行中元素 1所在的 e1,e3,e6列,得矩阵,
5
4
2
1
1100
1010
0101
0011
v
v
v
v
7541 eeee
2)在上述矩阵中去恰有两个 1的那一列中 1所在的行,
如 v5行,令 v5?K,此时 K={v3,v5}
划去 v5行及 v5行中元素 1所在的 e5,e7列,得矩阵,
4
2
1
10
01
11
v
v
v
41 ee
3)由于 v1与 v2,v4相邻,划去 v2,v4行,v1?K,过程结束,此时 K={v1,v3,v5}
6
5
4
3
2
1
10010000
11000100
01100010
00101000
00011001
00000111
v
v
v
v
v
v
R
87654321 eeeeeeee
K={v2,
v4,v5 }
以上我们介绍的是求极小覆盖的方法,我们求出所有的极小覆盖后从中找出最小覆盖,
方法二,下面我们介绍一种可以用逻辑运算来进行计算极小覆盖的方法,
两个基本的逻辑运算,逻辑 + 和逻辑乘 ·,运算规律为,
(1)交换律 A+B=B+A,A·B=B·A.
(2)结合律 (A+B)+C=A+(B+C),(A·B)·C=A·(B·C).
(3)分配律 A·(B+C)=A·B+A·C,
A+B·C=(A+B)·(A+C).
(4)等幂律 A+A=A,A·A=A.
(5)吸收律 A+AB=A,A·(A+B)=A.
极小覆盖集的计算公式是,
)(),,,(
)(1
21
ivNu
n
i
in uvvvv
v2
v4
v3 v5v1
我们求前面例子的最小覆盖,
542432531 vvvvvvvvv
))()()((
))()()()((
),,,(
432553145423543214253121
4325531454235312421
21
vvvvvvvvvvvvvvvvvvvvvvvv
vvvvvvvvvvvvvvvvvvv
vvv n
))()(( 4325542531434253121 vvvvvvvvvvvvvvvvvvv
))(( 4325542531432 vvvvvvvvvvvv
从上面的计算我们得到,有 3个极小覆盖,且都为最小覆盖,?(G)=3.
练习,求下图的极小覆盖和最小覆盖,
v5
v1
v2
v3
v6
v4
答案,
有 5个极小覆盖,分别是
v1v3v4,v1v2v4v6,v1v3v5v6,
v2v3v5v6,v2v4v5v6.
其中 v1v3v4为最小覆盖,所以?(G)=3.
三、化学制品的存放与图的着色
1.问题,一家公司生产若干种化学制品,其中某些制品互不相容,存放在一起可能发生化学反应,
引起危险,因此公司必须把仓库分成相互隔离的若干区,以便把相不互容的制品分开存放,问至少要多少小区,怎样存放才能保证安全?
考虑比较简化的实例,设只有七种化学制品,用 a,b、
c,d,e,f,g表示,其中不能存放在一起的有,
a
b
c
d
e f g
图中把不能存放在一起的制品用边连接起来,
(a,b),(a,d),(b,c),(b,e),(b,g),(c,d),(c,e),(c,f),
(d,e),(d,g),(e,f),(f,g),用图来表示这种关系,
反之,没有边连接的制品 (点 )可以存放在一起,
2.图的点着色用若干种颜色给图的点着色,使相邻的点有不同的颜色,这称为图的点着色,
).(
,)2(;..,)1(
),.,.,2,1(),,(
21
点着色划分的一个则称此划分为使划分为将对图
kkV
VV
VVVV
kiVVEVG
ji
n
i
a
b
c
d
e f g?
3.图的色数在所有的着色中,所用颜色的最少数目,称为图的 色数,
}m in {)( 着色存在 kGkG
.2)4(
.3;2)3(
.)(:)2(
.0)(1)()1(
:
有边的树的色数是奇圈的色数是偶圈的色数是对完全图果关于图的色数的若干结
nK
GEG
n
图的色数目前还没有有效的计算方法,
