离散数学图论与关系中有图题目docxWord文档下载推荐.docx
《离散数学图论与关系中有图题目docxWord文档下载推荐.docx》由会员分享，可在线阅读，更多相关《离散数学图论与关系中有图题目docxWord文档下载推荐.docx（35页珍藏版）》请在冰点文库上搜索。
n；
对于二
部图G
V1,V2,E,E
时即
1，E
G2
；
在彼得森图G中，
存在奇数长的基本回路，因而G3，又彼得森图既不是完全图也不是长度为奇数的基
本回路，且G3，由定理G3，故G3）
例2给右边三个图的顶点正常着色，每个图至少需要几种颜色。
答案：
（1）
2；
（2
）
3；
（3）
4
例3
有8种化学品A,B,C,D,P,R,S,T
（3）
要放进贮藏室保管。
出于安全原因，
下列各组药品不能贮在同一个室内：
A-R,A-C,A-T,R-P,P-S,S-T,T-B,B-D,D-C,R-S,R-B,
P-D,S-C,S-D，问贮藏这8种药品至少需要多少个房间？
S
TRP
CT
解以8种药品作为结点，若两种药品不能贮在同一个室
RP
C
内，则它们之间有一条边，这样得右图，转化为图的正常着
D
B
色问题。
（1）对各结点按度数的递减顺序排列为
SRDPCTAB；
A
（2）对S及不与之相邻点A，B着c色；
（3）对R及不与之
K1
K2
1
K9
J2
J3
J4
J1
相邻点D着c2色；
（4）对P和C着c3色。
故着色数
G3；
K8
K3
K4
K7
B1
B2
B3
B4
B5
又因为因S,D,P为K3子图，故着色数
3，从而
K6
K5
G3。
因此贮藏这8种药品至少需要
3个房间。
贮藏方式之一为
SAB,RDT,PC。
（考试排考或老师排课让选修的学生避免冲突的问题类似处理！
）
二、强连通一定单向连通，单向连通一定弱连通！
弱连通图单向连通图单向连通图
强连通图强连通图强连通图
弱连通图、单向连通图和强连通图
三、
哈密顿图欧拉图
同构的无向图
欧拉图
哈密顿图
均不是
同构的有向图
1、设G为无向欧拉图，求G中一条欧拉回路的Fleury算法如下：
第1步，任取G中的一
个结点v0，令P0v0；
第2步，假设Pi
v0e1v1e2Lviei已选好，按下面方法从
E
e1,e2,L,ei
中选ei1：
（1）ei1与ei相关联，
（2）除非无别的边可供选择，否则
ei1不
应该是GiG
e1,e2
L,ei的断边；
第3步，当第2步不能执行时，算法停止。
（有向欧拉图的欧拉回路可类似求出，可用于解决邮路问题）
邮路问题用图论的概念描述如下：
在一个带权图
G中，怎样找到一条回路
C，使得C包含
G中的每一条边至少一次，而且回路
C具有最小权。
C分以下三种情况：
（1）如果G是欧
拉图，必定有欧拉回路，
C即可找到；
（2）如果G是具有从vi到vj的欧拉通路的半欧拉图，
的构造如下：
找到从
vi到vj的欧拉通路及vi到vj的最小权通路（即最短路径）
--这两条
通路和并在一起就是最小权回路；
（3）如果G不是半欧拉图，一般说来，
G中包含多条边
的回路，其中夫的边数与奇数结点数目有关，若奇数结点多于
2，则回路中会出现更多的重
复的边。
问题是怎样使重复边的权综合最小。
在理论上已证明：
一条包括
G的所有边的回
路C具有最小权当且仅当：
（1，每条边最多重复一次，（2，在G的每个回路上，有重复边的权之和小于回路权的一半。
例：
求右图所示的带权图中最优投递路线，
邮局
40
在D点。
50
6
8G
E,F两个。
用标
35
解先观察奇度结点，此图中有
19
号法求出其间最短路径
EGF，其权为28。
然后
12D
23
20
将最短路径上的边重复一次，
于是得欧拉图G*，
30
10
F
求从D
出的一条欧拉回路，如
DEGFGEBACBDCFD
，其权为281=35+8+20+20+8+40+50+30+19+6+12+10+23
。
2、求接近最小权哈密顿回路的“最邻近”算法：
设
V,E,W
是有n个顶点的无向完
全图，
（1）任取v0
V作为始点，令L
为v0
，k
0；
（2）令
wvk,x
min
wvk,vv不在L中，置vk1
x。
置Lv0v1Lvk
1,k
k
1；
（3）若
n1，转
（2）；
（4）置Lv0v1Lvkv0
，结束。
（可近似解决货郎担问题）
例1
用最邻近算法求下图的最短哈密尔顿回路。
a
8
e
14
b
5
7
c
d
所得长度为14+6+5+5+7=37，与最短7+8+5+10+6=36很接近了！
例2求下图的最短哈密尔顿回路。
12
18
11
三条比较，最小权为47。
例3已知A,B,C,D,E,F,G7
dc
个人中，A会讲英语，B会讲英语和汉语，B
C会讲英语、意大利语和俄语，D会讲日语和汉语，E会讲意大利语A和德语，F会讲俄语，G会讲俄语、日语和法语。
能否将他们的座位
安排在圆桌旁，使得每个人都能与他身边的人交谈？
（按哈密尔顿回路安排就是了！
）FE例411个学生要共进晚餐，他们将坐成一个圆桌，计划要求每次晚
餐上每个学生有完全不同的邻座，这样能攻进晚餐几天？
（
K11共有10
9
1111
55条边，每条哈密尔顿回路有
11条边，因而共有
5条没有公
2
共边的哈密尔顿回路，可吃
5天！
分别用
2，3，4，5与11互素，以它们为步长能找到！
半哈密顿图与哈密顿图补例：
彼德森图
补充内容：
设G是无向完全图，若对G的每条边指定一个方向，所得的图称为竞赛图。
证明：
在无又
向回路（或有向圈）的竞赛图D
VD,ED中，对任意u,vVD,dudv
（用反证法，见于《离散数学习题与解析》胡辛启清华第
2版）
可以证明：
对于每个竞赛图
D，至多改变一条边的方向后就可以变成哈密尔顿图。
四、求最小生成树
1、破圈法过程演示
（1）令EE；
（2）选取E中的一条简单回路C,设C中权最大的边为e，令EE{e}；
（3）重复步骤
（2）,直到EV1为止。
1224
91113
107
题目最后结果
2、Kruskal算法过程演示
（1）首先将边按权值由小到大排成序列
S,
令i
1,E
{S[1]}；
（2）令i
i
1,选取边S[i]与
E中的边不构成简单回路，
则令E
U{S[i]}；
（3）重复步骤
（2）,直到E
V
1为止。
13
3、Prim算法过程演示
（1）从V
中任意选取结点
v0，令V
{v0}；
（2）在V与V
V之间选一条权最小的边
e（vi,vj
），其中viV,vjV
并且令E
U{e},V
VU{vj}；
（3）重复步骤
（2）,
直到V
V为止。
增加破圈法一例演示：
4、求下列最小生成树的权值
22
C（T）=1+2+3=6
C（T）=1+2+3+1=7
15
36
28
17
16
C（T）=1+3+4+8+9+23=48
C（T）=1+2+3+5+7=18
617
716
86
1312
C（T）=3+6+6+7=22
911
64
13
C（T）=4+5+6+7=22
v2
v5
v1
v3
10v7
v6
v4
C（T）=2+3+4+5+6+10=30
100
C（T）=2+2+3+5+6+100=118
487
910
2012
C（T）=8+9+4+7=28
C（T）=1+3+3+2+1=10
98
32
5、在右图所示的带权图中，
共有多少棵生成树，他们的权各为多少？
，
其中哪些是图中的最小生成树？
a1b
322
d4c
w=8
w=6
w=7
w=9
五、求最优二叉树
对给定的实数序列
w1w2
L
wt，构造最优r元树的递归算法：
1、求最优二元树的
Huffman
算法：
第一步，连接以
w1,w2
为权的两片树叶，得一个分支点
及其所带的权w1
w2；
第二步，在w1
w2,w3,L,wt中选出两个最小的权，连接它们对应
的结点（不一定都是树叶），又得分支结点及其所带的权；
重复第二步，直到形成
t
1个分
支点，t片树叶为止。
2、求最优rr
元树的Huffman算法：
（1）若t
1为整数，则求法与求最优二元树的
r
Huffman算法类似，只是每次取
r个最小的权；
（2）若t
不为整数，得余数
s
[1,r
1），
将s
1个较小的权对应的树叶为兄弟放在最长的路径上，然后算法同（
1）。
1、找出叶的权分别为2，3，5，7，11，13，17，19，23，29，31，37，41的最优叶加权二
叉树，并求其加权路径的长度。
wvLv789）
vV
313741
29
2、求带权为2，3，5，7，8的最优二元树T，并给出T对应的二元前缀码集合。
（B={00,010,011,10,11},W（T）=253233272855）
578
23
3、求带权为1，2，3，4，5，6，7，8的最优二元树T，并给出T对应的二元前缀码集合。
（B={000,001,01000,01001,0101,011,10,11},W（T）=102）
78
456
12
345623
4、
（1）求带权为1，1，2，3，3，4，5，6，7的最优三元树；
（2）求带权为1，1，2，3，
3，4，5，6，7，8的最优三元树
32
C（T1）=61,C（T2）=81
六、如图G
v2b
f
gv5
v1v4
图中的边割集有S1{a,f
升级会员 