课前练习-图论

一、填空题1、对下列图，试填下表（是⨯⨯类图的打〝√ 〞，否则打〝⨯〞）。

① ② ③2、若图G=<V , E>中具有一条汉密尔顿回路，则对于结点集V 的每个非空子集S ，在 G 中删除S 中的所有结点得到的连通分支数为W ，则S 中结点数|S|与W 满 足的关系式为 。

3、设有向图D 为欧拉图，则图D 中每个结点的入度 ．4、数组{1，2，3，4，4}是一个能构成无向简单图的度数序列，此命题的真值是 .5、“3,3K 是欧拉图也是哈密顿图”这句话是_______。

(填对或错)6、极大可平面图的每一个面的次数都是_________．7、5阶完全图的边连通度是．8、图G是2-色的当且仅当G是．二、选择题1、下列无向图可能不是偶图的是( )(A) 非平凡的树(B)无奇圈的非平凡图(C) n(1)n 方体图(D) 平面图2、关于平面图，下列说法错误的是( )(A) 简单连通平面图中至少有一个度数不超过5的顶点；(B)极大外平面图的内部面是三角形，外部面也是三角形；(C) 存在一种方法，总可以把平面图的任意一个内部面转化为外部面；(D) 平面图的对偶图也是平面图。

3、已知图G的邻接矩阵为，则G有（）．A．5点，8边B．6点，7边C．6点，8边D．5点，7边4、设图G＝<V, E>，则下列结论成立的是( )．A．deg(V)=2∣E∣B．deg(V)=∣E∣C．EvVv2)deg(=∑∈D．EvVv=∑∈)deg(5、设完全图K n有n个结点(n≥2)，m条边，当（）时，K n中存在欧拉回路．A．m为奇数B．n为偶数C．n为奇数D．m为偶数6、设G是连通平面图，有v个结点，e条边，r个面，则r= ( )．A．e－v＋2 B．v＋e－2 C．e－v－2 D．e＋v＋27、下列定义正确的是( )．A含平行边或环的图称为多重B不含平行边或环的图称为简单图C含平行边和环的图称为多重D不含平行边和环的图称为简单图8、以下结论正确是( )．A仅有一个孤立结点构成的图是零图B无向完全图Kn每个结点的度数是nC有n(n>1)个孤立结点构成的图是平凡图D图中的基本回路都是简单回路9、下列数组能构成简单图的是( )．(A) (0,1,2,3) (B) (2,3,3,3) (C) (3,3,3,3) (D) (4,2,3,3)10、n阶无向完全图Kn中的边数为（）．(A) 2)1(+nn(B) 2)1(-nn(C) n (D)n(n+1)11、以下命题正确的是( )．(A) n(n≥1)阶完全图Kn都是欧拉图(B) n(n≥1)阶完全图Kn都是哈密顿图(C) 连通且满足m=n－1的图<V,E>(∣V∣=n,∣E∣=m)是树(D) n(n≥5)阶完全图Kn都是平面图12、下列结论不正确是( )．(A) 无向连通图G是欧拉图的充分必要条件是G不含奇数度结点(B) 无向连通图G有欧拉路的充分必要条件是G最多有两个奇数度结点(C) 有向连通图D是欧拉图的充分必要条件是D的每个结点的入度等于出度(D) 有向连通图D有有向欧拉路的充分必要条件是除两个结点外，每个结点的入度等于出度13、无向完全图K4是（）．（A）欧拉图（B）哈密顿图（C）树（D）平面图14、在如下各图中（）欧拉图。

《离散数学》第四部分---图论练习题答案一、选择或填空1、设G是一个哈密尔顿图，则G一定是( )。

(1) 欧拉图(2) 树(3) 平面图(4) 连通图答：(4)2、下面给出的集合中，哪一个是前缀码？( )(1) {0，10，110，101111} (2) {01，001，000，1}(3) {b，c，aa，ab，aba} (4) {1，11，101，001，0011}答：（2）3、一个图的哈密尔顿路是一条通过图中( )的路。

答：所有结点一次且恰好一次4、在有向图中，结点v的出度deg+(v)表示( )，入度deg-(v)表示( )。

答：以v为起点的边的条数，以v为终点的边的条数5、设G是一棵树，则G 的生成树有( )棵。

(1) 0 (2) 1 (3) 2 (4) 不能确定答：16、n阶无向完全图K n 的边数是( )，每个结点的度数是( )。

答：2)1(nn, n-17、一棵无向树的顶点数n与边数m关系是( )。

8、一个图的欧拉回路是一条通过图中( )的回路。

答：所有边一次且恰好一次9、有n个结点的树，其结点度数之和是( )。

答：2n-210、下面给出的集合中，哪一个不是前缀码( )。

(1) {a，ab，110，a1b11} (2) {01，001，000，1}(3) {1，2，00，01，0210} (4) {12，11，101，002，0011}答：(1)11、n个结点的有向完全图边数是( )，每个结点的度数是( )。

答：n(n-1),2n-212、一个无向图有生成树的充分必要条件是( )。

答：它是连通图13、设G是一棵树，n,m分别表示顶点数和边数，则(1) n=m (2) m=n+1 (3) n=m+1 (4) 不能确定。

答：（3）14、设T=〈V,E〉是一棵树，若|V|>1，则T中至少存在( )片树叶。

答：215、任何连通无向图G至少有( )棵生成树，当且仅当G 是( )，G的生成树只有一棵。

《图论及其应用》习题课教材目录第一章图的基本概念1.1 图和简单图1.2 子图与图的运算1.3 路与图的连通性1.4 最短路及其算法1.5 图的代数表示及其特征1.6 极图1.7 交图与团图习题1第二章树2.1 树的概念与性质2.2 树的中心与形心2.3 生成树2.4 最小生成树习题2第三章图的连通度3.1 割边、割点和块3.2 连通度3.3 应用3.4 图的宽距离和宽直径习题3第四章欧拉图与哈密尔顿图4.1 欧拉图4.2 高效率计算机鼓轮的设计4.3 中国邮路问题4.4 哈密尔顿图4.5 度极大非哈密尔顿图4.6 旅行售货员问题4.7 超哈密尔顿图4.8 E图和H图的联系4.9 无限图中的欧拉,哈密尔顿问题习题4第五章匹配与因子分解5.1 匹配5.2 偶图的匹配与覆盖5.3 Tutte定理与完美匹配5.4 因子分解5.5 最优匹配与匈牙利算法5.6 匹配在矩阵理论中的应用习题5第六章平面图6.1 平面图6.2 一些特殊平面图及平面图的对偶图6.3 平面图的判定及涉及平面性的不变量6.4 平面性算法习题6第七章图的着色7.1 图的边着色7.2 顶点着色7.3 与色数有关的几类图7.4 完美图7.5 着色的计数，色多项式习题27.6 List着色7.7 全着色7.8 着色的应用习题7第八章Ramsey定理8.1 独立集和覆盖8.2 Ramsey定理8.3 广义Ramsey数8.4 应用习题8习题 11. 证明在n阶连通图中（1）至少有n-1条边。

（2）如果边数大于n-1，则至少有一条闭通道。

（3）如恰有n-1条边，则至少有一个奇度点。

证明(1) 若对∀v∈V(G),有d(v)≥2,则：2m=∑d(v)≥2n ⇒ m≥n>n-1,矛盾！若G中有1度顶点，对顶点数n作数学归纳。

当n=2时，G显然至少有一条边，结论成立。

设当n=k时，结论成立，当n=k+1时，设d(v)=1，则G-v是k阶连通图，因此至少有k-1条边，所以G 至少有k条边。

《图论》练习题(2014)1、利用Dijkstra 算法求下图中顶点0v 到其它各顶点的距离，并写出到顶点8v 的最短路。

2、1、列出色数3为的三个图： 。

2、p 阶完全图的色数为： 。

3、p 阶树的邻接多项式为： 。

4、p 阶完全图的邻接多项式为： 。

5、如下图所示的图的邻接矩阵为 ，关联矩阵为 。

6、度序列为(2,2,2,2,2,2)的简单图是 。

7、是否存在度序列为(2,2,3,4,5,6)，(1,2,3,4,4,5)的简单图？若存在，给出一个图；若不存在，请说明理由。

8、画出如下图的所有生成子图。

9、设图G 如下图所示，求该图的生成树个数)(G 。

v 2v 6v 4v 610、已知图G （V 、E ），画出G －V 5，G －v 3v 4，G[{v 2，v 3，v 5}]，G[{v 3v 4，v 4，v 6，v 7v 8}]G ：11、已知图G 的邻接矩阵⎪⎪⎪⎪⎪⎭⎫ ⎝⎛=2111102112011111A ，画出G ，并求出度序列。

12、证明：偶图G 的任意子图H 仍为偶图。

13、证明：设图G （V 、E ）的度序列为（p d d d ,,,21 ），边数为q ，则q i d pi 21==∑14、证明：在任何图中，奇顶点个数为偶数。

15、证明：整数序列（6，6，5，4，3，3，1）不可能为一个简单图的图序列。

16、证明顶点度数均为2的简单连通图是圈。

17、证明非平凡树T 的边连通度为'()1T κ=。

18、n 阶完全图n K 的连通度为()1T n κ=-。

19、设G 是一个p 阶图，且()()21,-≥∈∀p v d G V v ，则G 连通图。

20、若图G 是 不连通的，则其补图G C 是连通的。

21、证明：设G 是由1G 和2G 两个连通分支组成的图，则);();();(21x G P x G P x G P =。

v 1v 2v 3v 4v 5v 6v 8v 722、证明：设G 是由1G 和2G 两个连通分支组成的图，则)}(),(max{)(21G G G χχχ=。

一、问题重述邮路是邮政运输网络的基本组成单元，它是指利用各种运输工具按固定班期、规定路线运输邮件，并与沿线有交接频次的邮政局、所交换邮件总包所行驶的路线。

邮路的结构形式有三种：辐射形、环形和混合形。

辐射形邮路可以缩短运递时间，加快邮运速度。

但它的联系点较少，需用的运输工具较多，所耗费用较大。

环形是不走重复路线，联系点较多，运输工具的利用率高，运费也较省。

但是邮件送到最后几个交接点的时间较长。

混合型二者兼有。

某地区的邮政局分为地市局、县局和支局三级机构。

该地区的邮政运输网络由区级邮政运输网和县级邮政运输网构成。

区级邮政运输网由从地市局出发并最终返回地市局的区级邮车所行驶的全部邮路构成，县级邮政运输网由从县局出发并最终返回县局的县级邮车所行驶的全部邮路构成。

时限与成本是邮政运输问题的两个重要指标。

时限是指邮电部规定的邮件、报刊处理、传递的最大时间限制，时限关系到邮政通信质量的好坏；成本影响着企业的经营。

为使邮政企业实现低成本运营和较高的服务质量，我们需要对该地区的邮政运输网络进行重构，确定合适的邮路规划方案并进行邮车的合理调度。

为了满足邮政的时限要求，必须尽可能地保证各县局、支局在营业时间内收寄的多数邮件能当天运送回地市局，以及每天到达地市局的多数邮件能当天运送到目的地县局、支局。

该地区从地市局到县局每天两班车，从县局到支局每天仅有一班车。

该地区的邮政运输流程及时限规定如下：Step1:区级第一班次邮车从地市局D出发将邮件运送到各县局X i和沿途支局，并将各县局X i和沿途支局收寄的邮件运送回地市局D；区级第一班次邮车出发时间必须在06:00之后，返回地市局D时间必须在11:00之前。

Step2:县局X i将当天区级第一班次邮车及前一天的区级第二班次邮车所送达的本县邮件进行集中处理，按寄达支局装上相应的县级邮车；县局X i对邮件的集中处理时间为1小时（包括邮件的卸装、分拣封发等处理时间）Step3:各县级邮车将邮件运送到其负责的支局并将这些支局收寄的邮件运送回县局X i；Step4: 区级第二班次邮车从地市局D出发将邮件运送到各县局X i和沿途支局，并将各县局X i收寄的邮件（包括当日各县级邮车运回县局X i的邮件）和沿途支局收寄的邮件运送回地市局D；请注意区级第二班次邮车在县局X i卸装完邮件后的出发时间必须在县局X i的全部县级邮车返回县局并集中处理1小时以后，最终返回地市局D的时间必须在18:00之前。

1 设图G有12条边，G中有1度结点2个，2度结点2个，4度结点3个，其余结点度数不超过3．求G中至少有多少个结点？2 设有向简单图G的度数序列为(2,2,3,3）, 入度序列为(0,0,2,3),求G得出度序列 .3 设D是n阶有向简单完全图,则图D的边数为 .4设G是n阶无向简单完全图K n，则图G的边数为 .5 仅有一个孤立结点组成的图称为( )(A)零图(B)平凡图(C)补图(D)子图6设n阶图G中有m条边，每个结点的度数不是k的是k+1，若G中有N k个k度顶点，N k+1个k+1度顶点，则N k = .7设图G如右图.已知路径(1) P1=(v1e5 v5e7 v2e2 v3 )(2) P2=(v5e6 v2e2 v3e3 v4e8 v2e7 v5)(3) P3=(v2e7 v5e6 v2)(4) P4=(v1e1 v2e2 v3e3 v4e8 v2e6 v5)判断路径类型，并求其长度.81）判断下图G1中的路径类型, 并求其长度. P1=(v3e5v4e7v1e4v3e3v2e1v1e4v3)P2=(v3e3v2e2v2e1v1e4v3)P3=(v3e3v2e1v1e4v3).2）判断下图G2中的路径类型, 并求其长度. P1=(v1e1v2e6v5e7v3e2v2e6v5e8v4)P2=(v1e5v5e7v3e2v2e6v5e8v4)P3=(v1e1v2e6v5e7v3e3v4).v1e1e5v2e65e7e4 e2e8v3 4e3v e v1 设图G 有12条边，G 中有1度结点2个，2度结点2个，4度结点3个，其余结点度数不超过3．求G 中至少有多少个结点？ 至少9个2 设有向简单图G 的度数序列为(2,2,3,3）, 入度序列为(0,0,2,3),求G 得出度序列 （2,2,5,6） .3 设D 是n 阶有向简单完全图,则图D 的边数为 )1(−n n .4 设G 是n 阶无向简单完全图K n ，则图G 的边数为 m =n (n -1)/2 .5 仅有一个孤立结点组成的图称为( B ) (A) 零图 (B)平凡图 (C)补图 (D)子图6设n 阶图G 中有m 条边，每个结点的度数不是k 的是k+1，若G 中有N k 个k 度顶点，N k+1个k+1度顶点，则N k = N k =(k+1)n-2m . 7设图G 如右图.已知路径 (1) P 1=(v 1e 5 v 5e 7 v 2e 2 v 3 ) (2) P 2=(v 5e 6 v 2e 2 v 3e 3 v 4e 8 v 2e 7 v 5) (3) P 3=(v 2e 7 v 5e 6 v 2)(4) P 4=(v 1e 1 v 2e 2 v 3e 3 v 4e 8 v 2e 6 v 5)判断路径类型，并求其长度. (1) 初级通路；3 (2) 简单回路；5 (3) 初级回路；2 (4) 简单通路. 5 81）判断下图G1中的路径类型, 并求其长度. P 1=(v 3e 5v 4e 7v 1e 4v 3e 3v 2e 1v 1e 4v 3) P 2=(v 3e 3v 2e 2v 2e 1v 1e 4v 3) P 3=(v 3e 3v 2e 1v 1e 4v 3).2）判断下图G2中的路径类型, 并求其长度. P 1=(v 1e 1v 2e 6v 5e 7v 3e 2v 2e 6v 5e 8v 4) P 2=(v 1e 5v 5e 7v 3e 2v 2e 6v 5e 8v 4) P 3=(v 1e 1v 2e 6v 5e 7v 3e 3v 4).解：在图G 1中，v 3e 5v 4e 7v 1e 4v 3e 3v 2e 1v 1e 4v 3是一条长度为6的回路，但既不是简单回路，也不是初级回路； v 3e 3v 2e 2v 2e 1v 1e 4v 3是一条长度为4的简单回路，但不是初级回路； v 3e 3v 2e 1v 1e 4v 3是一条长度为3的初级回路。

课前练习一、填空题1、图G 是简单图当且仅当 。

2、简单图G 是二部图当且仅当 。

3、若简单图G 满足(G)δ≥3，则G 中存在长度至少为 的圈。

4、连通图G 具有欧拉通路，而无欧拉回路的充要条件为 。

5、一颗树有两个2度分支点，一个3度分支点，三个4度分支点，则该树有 片树叶。

6、设T 为高为k 的二叉树，则T 最多有 个顶点。

7、设图G 是具有6条边、4个顶点的平面图,则图G 的面数为 。

8、一个图为非平面图当且仅当 。

9、S V ⊂，S 是图G 的极大独立集，则()V G S -是图G 的 。

10、带权为1，3，5，7，8，11，13的最优二叉树T 的权W(T)= 。

二、解答题1、求下图G 1的色多项式，并指出其色数、点连通度和边连通度。

图G 12、（1）证明自补图的阶数n 4k =或者n 4k 1=+，k 为某个自然数。

（2）找出所有4阶的自补图。

3、（1）证明：设G 是有v 个顶点ε条边，且G 是自对偶平面图，则2v 2ε=-。

（2）已知一颗无向树T 有三个3度结点，一个二度结点，其余都是1度结点。

①T 有几个1度结点？②试画出两棵满足上述度数要求的非同构的无向树。

4、通过布尔变量的运算，求下图3的全部极小支配集。

V 16 图3图G 25、用破圈法求下图G 3中的一颗最小生成树,写出具体过程，并计算生成树的权。

图G 36、设简单图,, |V|=n, |E|=m,G V E =<> 若有212n m C -≥+，则G 是哈密尔顿图。

7、证明：5K 不是平面图.8、证明：若,(,1)m n K m n ≥是哈密顿图，则必有.m n = 9、若,m n K 是树，求,m n 应满足的条件.132411253e 6e 1e 2e 3e 4e 5e 7e 8e 9。

图论练习题一、基本题1、设G是由5个顶点构成的完全图，则从G中删去（A）边可以得到树。

A．6 B．5 C．8 D．42、下面哪几种图不一定是树（A）。

A．无回路的连通图B．有n个结点，n-1条边的连通图C．对每对结点间都有通路的图D．连通但删去任意一条边则不连通的图3、5阶无向完全图的边数为（B）。

A．5 B．10 C．15 D．204、设图G有n个结点，m条边，且G中每个结点的度数不是k，就是k+1，则G中度数为k的节点数是（）A．n/2 B．n(n+1) C．nk-2m D．n(k+1)-2m 5、设G=<V，E>为有向图，V={a,b,c,d,e,f}，E={<a,b>,<b,c>,<a,d>,<d,e>,<f,e>}是（B）。

A．强连通图B．单向连通图C．弱连通图D．不连通图6、在有n个结点的连通图中，其边数（B）A．最多有n-1条B．至少有n-1条C．最多有n条D．至少有n条7、设无向简单图的顶点个数为n，则该图最多有（C）条边。

A．n-1 B．n(n-1)/2 C． n(n+1)/2 D．n28、要连通具有n个顶点的有向图，至少需要（A ）条边。

A．n-l B．n C．n+l D．2n9、n个结点的完全有向图含有边的数目（B）。

A．n*n Ｂ．n（n＋１） C．n／2 D．n*（n－l）10、在一个无向图中，所有顶点的度数之和等于所有边数（B）倍。

A．1/2 B．2 C．1 D．411、在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（C）倍。

A．1/2 B．2 C．1 D．412、连通图G是一棵树，当且仅当G中（B）A．有些边不是割边B．所有边都是割边C．无割边集D．每条边都不是割边13、4个顶点的完全图G，其生成树个数是（）。

A．4 B．8 C．16 D．64二、应用题题1、判断下图是否能一笔画出，并说明理由。

第一章习题1．画出具有4个顶点的所有无向图(同构的只算一个)。

2．画出具有3个顶点的所有有向图(同构的只算一个)。

3．画出具有4个、6个、8个顶点的三次图。

4．某次宴会上，许多人互相握手。

证明：握过奇数次手的人数为偶数(注意，0是偶数)。

5．证明：哥尼斯堡七桥问题无解。

6．设u与v是图G的两个不同顶点。

假设u与v间有两条不同的通道(迹)，那么G中是否有回路？7．证明：一个连通的(p，q)图中q ≥p-1。

8．设G是一个(p，q)图，δ(G)≥[p/2]，试证G是连通的。

9．证明：在一个连通图中，两条最长的路有一个公共的顶点。

10．在一个有n个人的宴会上，每个人至少有m个朋友(2≤m≤n)。

试证：有不少于m+1个人，使得他们按某种方法坐在一张圆桌旁，每人的左、右均是他的朋友。

11．一个图G是连通的，当且仅当将V划分成两个非空子集V1和V2时，G总有一条联结V1的一个顶点与V2的一个顶点的边。

12．设G是图。

证明：假设δ(G)≥ 2，那么G包含长至少是δ(G)+1的回路。

13．设G是一个(p，q)图，证明：(a)q≥p，那么G中有回路；(b)假设q≥p+4，那么G包含两个边不重的回路。

14．证明：假设图G不是连通图，那么G c 是连通图。

15．设G是个(p，q)图，试证：(a)δ(G)·δ(G C)≤[(p-1)/2]([(p+1)/2]+1)，假设p≡0，1，2(mod 4)(b) δ(G)·δ(G C)≤[(p-3)/2]·[(p+1)/2]，假设p≡3(mod 4)16．证明：每一个自补图有4n或4n+1个顶点。

17．构造一个有2n个顶点而没有三角形的三次图，其中n≥3。

18.给出一个10个顶点的非哈密顿图的例子，使得每一对不邻接的顶点u和v，均有degu+degv≥919．试求Kp中不同的哈密顿回路的个数。

20．试证：图四中的图不是哈密顿图。

21．完全偶图Km，n为哈密顿图的充分必要条件是什么？22．菱形12面体的外表上有无哈密顿回路？23．设G是一个p(p≥3)个顶点的图。

作业解答练习题2 利用matlab编程FFD算法完成下题：设有6种物品，它们的体积分别为：60、45、35、20、20和20单位体积，箱子的容积为100个单位体积。

解答一：function [num,s] = BinPackingFFD(w,capacity)%一维装箱问题的FFD（降序首次适应）算法求解:先将物体按长度从大到小排序,%然后按FF算法对物体装箱%输入参数w为物品体积，capacity为箱子容量%输出参数num为所用箱子个数，s为元胞数组，表示装箱方案，s{i}为第i个箱子所装%物品体积数组%例w = [60,45,35,20,20,20]; capacity = 100;% num=3,s={[1,3],[2,4,5],6};w = sort(w,'descend');n = length(w);s = cell(1,n);bin = capacity * ones(1,n);num = 1;for i = 1:nfor j = 1:num + 1if w(i) < bin(j)bin(j) = bin(j) - w(i);s{j} = [s{j},i];if j == num + 1num = num + 1;endbreak;endendends = s(1:num);解答二：clear;clc;V=100;v=[60 45 35 20 20 20];n=length(v);v=fliplr(sort(v));box_count=1;x=zeros(n,n);V_Left=100;for i=1:nif v(i)>=max(V_Left)box_count=box_count+1;x(i,box_count)=1;V_Left=[V_Left V-v(i)];elsej=1;while(v(i)>V_Left(j))j=j+1;endx(i,j)=1;V_Left(j)=V_Left(j)-v(i);endtemp=find(x(i,:)==1);fprintf('第%d个物品放在第%d个容器\n',i,temp) endoutput:第1个物品放在第1个容器第2个物品放在第2个容器第3个物品放在第1个容器第4个物品放在第2个容器第5个物品放在第2个容器第6个物品放在第3个容器解答三：function box_count=FFD(x)%降序首次适应算法v=100;x=fliplr(sort(x));%v=input('请输入箱子的容积:');n=length(x);I=ones(n);E=zeros(1,n);box=v*I;box_count=0;for i=1:nj=1;while(j<=box_count)if x(i)>box(j)j=j+1;continue;elsebox(j)=box(j)-x(i);E(i)=j;break;endendif j>box_countbox_count=box_count+1;box(box_count)=box(box_count)-x(i);E(i)=j;endenddisp(E);在命令窗口输入：>> x=[60,45,35,20,20,20];>> FFD(x)1 2 1 2 2 3ans =3练习题5 “超市大赢家”提供了50种商品作为奖品供中奖顾客选择,车的容量为1000dm3, 奖品i占用的空间为w i dm3,价值为v i元, 具体的数据如下:v i= { 220, 208, 198, 192, 180, 180, 165, 162, 160, 158,155, 130, 125, 122, 120, 118, 115, 110, 105, 101, 100, 100, 98,96, 95, 90, 88, 82, 80, 77, 75, 73, 72, 70, 69, 66, 65, 63, 60, 58,56, 50, 30, 20, 15, 10, 8, 5, 3, 1}w i = {80, 82, 85, 70, 72, 70, 66, 50, 55, 25, 50, 55, 40, 48,50, 32, 22, 60, 30, 32, 40, 38, 35, 32, 25, 28, 30, 22, 50, 30, 45,30, 60, 50, 20, 65, 20, 25, 30, 10, 20, 25, 15, 10, 10, 10, 4, 4, 2,1}。

(二）图论复习题一、选择题1．设图G ＝〈V ， E 〉，v ∈V ，则下列结论成立的是 ( C ） ． A ．deg(v )=2∣E ∣ B ． deg(v )=∣E ∣ C ．E v Vv 2)deg(=∑∈ [PPT 23] D ．Ev Vv =∑∈)deg(定理1 图G=（V ，E ）中，所有点的次之和为边数的两倍 2．设无向图G 的邻接矩阵为⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡0101010010000011100100110则G 的边数为( B ）．A ．6B ．5C ．4D ．33、 设完全图K n 有n 个结点（n ≥2）,m 条边，当（ C )时,K n 中存在欧拉回路．A ．m 为奇数B ．n 为偶数C ．n 为奇数D ．m 为偶数解释：K n 每个结点的度都为n －1，所以若存在欧拉回路则n －1必为偶数。

n 必为奇数。

4．欧拉回路是（ B ）A 。

路径 B. 简单回路[PPT 40] C. 既是基本回路也是简单回路 D.既非基本回路也非简单回路5．哈密尔顿回路是（ C ) A. 路径 B. 简单回路 C 。

既是基本回路也是简单回路 D.既非基本回路也非简单回路［PPT 40］：哈密尔顿回路要求走遍所有的点,即是基本回路的点不重复，也可以是简单回路的边不重复。

6．设G 是简单有向图，可达矩阵P(G)刻划下列关系中的是（ C ） A 、点与边 B 、边与点 C 、点与点 D 、边与边7．下列哪一种图不一定是树（C )。

A 。

无简单回路的连通图B 。

有n 个顶点n-1条边的连通图C 。

每对顶点间都有通路的图D 。

连通但删去一条边便不连通的图8．在有n 个结点的连通图中,其边数(B ）A 。

最多有n-1条B 。

至少有n-1条 C.最多有n 条 D 。

至少有n 条9．下列图为树的是(C ）。

A 、>><><><=<},,,,,{},,,,{1d c b a a a d c b a GB 、>><><><=<},,,,,{},,,,{2d c d b b a d c b a GC 、>><><><=<},,,,,{},,,,{3a c d a b a d c b a GD 、>><><><=<},,,,,{},,,,{4d d c a b a d c b a G 10、下面的图7—22是（C ）.A.完全图；B 。