如果两个人之间相互认识，则在这两个人(顶点)间连一 条红色边，如果两个人不认识，则在这两个人(顶点)间 连一条蓝色边(下面会看到这样做的好处)
那么这样我们就得到了一个由红边和蓝边组成的6阶完 全图
我们实际上要证明的就是这个图中或者存在一个红三 角形(认识)，或者存在一个蓝三角形(不认识)
任取一个顶点v0，由它连出5条边到其它的顶点，这五条边只有红 色和蓝色两种
F(P) F(e) eE ( P)
则称F (P)为路径P(u, v) 的权或长度(距离).
定义2 若P0 (u, v) 是G 中连接u, v的路径, 且对任 意在G 中连接u, v的路径P (u, v)都有
F (P0)≤F(P), 则称P0 (u, v) 是G 中连接u, v的最短路.
36
重要性质：
握手定理：
n
d (vi ) 2m
i 1
26
我们今后只讨论有限简单图：
(1) 顶点个数是有限的; (2) 任意一条边有且只有两个不同的点与它相互关联; (3) 若是无向图, 则任意两个顶点最多只有一条边与 之相联结; (4) 若是有向图, 则任意两个顶点最多只有两条边与 之相联结. 当两个顶点有两条边与之相联结时，这两条 边的方向相反. 如果某个有限图不满足(2)(3)(4),可在某条边上增设 顶点使之满足.
根据抽屉原理，肯定有一种颜色的边有3条或3条以上,不妨设为红
色
v0
vi
vk
vj
如果vi,vj,vk之间的边都是蓝边，则图中存在一个蓝三角形 如果至少有1条为红边，那么它总会与v0发出的两条红边组成一个红三 角形。 这样就证明了这个命题。
4、 商人们怎样安全过河
问题(智力游戏)
随从们密约, 在河的任一 岸, 一旦随从的人数比商 人多, 就杀人越货.
以可允许的10个状态向量作为顶点,将可能互相转移 的状态用线段连接起来构成一个图.
根据此图便可找到渡河方法.
29
(1,1,1,1) (1,1,1,0) (1,1,0,1) (1,0,1,1) (1,0,1,0) (0,0,0,0) (0,0,0,1) (0,0,1,0) (0,1,0,0) (0,1,0,1)
河 小船(至多2人)
但是乘船渡河的方案由商人决定.
商人们怎样才能安全过河?
问题分析
多步决策过程
3名商人3名随 从来自决策~ 每一步(此岸到彼岸或彼岸到此岸)船上的人员
要求~在安全的前提下(两岸的随从数不比商人多),经有限 步使全体人员过河.
模型构成
xk~第k次渡河前此岸的商人数 yk~第k次渡河前此岸的随从数 sk=(xk , yk)~过程的状态
定义2 若将图G的每一条边e都对应一个实数F (e), 则称F (e)为该边的权, 并称图G为赋权图(网络), 记为G = (V, E , F ).
定义3 任意两点均有通路的图称为连通图. 定义4 连通而无圈的图称为树, 常用T表示树.
28
例 一摆渡人欲将一只狼,一头羊,一篮菜从河西渡过 河到河东.由于船小,一次只能带一物过河，并且狼与羊, 羊与菜不能独处.给出渡河方法.
sk+1=sk+(-1)k
d多k 步决策 问题
~状态转移律
求dkD(k=1,2, n), 使skS, 并按 转移律由 s1=(3,3)到达 sn+1=(0,0).
模型求解
S={(x , y) x=0, y=0,1,2,3;
• 穷举法 ~ 编程上机
x =3, y=0,1,2,3; x=y=1,2}
• 图解法
y
状态s=(x,y) ~ 16个格点
3
s1
允许状态 ~ 10个 点
允许决策 ~ 移动1或2格; 2
d1
k奇,左下移; k偶,右上移.
1
d1, ，d11给出安全渡河方案 d11
评注和思考
0
sn+1
1
2
3x
规格化方法,易于推广 考虑4名商人各带一随从的情况
图的定义
图论中的“图”并不是通常意义下的几何图形或物 体的形状图, 而是以一种抽象的形式来表达一些确定的 事物之间的联系的一个数学系统.
定义1 一个有序二元组(V, E ) 称为一个图, 记为G = (V, E ), 其中
① V称为G的顶点集, V≠, 其元素称为顶点或结点,
简称点; ② E称为G的边集, 其元素称为边, 它联结V 中的两
个点, 如果这两个点是无序的, 则称该边为无向边, 否则, 称为有向边.
如果V = {v1, v2, … , vn}是有限非空点集, 则称G为 有限图或n阶图.
i j;
上可用权矩阵来
表示.
32
vij E.
2020/6/15
0 6 8
A
3 4
0
7 0 5
2 0
无向图G的权矩阵A是一个对称矩阵.
0 6 3 4
A
6 3 4
0 7
7 0 2
2 0
33
⑶ 关联矩阵 一个有m条边的n阶有向图G的关联矩 阵A = (aij )n×m , 其中
(aij )n×m , 其中
1, aij 0,
若vi与ej关联; 若vi与ej不关联.
无向图的关联矩阵每列的元素中有且仅有两个1.
1 1 1 0 0 0
A
1
0 0
0 1 0
0 0 1
1 1 0
1 0 1
0 11
35
2、最短路径算法
定义1 设P(u, v) 是赋权图G = (V, E , F) 中从点u到 v的路径, 用E(P) 表示路径P(u, v)中全部边的集合, 记
24
一个图会有许多外形不同的图解, 下面两个图表示 同一个图G = (V, E )的图解.其中
V = {v1 , v2 , v3 , v4}, E = { v1v2 , v1v3 , v1v4 , v2v3 , v2v4 , v3v4}.
这两个图互为同构图,今后将不计较这种外形上的差 别,而用一个容易理解的、确定的图解去表示一个图.25
解：用四维0-1向量表示(人,狼,羊,菜)在河西岸的 状态(在河西岸则分量取1,否则取0),共有24 =16 种状态. 在河东岸的状态类似记作.
由题设,状态(0,1,1,0),(0,0,1,1),(0,1,1,1)是不允许 的,从而对应状态(1,0,0,1), (1,1,0,0), (1,0,0,0)也是不允 许的.
21
1a12
212
b
23
32
21
1a12
212
b
234
32
21
1a12
212
b
234
5
32
21
1a12
212
b
234
56
6
32
21
1a12
212
b
234
567
67
32
21
1a12
212
b
234
8
5678
678
3、引例
现有6个人，任意两人之间或者相互认识 ，或者相互不认识，证明这6个人中，或者有 3个人彼此都认识，或者有3个人彼此不认识
xk, yk=0,1,2,3; k=1,2, S ~ 允许状态集合
S={(x , y) x=0, y=0,1,2,3; x=3, y=0,1,2,3; x=y=1,2}
uk~第k次渡船上的商人数
uk, vk=0,1,2;
vk~第k次渡船上的随从数
k=1,2,
dk=(uk , vk)~决策 D={(u , v) u+v=1, 2} ~允许决策集合
22
如果E的每一条边都是无向边, 则称G为无向图(如 图1); 如果E的每一条边都是有向边, 则称G为有向图 (如图2); 否则, 称G为混合图.
图
图
1
2
并且常记
V = {v1, v2, … , vn}, |V | = n ; E = {e1, e2, … , em}(ek=vivj ) , |E | = m.
2、一个简单的例子
印刷电路板将布线区域划分为n×m个方格 阵列
精确的电路板布线问题要求确定连接方格 a的中点到方格b的中点的最短布线方案。
布线时电路只能沿直线或直角布线。 为避免线路相交，已布线方格做上封闭标
记，其他线路布线不允许穿过封闭区域。
a b
1
1a1
1
b
2
21
1a12
212
b
2
32
所在的点, 即:l(x)=min(l(t)) (t T),
注：l(t)不一定是从a到t的最短路径，因为最短路径中可能包含
T中其他的节点。
定理1 若t是T中关于P由最小指标的结点，则l(t)是a和t 之间的最短距离。
定理2 设 T为V的子集，P=V-T，设
(1)对P中的任一点p,存在一条从a到p的最短路径,这条
路径仅有P中的点构成,
(2)对于每一点t,它关于P的指标为l(t),令x为最小指标
思路一
只有6个人，人数非常少，可以枚举任 意两人之间的关系，然后判断每一种情 况是否符合题意。如果所有情况都满足， 则命题成立。
虽然只有6个人，但是这样做的时间复 杂度可不低，枚举次数为215
只能借助计算机了。。。
有没有人可以直接证明的办 法呢？
思路二
有了图论这个强大的工具，我们还是像往常一 样，以人为顶点，关系为边，建图。但是为了 以后的直观，这里图的建立有一点小小的不同：
若v0 v1 … vm 是图G中从v0到vm的最短路, 则 1≤k≤m, v0v1 … vk 必为G中从v0到vk的最短路.
即：最短路是一条路，且最短路的任一段也是最 短路.