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

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

2、4 ,为此图的最大度G 4, G不是完全图，也不是奇数长的基本回路，由定理可知GG4,因而 G 4。（对n阶轮图Wn, n为奇数时有四3, n为偶数时有Wn4；对n阶零图Nn,有 Nn 1；完全图Kn,有Knn ；对于二部图GV1,V2,E ,E 时即 Nn 1, E 时即 G 2;在彼得森图 G中，存在奇数长的基本回路，因而G 3,又彼得森图既不是完全图也不是长度为奇数的基本回路，且 G 3,由定理G 3,故 G 3)例2给右边三个图的顶点正常着 色，每个图至少需要几种颜色。答案：（1 ） G 2 ;（G 3； （3）G 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,RAAK7同构的无向图6 K5弱连通图、单向连通图和强连通图（考试排考或老师排课让选修的学生避免冲突的问题类似处理！）二、强连通一定单向连通，单向连通一定弱连通！弱连通图单向连通图单向连通图强连通图1、设G为无向欧拉图，求G中一条欧拉回路的Fleury算法如下：第1步，任取G中的一G3。因此贮藏这8种药品至少需要 3个房间。贮藏方式之一为 SAB, RDT, PC 。强连通图强连通图哈密顿图哈密顿图P-D, S-C ,S-D,问贮藏这8种药品

4、至少需要多少个房间？ 解以8种药品作为结点，若两种药品不能贮在同一个室 内，则它们之间有一条边，这样得右图，转化为图的正常着 色问题。（1）对各结点按度数的递减顺序排列为SRDPCTAB ;（2）对S及不与之相邻点 A, B着c1色；（3）对R及不与之又因为因S,D,P为K3子图，故着色数G 3 ,从而BJ2 J3 J41 B2 B3 B4 B5欧拉图均不是同构的有向图SC TSCT相邻点KiK2K9二：.K8、陵 K3D着C2色；（4）对P和C着C3色。故着色数G 3；欧拉图个结点Vo ,令P0 Vo ；第2步，假设P VoOMe2L ve已选好，按下面方法从E G,e2,L ,e中选e 1

5、 ： （1） e 1与3相关联，（2）除非无别的边可供选择，否则 e1不应该是Gi G e,2,L ,e的断边；第3步，当第2步不能执行时，算法停止。（有向欧拉图的欧拉回路可类似求出，可用于解决邮路问题）邮路问题用图论的概念描述如下：在一个带权图 g中，怎样找到一条回路 C,使得c包含 G中的每一条边至少一次，而且回路 C具有最小权。C分以下三种情况：（1）如果G是欧 拉图，必定有欧拉回路， C即可找到；（2）如果G是具有从vi到Vj的欧拉通路的半欧拉图，C的构造如下：找到从 vi到Vj的欧拉通路及vi到Vj的最小权通路（即最短路径）-这两条通路和并在一起就是最小权回路；（3）如果G不是半欧拉

6、图，一般说来，G中包含多条边的回路，其中夫的边数与奇数结点数目有关，若奇数结点多于2,则回路中会出现更多的重复的边。问题是怎样使重复边的权综合最小。在理论上已证明：一条包括G的所有边的回路C具有最小权当且仅当：（1,每条边最多重复一次，（2,在G的每个回路上，有重复边 的权之和小于回路权的一半。例：求右图所示的带权图中最优投递路线，邮局在D点。解 先观察奇度结点，此图中有 E,F两个。用标 号法求出其间最短路径 EGF,其权为28。然后. 、一 . 一 . . . *将最短路径上的边重复一次， 于是得欧拉图G ,求从 D 出的一条欧拉回路，如DEGFGEBACBDCFD ,其权为 281=35

7、+8+20+20+8+40+50+30+19+6+12+10+23。2、求接近最小权哈密顿回路的“最邻近”算法：设 G V,E,W 是有n个顶点的无向完 全图，（1）任取v0V作为始点，令 L为v0, k 0; （2）令w vk, xmin w vk,v v不在L中，置 vk 1 x。置 L v0v1 L vk 1,k k 1 ； （3）若k n 1 ,转（2） ； （4）置L V0V1L VkV0 ,结束。（可近似解决货郎担问题）例1用最邻近算法求下图的最短哈密尔顿回路。所得长度为14+6+5+5+7=37 ,与最短 7+8+5+10+6=36很接近了!例2求下图的最短哈密尔顿回路。三条比较

8、，最小权为 47。例3已知A,B,C,D,E,F,G7个人中，A会讲英语，B会讲英语和汉语，C会讲英语、意大利语和俄语，D会讲日语和汉语，E会讲意大利语和德语，F会讲俄语，G会讲俄语、日语和法语。能否将他们的座位 安排在圆桌旁，使得每个人都能与他身边的人交谈？（按哈密尔顿回路安排就是了 ！）例4 11个学生要共进晚餐，他们将坐成一个圆桌，计划要求每次晚餐上每个学生有完全不同的邻座，这样能攻进晚餐几天？（11 11 155条边，每条哈留尔顿回路有11条边，因而共有5条没有公 2Kii共有共边的哈密尔顿回路，可吃 5天！分别用2, 3, 4, 5与11互素，以它们为步长能找到！） 半哈密顿图与哈密

9、顿图补例：补充内容：设G是无向完全图，若对 G的每条边指定一个方向，所得的图称为竞赛图。证明：在无又向回路（或有向圈）的竞赛图D V D ,E D中，对任意u,v V D ,d u d v（用反证法，见于离散数学习题与解析胡辛启清华第 2版）可以证明：对于每个竞赛图D,至多改变一条边的方向后就可以变成哈密尔顿图。四、求最小生成树1、破圈法过程演示令E E ； （2）选取E中的一条简单回路 C,设C中权最大的边为e,令E E e；（3）重复步骤（2）,直到E V 1为止。(1)首先将边按权值由小到大排成序列S,令i1,ES1；(2)令ii 1,选取边 Si与E中的边不构成简单回路,则令E E U

10、Si ; (3)重复步骤(2),直到E V 1为止。3、Prim算法过程演示(1)从V中任意选取结点Vo,令 VVo ； (2)在V与V V之间选一条权最小的边e (Vi,Vj)，其中 Vi V ,Vj V V 并且令 EE Ue, V V UVj ； (3)重复步骤(2),直到V V为止。增加破圈法一例演示:4、求下列最小生成树的权值C(T)=1+2+3=631C=1+2+3+1=7C(T)=1+2+3+5+7=18C(T)=3+6+6+7=22C(T)=2+2+3+5+6+100=1182r2C(T)=8+9+4+7=28C(T)=1+3+3+2+1=105、在右图所示的带权图中， 共有多

11、少棵生成树，他们的权各为多少？， 其中哪些是图中的最小生成树？五、求最优二叉树对给定的实数序列W1w2Lwt,构造最优r元树的递归算法:1、求最优二元树的 Huffman算法：第一步，连接以 w1,w2为权的两片树叶，得一个分支点及其所带的权 wi w2;第二步，在 wi w2,w3,L ,wt中选出两个最小的权，连接它们对应的结点（不一定都是树叶），又得分支结点及其所带的权；重复第二步，直到形成t 1个分支点，t片树叶为止。_t 12、求取优r r 3兀树的Huffman算法：（1）右为整数，则求法与求取优一兀树的r 1t 1 一Huffman算法类似，只是每次取 r个最小的权；（2）若 不

12、为整数，得余数 s 1,r 1）,r 1将s 1个较小的权对应的树叶为兄弟放在最长的路径上，然后算法同（1）。1、找出叶的权分别为2, 3, 5, 7, 11, 13, 17, 19,23, 29, 31, 37, 41的最优叶加权二叉树，并求其加权路径的长度。789)v V2、求带权为2, 3, 5, 7, 8的最优二元树T,并给出T对应的二元前缀码集合。(B=00,010,011,10,11,W(T尸 2532332728 55)3、求带权为1, 2, 3, 4, 5, 6, 7, 8的最优二元树T,并给出T对应的二元前缀码集合。(B=000,001,01000,01001,0101,01

13、1,10,11,W(T)=102 )7的最优三元树;4、(1)求带权为 1, 1, 2, 3, 3, 4, 5, 6,3, 4, 5, 6, 7, 8的最优三元树(2)求带权为1, 1, 2, 3,C(T1)=61,C(T2)=81六、如图GV1V4图中的边割集有 S a, f,d, S a,e,b, S3 b,c, f,S4 c,e,d, S5 g, S6 a,e, f,c, S b,d,e, f图中的点割集为Vi V4(有割点的连通图不能是哈密尔顿图。因而若是G连通图且有割点v,则G v中至少有两个连通分支，即 p G v v ,与定理矛盾。)七、例1如图Gv413L* ,从而不是二分图。

14、15 5 8矛盾)n 10,边数 m 15,一 .5m r 2有推论m - n3例3现有4名教师：张、王、李、赵，要求他们去教4门课程：数学、物理、电工和计算机科学。已知张能教数学和计算机科学,王能教物理和电工，李能教数学、物理和电工，而图中的一个对集为边集(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,Vi,V4,V6)*,、独立

15、集有如I(Vi,V6),最大独立集为I(V7,Vi,V6)边覆盖有如L (1,6,9,13,14),最小边覆盖为L* (1,7,8,14)可以验证定理 I | |K*| 358V,M|L4 4 8 V 一 、 . . 一 、 、 *由于该无孤立点的图中K* M , I例2如右彼得森图。红点集合为一最小点覆盖集，白点集合为最大点独立集，点覆盖数06 ,点独立数 04;绿边组成最小边覆盖集，这里也是一个最大匹配，边覆盖数15,边独立数(匹配数) 15(彼得森图不是平面图，因为它的顶点数赵只能教电工。如何安排才能使 4位教师都能授课，而且 课都有人教？共有几种方案？(画出二部图，满足相异性 因而存在

16、完备匹配。该题匹配也是完美的，方案只有一种)而它的每个面至少由 5条边组成，由n八、作出下列度数列的非同构图1、度数列d为2, 2, 2, 3, 3, 4, 5, 5的八阶13边。可作图以下两图为例:2、度数列d为2, 3, 3, 3, 4, 4, 5的七阶12边。可作图以下两图为例:4、6阶2-正则图只有两种非同构情况5、6阶3-正则图也只有两种非同构情况九、求最短通路的过程演示1、Dijkstra算法（1959年提出）是公认的好算法：第一步，给始点v1标上P标号d5,给其它的点标上 T标号d vjw1j,2 j n （M,Vj没有边时Wij）；第二步，在所有的T标号中取最小者，设结点 vk

17、的T标号d vk最小，则将vk的T标号改为P标号，并计算具有T标号的其它各个结点的 T标号：新的d vjmin旧的d vj ,d vk +wkj ；第三步，若终点已具有 P标号，则此标号，即为所求最短路径的权，算法终止；否则转到第 二步。2、Warshall算法：第一步，令 W 0 Wwijwij0 ；第二步，从 W 0出发，依次构12nkk造 n阶矩阵W ,W ,L ,W 。各Wwij个的定义为：kk 1 k 1 k 1 kwijminwij, wikwkj, wij是从vi到Vj中间结点仅属于v1,v2,L,vk的通路中权最小的通路之权。最后得到的W n的元素w就是是从vi到vj的最短路径

18、的权。1、对右图给出的附权图G,求出结点M到其余个节点的最短路径d v1d v2d V3d v4d V5d V6d v7*39*一* .3 /V1,* .5 1V210/V24/v2*3 /V1* 一5 /V29/V54/v213/V5*4*,3 /v1_* ，5 1V29/V5*4 /v213/V5*一* .3 1V_* .5 /V2*9 /V5* .4 /v211/v417/v4*,3 /v1_* ，5 1V2*9 /V5*4 /v211* /v415/v6*一* .3 1V_* .5 /V2*9 /V5* .4 /v211* /v4* 一15 /v6注：例如对v3,新的dv3min旧的d

19、v3,dv2+w23min9,2+35,故v3的临时T标号改为5。在5的右下方记上v2，表明是因为结点v2的标号成为固定标号 P而引起v3*的T标3的改变。取后回溯，由第7歹U15 / V6找到v6，再由第6列11*/v4找到v4，再由第4列9 /V5找到v5,再由第5列4 /V2找到v2,，得到最短路径v1v2v5v4v6v7。2、对右图所示的有向图，用 Warshall算法求任意两结 点之间的最短路径的权。111011141013111110127 12105 10注：因为所给图是强连通的，所以W 6中不出现。例如w521w529 ,因为, 一, 4.33v1 , k 1 ；再如 w52min w52 , w54 min w50,w50w10min ,2 79 ,这对应通路v5v1v2,通路中间结点属于3w42min 9,4 48 ,这对应通路 v5v1v4v2 ，这时通路中间结点属于v1,