离散数学图论与关系中有图题目

图论中有图题目 一、 4个结点、6个结点和8个结点的三次正则图没有一个简单的办法能确定图的色数以及用尽可能少的颜色给图的节点着色。Welch-Powell给出了一个使颜色数尽可能少（不一定最少）的结点着色方法，在实际使用中比较有效： 第1步、 将图的结点按度数的非增顺序排列；第2步、用第1种颜色给第1个结点着色，并按照结点排列顺序，用同一种颜色给每个与前面已着色的结点不邻接的结点着色；第3步、换一种颜色对尚未着色的结点按上述方法着色，如此下去，直到所有结点全部着色为止。 例1 分别求右面两图的色数

（1）由于（1）中图G中无奇数长的基本回路，由定理可知G2。 （2）由于（2）中图G含子图轮图W4，由于W44，故G4。又因

为此图的最大度G4，G不是完全图，也不是奇数长的基本回路，由定理可知（对n阶轮图Wn，n为奇数时有Wn3，n为偶GG4，因而G4。

数时有Wn4；对n阶零图Nn，有Nn1；完全图Kn，有Knn；对于二部图GV1,V2,E,E时即Nn1，E时即G2；在彼得森图G中，存在奇数长的基本回路，因而G3，又彼得森图既不是完全图也不是长度为奇数的基本回路，且G3，由定理G3，故G3） 例2 给右边三个图的顶点正常着

色，每个图至少需要几种颜色。 答案：（1）

(1)(2)G2；（2）

（3）G4 G3；

例3 有8种化学品A,B,C,D,P,R,S,T

(2)(1)(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种药品至少需要多少个房间？

TR解 以8种药品作为结点，若两种药品不能贮在同一个室RPPCDD内，则它们之间有一条边，这样得右图，转化为图的正常着

BB色问题。（1）对各结点按度数的递减顺序排列为SRDPCTAB；A（2）对S及不与之相邻点A，B着c1色；（3）对R及不与之

K9K1K2K3K4K6K5J1SSCAJ2J3J4T相邻点D着c2色；（4）对P和C着c3色。故着色数G3；K8K7又因为因S,D,P为K3子图，故着色数

G3，从而

B1B2B3B4B5G3。因此贮藏这8种药品至少需要3个房间。贮藏方式之一为SAB, RDT, PC。

(考试排考或老师排课让选修的学生避免冲突的问题类似处理！)

二、强连通一定单向连通，单向连通一定弱连通！

弱连通图单向连通图单向连通图强连通图强连通图强连通图

弱连通图、单向连通图和强连通图三、

哈密顿图欧拉图同构的无向图欧拉图哈密顿图均不是同构的有向图

1、设G为无向欧拉图，求G中一条欧拉回路的Fleury算法如下：第1步，任取G中的一

精彩文档

实用标准文案

个结点v0，令Piv0e1v1e20v0；第2步，假设Pi已选好，按下面方法从vieEe1,e2,（1）ei1与ei相关联，（2）除非无别的边可供选择，否则ei1不,ei中选ei1：

应该是GiGe1,e2,,ei的断边；第3步，当第2步不能执行时，算法停止。

（有向欧拉图的欧拉回路可类似求出，可用于解决邮路问题）

邮路问题用图论的概念描述如下：在一个带权图G中，怎样找到一条回路C，使得C包含G中的每一条边至少一次，而且回路C具有最小权。C分以下三种情况：（1）如果G是欧拉图，必定有欧拉回路，C即可找到；（2）如果G是具有从vi到vj的欧拉通路的半欧拉图，C的构造如下：找到从vi到vj的欧拉通路及vi到vj的最小权通路（即最短路径）--这两条通路和并在一起就是最小权回路；（3）如果G不是半欧拉图，一般说来，G中包含多条边的回路，其中夫的边数与奇数结点数目有关，若奇数结点多于2，则回路中会出现更多的重复的边。问题是怎样使重复边的权综合最小。在理论上已证明：一条包括G的所有边的回路C具有最小权当且仅当：（1，每条边最多重复一次，（2，在G的每个回路上，有重复边的权之和小于回路权的一半。 例：求右图所示的带权图中最优投递路线，邮局40在D点。 506358解 先观察奇度结点，此图中有E,F两个。用标

1912号法求出其间最短路径EGF，其权为28。然后23BEAG将最短路径上的边重复一次，于是得欧拉图G，

*

30D1020C求从D出的一条欧拉回路，如

DEGFGEBACBDCFD，其权为281=35+8+20+20+8+40+50+30+19+6+12+10+23。

2、求接近最小权哈密顿回路的“最邻近”算法：设GV,E,W是有n个顶点的无向完全图，（1）任取v0V作为始点，令L为v0，k0；（2）令

Fwvk,xminvkvv,不在L中，置vk1x。置Lv0v1wkn1，转（2）；（4）置Lv0v1（3）若vk1,kk1；

（可近似解决货郎担问题） vkv0，结束。

例1 用最邻近算法求下图的最短哈密尔顿回路。

a146b561478ae57ae586bc1456b7e5c10ddc10d

所得长度为14+6+5+5+7=37，与最短7+8+5+10+6=36很接近了！

精彩文档

实用标准文案

例2 求下图的最短哈密尔顿回路。

b1018127141118b127101811b710b1412cadcadcadca1114d

三条比较，最小权为47。

例3 已知A,B,C,D,E,F,G7个人中，A会讲英语，B会讲英语和汉语，C会讲英语、意大利语和俄语，D会讲日语和汉语，E会讲意大利语和德语，F会讲俄语，G会讲俄语、日语和法语。能否将他们的座位安排在圆桌旁，使得每个人都能与他身边的人交谈？ （按哈密尔顿回路安排就是了！）

例4 11个学生要共进晚餐，他们将坐成一个圆桌，计划要求每次晚

BAGF111098765CDE1234餐上每个学生有完全不同的邻座，这样能攻进晚餐几天？（K11共有

1111155条边，每条哈密尔顿回路有11条边，因而共有5条没有公

2共边的哈密尔顿回路，可吃5天！分别用2，3，4，5与11互素，以它们为步长能找到！） 半哈密顿图与哈密顿图补例：

彼德森图

补充内容：

设G是无向完全图，若对G的每条边指定一个方向，所得的图称为竞赛图。证明：在无又向回路（或有向圈）的竞赛图DVD,ED中，对任意u,vVD,dudv

（用反证法，见于《离散数学习题与解析》胡辛启清华第2版）

可以证明：对于每个竞赛图D，至多改变一条边的方向后就可以变成哈密尔顿图。

四、求最小生成树 1、破圈法过程演示

(1)令EE；(2)选取E中的一条简单回路C, 设C中权最大的边为e，令EE{e}；(3)重复步骤(2), 直到EV1为止。

精彩文档

实用标准文案

12910题目

2118574136 最后结果

2981356

2910118574136910211857610139211813569211856

132、Kruskal算法过程演示

(1)首先将边按权值由小到大排成序列S, 令i1,E{S[1]}；(2)令ii1,选取边S[i]与

E中的边不构成简单回路，则令EE{S[i]}；(3)重复步骤(2), 直到EV1为止。

212212135135613821356

3、Prim算法过程演示

(1)从V中任意选取结点v0，令V{v0}；(2)在V与VV之间选一条权最小的边

e(vi,vj)，其中viV,vjVV并且令EE{e},VV{vj}；(3)重复步骤(2),

直到VV为止。

9998988521598159821359821356

增加破圈法一例演示：

精彩文档

实用标准文案

137682543176524316524315243152

4、求下列最小生成树的权值

12234

C(T)=1+2+3=6

31531

C(T)=1+2+3+1=7

24620232836814916153

C(T)=1+3+4+8+9+23=48

1718549761023

C(T)=1+2+3+5+7=18

精彩文档

实用标准文案

617713863161712

C(T)=3+6+6+7=22

1687569613114

C(T)=4+5+6+7=22

v292v14510v5v336831012v77v4C(T)=2+3+4+5+6+10=30

11v6

1223410037

56C(T)=2+2+3+5+6+100=118

精彩文档

实用标准文案

4879102081215

C(T)=8+9+4+7=28

1355736241

C(T)=1+3+3+2+1=10

125412585854971689716899

54145541453636236362

161139108211176392451087C(T)=1+2+3+5+7=1845

5、在右图所示的带权图中，共有多少棵生成树，他们的权各为多少？，其中哪些是图中的最小生成树？

精彩文档

a1b322d4c实用标准文案

a31w=8412w=6bcbca31w=6b2adad1w=74124b2a3w=94b2da3dadw=824cb2cbda3cbdw=72w=72ccdc五、求最优二叉树

对给定的实数序列w1w2wt，构造最优r元树的递归算法：

1、求最优二元树的Huffman算法：第一步，连接以w1,w2为权的两片树叶，得一个分支点及其所带的权w1w2；第二步，在w1w2,w3,,wt中选出两个最小的权，连接它们对应

的结点（不一定都是树叶），又得分支结点及其所带的权；重复第二步，直到形成t1个分支点，t片树叶为止。

t1为整数，则求法与求最优二元树的r1t1Huffman算法类似，只是每次取r个最小的权；（2）若不为整数，得余数s[1,r1)，

r1将s1个较小的权对应的树叶为兄弟放在最长的路径上，然后算法同（1）。

2、求最优rr3元树的Huffman算法：（1）若

1、找出叶的权分别为2，3，5，7，11，13，17，19，23，29，31，37，41的最优叶加权二叉树，并求其加权路径的长度。（

wvLv789）

vV29111323137411423753

172、求带权为2，3，5，7，8的最优二元树T，并给出T对应的二元前缀码集合。

精彩文档

实用标准文案

（B={00,010,011,10,11},W(T)=253233272855）

52378

3、求带权为1，2，3，4，5，6，7，8的最优二元树T，并给出T对应的二元前缀码集合。 （B={000,001,01000,01001,0101,011,10,11},W(T)=102）

7456312812578345623 4、（1）求带权为1，1，2，3，3，4，5，6，7的最优三元树；（2）求带权为1，1，2，3，3，4，5，6，7，8的最优三元树

322040128673

1043112374152735645211C(T1)=61,C(T2)=81

六、如图G

v2eafbv3cgdv5

v1v4图中的边割集有S1{a,f,d},S2{a,e,b},S3{b,c,f},

精彩文档

实用标准文案

S4{c,e,d},S5{g},S6{a,e,f,c},S7{b,d,e,f}

图中的点割集为V1{v4}

（有割点的连通图不能是哈密尔顿图。因而若是G连通图且有割点v，则Gv中至少有两个连通分支，即pGvv，与定理矛盾。） 七、例1 如图G

v1142v363795v5811v6131012v714v2

图中的一个对集为边集(5,12,3).一个最大对集为M*=(1,3,11,14),

完美对集有：(1,3,11,14),(1,3,10,12),(1,6,9,14),(1,7,8,14),(2,4,11,14),(2,4,10,12), (2,5,7,14),(1,7,10,13)

G的全体结点是一个覆盖，一个最小覆盖为K*(v5,v8,v1,v4,v6) 独立集有如I(v1,v6)，最大独立集为I*(v7,v1,v6) 边覆盖有如L(1,6,9,13,14)，最小边覆盖为L*(1,7,8,14)

**可以验证定理IK*358V,ML*448V **由于该无孤立点的图中K*M,IL*，从而不是二分图。

v4v8例 2 如右彼得森图。

红点集合为一最小点覆盖集，白点集合为最大点独立集，点覆盖数06，点独立数04；

绿边组成最小边覆盖集，这里也是一个最大匹配，边覆盖数

aejdfigbhc15，边独立数（匹配数）15

(彼得森图不是平面图，因为它的顶点数n10，边数m15，而它的每个面至少由5条边组成，由nmr2有推论m55n2158矛盾) 33例3 现有4名教师：张、王、李、赵，要求他们去教4门课程：数学、物理、电工和计算

机科学。已知张能教数学和计算机科学，王能教物理和电工，李能教数学、物理和电工，而赵只能教电工。如何安排才能使4位教师都能授课，而且每门课都有人教？共有几种方案？（画出二部图，满足相异性条件，因而存在完备匹配。 王张李赵该题匹配也是完美的，方案只有一种）

数学物理计算机电工精彩文档

实用标准文案

八、作出下列度数列的非同构图

1、度数列d为2，2，2，3，3，4，5，5的八阶13边。可作图以下两图为例：

2、度数列d为2，3，3，3，4，4，5的七阶12边。可作图以下两图为例：

3、度数列d为1，3，3，4，6，6，7的七阶无向图。可作图以下两图为例：

4、6阶2-正则图只有两种非同构情况

5、6阶3-正则图也只有两种非同构情况

精彩文档

实用标准文案

九、求最短通路的过程演示

a4372b2aw43723b2v3c332vdb22[0](3)2w(4)a[4]7323b2v[3]cd[7]2[0](3)2w[3]cd[7]2(4)a[4]7v[0](3)[3]c(3)2w(4)a[4](7)3b2v[6]d[0](3)[3]c(3)2w(4)a[4](7)3b2v[6]d[0](3)[3]c(3)(2)w[8][6]d

1、Dijkstra算法（1959年提出）是公认的好算法：第一步，给始点v1标上P标号dv1，给其它的点标上T标号dvjw1j,2jn（vi,vj没有边时wij）；第二步，在所有的T标号中取最小者，设结点vk的T标号dvk最小，则将vk的T标号改为P标号，并计算具有T标号的其它各个结点的T标号：新的dvjmin旧的dvj,dvk+wkj；第三步，若终点已具有P标号，则此标号，即为所求最短路径的权，算法终止；否则转到第二步。

2、Warshall算法：第一步，令W造

000Wwijwij；第二步，从W出发，依次构

kkn阶矩阵W1,W2,,Wn。各Wwij个的定义为：

kk1k1k1kwijminwij,wikwkj,wij是从vi到vj中间结点仅属于v1,v2,,vk的通路中

权最小的通路之权。最后得到的Wn的元素wij就是是从vi到vj的最短路径的权。

n精彩文档

实用标准文案

27824125736278241257362782412573634362178412234361782412343621784122573657361346

13u04u04234613u04u0434657363u04u041、对右图给出的附权图G，求出结点v1到其余个节点的最短路径

v2371v4852v64dv1 dv2 dv3 dv4 dv5 dv6 * * * * 3 9 dv7     17/v4 v192  3/v1 3*/v1 3*/v1 *5/v2 *10/v2 4/v2 4/v2   13/v5 v3749v5v75*/v2 9/v5 5*/v2 9/v5 4*/v2 13/v5 * * * 3*/v1 3*/v1 3*/v1 5*/v2 9*/v5 5*/v2 9*/v5 5*/v2 9*/v5 4*/v2 11/v4 4*/v2 11*/v4 15/v6 4*/v2 11*/v4 15*/v6 注：例如对v3，新的dv3min旧的dv3,dv2+w23min9,2+35，故v3的临时T标号改为5。在5的右下方记上v2，表明是因为结点v2的标号成为固定标号P而引起v3的T标号的改变。最后回溯，由第7列15/v6找到v6，再由第6列11*/v4找到v4，再由

*精彩文档

实用标准文案

第4列9*/v5找到v5，再由第5列4*/v2找到v2，…, 得到最短路径v1v2v5v4v6v7。 2、对右图所示的有向图，用Warshall算法求任意两结点之间的最短路径的权。

0WW271W429173W429196395W742841741442221248152715921124825937242594641013 32W，214734W，1125812963367W，10725476v127v2124v331v442v5v6413

4859241015261027134173

485118249515286927127351647953

47951062475146270171128注：因为所给图是强连通的，所以W中不出现。例如w52，而w529，因为

0001w52minw52,w51w12min,279，这对应通路v5v1v2，通路中间结点属于

4333minw52,w54w42v1,k1；再如w52min9,448，这对应通路v5v1v4v2，

这时通路中间结点属于v1,v2,v3,v4,k4。

十、求关键通路示例

精彩文档

实用标准文案

TE=1,TL=3u22TE=3TL=41TE=6,TL=61u1TE=0TL=01351u522TE=8=max{6+2,3+2,5+2}TL=8=TEu3u62u4TE=5,TL=5=min{8-2,6-1}

十一、作关系的哈斯图、简化关系图的简化过程 例1、设A{1,2,3,4,5,6},“|”是A上的整除关系。

136a:关系图14326第一步化简1236第二步化简4221122063

44哈斯图,|的哈斯图如右所示， 例2、设A{2,4,5,10,12,20,25},A由图看出该偏序集没有最大元和最小元，12、20、25都是极大元，

42510252和5都是极小元。考虑B{2,4,10}，则B没有最大元，有最小元2，有极大元4和10，有极小元2。在这个偏序集中：2是B的一个下界也是下确界，20是B的一个上界也是上

确界；C={4,10,25}既没有上界，也没有下界；D={2,4}的一个下界是2也是下确界，4、12和20都是D的上界，4也是D的上确界。 24,|的哈斯图如右所示， 例3、设A{1,2,3,4,5,8,12,24},A由图看出该偏序集没有最大元，最小元为1；5，24是极大元，1是极小元。

8412513,|的哈斯图如右所示， 例4、设A{2,3,4,8,9,10,11},A例4、3个偏序集的哈斯图如右所示，

8109由图看出该偏序集没有最大元和最小元；8,9,10,11是极大元，2,3,11是极小元。 41132则（1）h是极大也是最大元，a,b,c为极小元，无最小元；（2）o,p,q,r为极大元，无最大元，j为极小元，且是最小元；（3）z为极大最大元，u为极小最小元； 满足条件ex的元素有

hfgdeabcoe,f,gh,，

pqrzmnwxkvjuylubd,cf,lubp,mp,lubw,y,vz,glba,g不存在

精彩文档