电子科技大学2017年图论期末试卷

电子科技大学研究生试题《图论及其应用》(参考答案)考试时间：120分钟一．填空题(每题3分，共18分)1．4个顶点的不同构的简单图共有__11___个；2．设无向图G 中有12条边，已知G 中3度顶点有6个，其余顶点的度数均小于3。

则G 中顶点数至少有__9___个；3．设n 阶无向图是由k(k ?2)棵树构成的森林，则图G 的边数m= _n-k____;4．下图G 是否是平面图？答__是___; 是否可1-因子分解？答__是_.5．下图G 的点色数=)(G χ______, 边色数=')(G χ__5____。

图G二．单项选择(每题3分，共21分)1．下面给出的序列中，是某简单图的度序列的是( A )(A) (11123); (B) (233445); (C) (23445); (D) (1333).2．已知图G 如图所示，则它的同构图是（ D ）3． 下列图中，是欧拉图的是（ D ）4． 下列图中，不是哈密尔顿图的是（B ）5． 下列图中，是可平面图的图的是（B ）AC DA B CD6．下列图中，不是偶图的是（ B ）7．下列图中，存在完美匹配的图是（B ）三．作图(6分)1．画出一个有欧拉闭迹和哈密尔顿圈的图；2．画出一个有欧拉闭迹但没有哈密尔顿圈的图；3．画出一个没有欧拉闭迹但有哈密尔顿圈的图；解： 四．(10分)求下图的最小生成树，并求其最小生成树的权值之和。

解：由克鲁斯克尔算法的其一最小生成树如下图：权和为：20.五．(8分)求下图G 的色多项式P k (G).解：用公式(G P k -G 的色多项式：)3)(3)()(45-++=k k k G P k 。

六．(10分) 22，n 3个顶点的度数为3，…，n k 个顶点的度数为k ，而其余顶点的度数为1，求1度顶点的个数。

解：设该树有n 1个1度顶点，树的边数为m.一方面：2m=n 1+2n 2+…+kn k另一方面：m= n 1+n 2+…+n k -1 v v 13图G由上面两式可得：n 1=n 2+2n 3+…+(k -1)n k七．证明：(8分) 设G 是具有二分类(X,Y)的偶图，证明(1)G 不含奇圈；（2）若|X |≠|Y |，则G 是非哈密尔顿图。

电⼦科技⼤学《图论及其应⽤》复习总结--第四章欧拉图与哈密尔顿图第四章欧拉图与哈密尔顿图(⼀)、欧拉图及其性质(1)、问题背景---欧拉与哥尼斯堡七桥问题问题：对于图G，它在什么条件下满⾜从某点出发，经过每条边⼀次且仅⼀次，可以回到出发点？注：⼀笔画----中国古⽼的民间游戏（存在欧拉迹）要求：对于⼀个图G, 笔不离纸, ⼀笔画成.拓展：三笔画：在原图上添加三笔，可使其变为欧拉图。

定义1 对于连通图G，如果G中存在经过每条边的闭迹，则称G为欧拉图，简称G为E图。

欧拉闭迹⼜称为欧拉环游，或欧拉回路。

定理1 下列陈述对于⾮平凡连通图G是等价的：(1) G是欧拉图；(2) G的顶点度数为偶数；(3) G的边集合能划分为圈。

推论1 连通图G是欧拉图当且仅当G的顶点度数为偶。

推论2 连通⾮欧拉图G存在欧拉迹当且仅当G中只有两个顶点度数为奇数。

证明：若G和H是欧拉图，则G×H是欧拉图。

若G是⾮平凡的欧拉图，则G的每个块也是欧拉图。

(⼆)、Fleury算法(欧拉图中求出⼀条具体欧拉环游的⽅法)⽅法是尽可能避割边⾏⾛(三)、中国邮路问题（最优欧拉环游，管梅⾕）定理2 若W是包含图G的每条边⾄少⼀次的闭途径，则W具有最⼩权值当且仅当下列两个条件被满⾜：(1) G的每条边在W中最多重复⼀次；(2) 对于G的每个圈上的边来说，在W中重复的边的总权值不超过该圈⾮重复边总权值。

(四)、哈密尔顿图的概念定义1 ：如果经过图G的每个顶点恰好⼀次后能够回到出发点，称这样的图为哈密尔顿图，简称H图。

所经过的闭途径是G的⼀个⽣成圈，称为G的哈密尔顿圈。

定义2: 如果存在经过G的每个顶点恰好⼀次的路，称该路为G的哈密尔顿路，简称H路。

(五)、哈密尔顿图性质与判定1、性质定理【必要条件】；定理1 (必要条件) 若G为H图，则对V(G)的任⼀⾮空顶点⼦集S，有：w(G−S)≤|S|注：不等式为G是H图的必要条件，即不等式不满⾜时，可断定对应图是⾮H、图。

1电子科技大学研究生试卷（考试时间： 至 ，共__2_小时）课程名称 图论及其应用 教师 学时 60 学分 教学方式 讲授 考核日期_2013__年_6__月__20__日 成绩 考核方式： （学生填写）一．填空题(每空2分，共20分)1． n 阶k 正则图G 的边数m =_____。

2．4个顶点的不同构单图的个数为________。

3．完全偶图,r s K (,2r s ≥且为偶数)，则在其欧拉环游中共含____条边。

4．高为h 的完全2元树至少有_______片树叶。

5. G 由3个连通分支124,,K K K 组成的平面图，则其共有_______个面。

6. 设图G 与5K 同胚，则至少从G 中删掉_______条边，才可能使其成为可平面图。

7. 设G 为偶图，其最小点覆盖数为α，则其最大匹配包含的边数为________。

8. 完全图6K 能分解为________个边不重合的一因子之并。

9. 奇圈的边色数为______。

10. 彼得森图的点色数为_______。

二．单项选择(每题3分，共15分) 1．下面说法错误的是( )学 号 姓 名 学 院…………………… 密……………封……………线……………以……………内……………答…… ………题……………无……………效……………………2(A) 图G 中的一个点独立集，在其补图中的点导出子图必为一个完全子图；(B) 若图G 连通，则其补图必连通； (C) 存在5阶的自补图； (D) 4阶图的补图全是可平面图. 2．下列说法错误的是（ ） (A) 非平凡树是偶图；(B) 超立方体图(n 方体,1n ≥)是偶图； (C) 存在完美匹配的圈是偶图； (D) 偶图至少包含一条边。

3.下面说法正确的是( )(A) 2连通图一定没有割点（假定可以有自环）； (B) 没有割点的图一定没有割边；(C) 如果3阶及其以上的图G 是块，则G 中无环，且任意两点均位于同一圈上；(D) 有环的图一定不是块。

习题四：3. (1)画一个有Euler闭迹和Hamilton圈的图；(2) 画一个有Euler闭迹但没有Hamilton圈的图；(3) 画一个有Hamilton圈但没有Euler闭迹的图；(4) 画一个即没有Hamilton圈也没有Euler闭迹的图;解：找到的图如下：(1)一个有Euler闭迹和Hamilton圈的图；(2)—个有Euler闭迹但没有Hamilton圈的图;⑶一个有Hamilton圈但没有Euler闭迹的图;(4)一个即没有Hamilton圈也没有Euler闭迹的图.4. 设n阶无向简单图G有m条边，证明：若2 ) * ',则G是血加此"图。

证明：G是H图。

若不然，因为G是无向简单图，则n芝3,由定理％若G是n芝3的非单图，则G、一 ...C …度弱丁某个阵".于是有：- - 1 2 E(G)| E(C m,n ) - m (n 2m)(n m 1) m(m 1)1.这与条件矛盾！所以G 是H 图若G 有个奇点，则存在k 条边不重的迹Q1・Q 矿心，使得 E(G) = E(Q 】)U E(Q J U E(Q 3) U …U E(Q k ) 证明：不失一般性，只就 G 是连通图进行证明。

设 G=(n, m)是连通图。

令 虬 V 2,…,v,V k+1,…,v 是G 的所有奇度点。

在V i与v i+k 问连新边e i 得图G* (1三隹k). 则G*是欧拉图，因此，由Fleury 算法得欧拉环游C 在C 中删去e i (1m M k).得 k 条边不重的迹Qi (1 MiMk):E(G) E(Q1^E(Q2^^E(Qk)10. 证明：若：(1) G 不是二连通图，或者(2) G 是具有二分类|(X,Y)的偶图，这里|X” |Y|则G 是非Hamilton 图。

证明：(1) G|不是二连通图，则G 不连通或者存在割点v ,俨任-v) >2 ,由丁课本 上的相关定理：若G 是Hamilton 图，则对丁*勇)的任意非空顶点集S,有： w(G- S) <|S|,则该定理的逆否命题也成立，所以可以得出：若不是二连通图， 则G 是非Hamilton 图(2)因为是具有二分类(XI)的偶图，乂因为|X|丰1丫1,在这里假设|X| < |Y|,则有 w(G-X) = |Y|>|X|，也就是说：对北(G)|的非空顶点集S,有：w(G-S)>||S|成 立，则可以得出则G 是非Hamilton 图。

习题四：3.（1）画一个有Euler 闭迹和Hamilton圈的图；（2）画一个有Euler闭迹但没有Hamilton圈的图；（3）画一个有Hamilton圈但没有Euler闭迹的图；（4）画一个即没有Hamilton圈也没有Euler闭迹的图；解：找到的图如下：(1)一个有Euler 闭迹和Hamilton圈的图；(2)一个有Euler闭迹但没有Hamilton圈的图；(3) 一个有Hamilton圈但没有Euler闭迹的图;(4)一个即没有Hamilton圈也没有Euler闭迹的图.)+2,则G是Hamilton图。

4.设n阶无向简单图G有m条边，证明:若m≥(n−12证明: G是H图。

若不然，因为G是无向简单图，则n≥3,由定理1：若G是n≥3的非单图，则G 度弱于某个C m,n.于是有：2,1()()(2)(1)(1)2111(1)(2)(1)(21)221 1.2m n E G E C m n m n m m m n m m m n m n ⎡⎤≤=+---+-⎣⎦-⎛⎫=+------- ⎪⎝⎭-⎛⎫≤+ ⎪⎝⎭这与条件矛盾！所以G 是H 图。

8.证明：若G 有2k ≥0个奇点，则存在k 条边不重的迹Q 1,Q 2…Q k ,使得E (G )=E (Q 1)∪E (Q 2)∪E (Q 3)∪⋯∪E(Q k ).证明：不失一般性，只就G 是连通图进行证明。

设G=(n, m)是连通图。

令v l ，v 2，…,v k ,v k+1,…,v 2k 是G 的所有奇度点。

在v i 与v i+k 间连新边e i 得图G*（1≦i ≦k).则G*是欧拉图，因此，由Fleury 算法得欧拉环游C.在C 中删去e i （1≦i ≦k).得k 条边不重的迹Q i （1≦i ≦k):12()()()()k E G E Q E Q E Q =U UL U10.证明：若：（1）G 不是二连通图，或者（2）G 是具有二分类(X,Y )的偶图，这里|X |≠|Y |,则G 是非Hamilton 图。

12017年图论课程练习题一．填空题1.图1中顶点a 到顶点b 的距离d (a ,b )= 。

ab9 图112.已知图G 的邻接矩阵0110110100110100010110010A=，则G 中长度为2的途径总条数为 。

3.图2中最小生成树T 的权值W (T )= 。

4.图3的最优欧拉环游的权值为 。

12 图 22图35.树叶带权分别为1,2,4,5,6,8的最优二元树权值为 。

二．单项选择1．关于图的度序列，下列说法正确的是( )(A) 对任意一个非负整数序列来说，它都是某图的度序列；(B) 若非负整数序列12(,,,)n d d d π= 满足1ni i d =∑为偶数，则它一定是图序列；(C) 若图G 度弱于图H ，则图G 的边数小于等于图H 的边数；(D) 如果图G 的顶点总度数大于或等于图H 的顶点总度数，则图G 度优 于图H 。

2．关于图的割点与割边，下列说法正确的是（ ） (A) 有割边的图一定有割点； (B) 有割点的图一定有割边； (C) 有割边的简单图一定有割点； (D) 割边不在图的任一圈中。

3.设()k G ，()G λ，()G δ分别表示图G 的点连通度，边连通度和最小度。

下面说法错误的是( )3(A) 存在图G ，使得()k G =()G δ=()G λ； (B) 存在图G ，使得()()()k G G G λδ<<；(C) 设G 是n 阶简单图，若()2n G δ≥，则G 连通，且()()G G λδ=；(D) 图G 是k 连通的，则G 的连通度为k 。

4.关于哈密尔顿图，下列命题错误的是( ) (A) 彼得森图是非哈密尔顿图；(B) 若图G 的闭包是哈密尔顿图，则其闭包一定是完全图； (C) 若图G 的阶数至少为3且闭包是完全图，则图G 是哈密尔顿图； (D) 设G 是三阶以上简单图，若G 中任意两个不邻接点u 与v ，满足()()d u d v n +≥，则G 是哈密尔顿图。

图论第二次作业一、第四章4.3（1）画一个有Euler 闭迹和Hamilton 圈的图； （2）画一个有Euler 闭迹但没有Hamilton 圈的图； （3）画一个有Hamilton 圈但没有Euler 闭迹的图； （4）画一个既没有Euler 闭迹也没有Hamilton 圈的图； 解：（1）一个有Euler 闭迹和Hamilton 圈的图形如下：（2）一个有Euler 闭迹但没有Hamilton 圈的图形如下：（3）一个有Hamilton 圈但没有Euler 闭迹的图形如下：（4）一个既没有Euler 闭迹也没有Hamilton 圈的图形如下：4.7证明：若G 没有奇点，则存在边不重的圈C 1,C 1,....,C m ,使得E(G)=E(C 1) E(C 2) ..... E(C m )。

证明：将G 中孤立点除去后的图记为G 1,则G 1也没有奇点，且δ(G 1)≥2，则G 1含圈C 1，在去掉G 1-E(C 1)的孤立点后，得图G 2，显然G 2仍无奇度点，且(G 2)≥2，从而G 2含圈C 2，如此重复下去，直到圈C m ，且G m -E(C m )全为孤立点为止，于是得到E(G) E(C 1) E(C 2) ... E(C m )。

4.10证明：若（1）G 不是二连通图，或者（2）G 是具有二分类(X,Y)的偶图，这里|X|≠|Y|， 则G 是非Hamilton 图。

证明：（1）因为G 不是二连通图，则G 不连通或者存在割点V ，有w(GV)2，由相关定理得：若G 是Hamilton 图，则对于V(G)的任意非空顶点集S ，有：w(GS)S ，则该定理得逆否命题也成立，所以可得：若G 不是二连通图，则G 是非Hamilton 图。

（2）因为G 是具有二分类(X,Y)的偶图，又因为|X|≠|Y|，在这里假设|X|≠|Y|，则有w(G-X)=Y>X ，也就是说：对于V(G)的非空顶点集S ，有：w(G-S)>S 成立，则可以得出G 是非Hamilton 图。

习题四：3.（1）画一个有Euler 闭迹和Hamilton圈的图；（2）画一个有Euler闭迹但没有Hamilton圈的图；（3）画一个有Hamilton圈但没有Euler闭迹的图；（4）画一个即没有Hamilton圈也没有Euler闭迹的图；解：找到的图如下：(1)一个有Euler 闭迹和Hamilton圈的图；(2)一个有Euler闭迹但没有Hamilton圈的图；(3) 一个有Hamilton圈但没有Euler闭迹的图;(4)一个即没有Hamilton圈也没有Euler闭迹的图.)+2,则G是Hamilton图。

4.设n阶无向简单图G有m条边，证明:若m≥(n−12证明: G是H图。

若不然，因为G是无向简单图，则n≥3,由定理1：若G是n≥3的非单图，则G 度弱于某个C m,n.于是有：2,1()()(2)(1)(1)2111(1)(2)(1)(21)221 1.2m n E G E C m n m n m m m n m m m n m n ⎡⎤≤=+---+-⎣⎦-⎛⎫=+------- ⎪⎝⎭-⎛⎫≤+ ⎪⎝⎭这与条件矛盾！所以G 是H 图。

8.证明：若G 有2k ≥0个奇点，则存在k 条边不重的迹Q 1,Q 2…Q k ,使得E (G )=E (Q 1)∪E (Q 2)∪E (Q 3)∪⋯∪E(Q k ).证明：不失一般性，只就G 是连通图进行证明。

设G=(n, m)是连通图。

令v l ，v 2，…,v k ,v k+1,…,v 2k 是G 的所有奇度点。

在v i 与v i+k 间连新边e i 得图G*（1≦i ≦k).则G*是欧拉图，因此，由Fleury 算法得欧拉环游C.在C 中删去e i （1≦i ≦k).得k 条边不重的迹Q i （1≦i ≦k):12()()()()k E G E Q E Q E Q =U UL U10.证明：若：（1）G 不是二连通图，或者（2）G 是具有二分类(X,Y )的偶图，这里|X |≠|Y |,则G 是非Hamilton 图。

电⼦科技⼤学《图论及其应⽤》复习总结--第⼀章图的基本概念⼀、重要概念图、简单图、图的同构、度序列与图序列、偶图、补图与⾃补图、两个图的联图、两个图的积图1.1 图⼀个图G定义为⼀个有序对(V, E)，记为G = (V, E)，其中（1）V是⼀个有限⾮空集合，称为顶点集或边集，其元素称为顶点或点；（2）E是由V中的点组成的⽆序点对构成的集合，称为边集，其元素称为边，且同⼀点对在E中可出现多次。

注：图G的顶点数（或阶数）和边数可分别⽤符号n(G) 和m(G)表⽰。

连接两个相同顶点的边的条数，叫做边的重数。

重数⼤于1的边称为重边。

端点重合为⼀点的边称为环。

1.2 简单图⽆环⽆重边的图称为简单图。

（除此之外全部都是复合图）注： 1.顶点集和边集都有限的图称为有限图。

只有⼀个顶点⽽⽆边的图称为平凡图。

其他所有的图都称为⾮平凡图。

边集为空的图称为空图。

2.n阶图：顶点数为n的图，称为n阶图。

3.(n, m) 图：顶点数为n的图，边数为m的图称为(n, m) 图1.3 邻接与关联：顶点u与v相邻接：顶点u与v间有边相连接(u adj v)；其中u与v称为该边的两个端点。

注：1.规定⼀个顶点与⾃⾝是邻接的。

2.顶点u与边e相关联：顶点u是边e的端点。

3.边e1与边e2相邻接：边e1与边e2有公共端点。

1.4 图的同构设有两个图G1=(V1,E1)和G2=(V2,E2),若在其顶点集合间存在双射，使得边之间存在如下关系：u1,v1∈V1,u2,v2∈ V2 ，设u1↔u2，v1↔v2,; u1v1∈E1 当且仅当u2v2∈E2,且u1v1与u2v2的重数相同。

称G1与G2同构，记为：G1≌G2注：1、图同构的两个必要条件： (1) 顶点数相同；(2) 边数相同。

2、⾃⼰空间的理解：通过空间的旋转折叠可以进⾏形态转换1.5 完全图、偶图1、在图论中，完全图是⼀个简单图，且任意⼀个顶点都与其它每个顶点有且只有⼀条边相连接。

**学院2013—2014学年第二学期期末考试 数学与应用数学专业2013级《图论》试卷A（本试卷满分100分，考试时间110分钟）一、填空题 （每小题2分，共20分） 1．5阶完全图G 的边的个数是___________．2．如果图G 的每个顶点的度数都相同，则称图G 为________图． 3．当且仅当无向连通图G 的顶点个数比边的个数多1时，图 G 是___． 4．无向图G 为欧拉图当且仅当G 连通，并且所有顶点的度都是 ． 5．(p ,q ) 图G 的向量空间的维数是_________．6．图G 的任意一个顶点的关联集都是其余各顶点关联集的____． 7．5阶完全图的边连通度是 ．8．已知M 是图G 的一个 ，若从G 中一个顶点到另一个顶点存在一条道路，此路径由属于M 和不属于M 的边交替出现组成的，则称此路径为M -交错道路．9．图G 是2-色的当且仅当G 是 ． 10．极大平面图所有面的次数均为 ． 二、判断题（每小题2分，共20分）1．图的所有顶点的度数之和是边数的2倍．2．连通图的一个生成树是边数最少的连通生成子图． 3．若一个图是欧拉图，那它也一定是哈密顿图．4．图的秩等于图的完全关联矩阵的秩，也等于其关联矩阵的秩． 5．r 一定是r —正则图的一个特征值． 6．图的点连通度小于等于图的边连通度．7．若一个图G 存在完美匹配，则该匹配必定是最大匹配． 8．图G 的一个M —可增广道路未必是一个M —交错道路． 9．图的边着色问题可以转化成图的点着色问题．10．设G 为p 阶、q 条边、f 个面的连通平面图，则 p -q +f =2．专业：__________ 班级：______ 学号：_______________________ 姓名：_____________________——————————————密——————————————封————————————————线———————————专业：________ 班级：___________ 学号：_______________________ 姓名：_____________________ ——————————————密——————————————封————————————————线———————————三、解答题（每小题5分，共30分） 1．试判断下列两个图是否同构．2．写出下图G 的一个生成树T 并写出图G 关于T 的基本圈组．3．求下图的完全关联矩阵并以v 2为参考点写出关联矩阵和一个可逆大子阵．4．简述图的点连通度、边连通度、最小顶点的度数三者之间的关系，并举例说明．5．下面的图中加粗的边构成最大匹配吗？如果不是请说明理由．v 143 v e 2 e 34 e AB CDGF4v5v 6v 1v2v 3v 15 u u43 u u26 u u6．试写出下图的一个着色方案，并回答该图的色数．四、应用题（每小题5分，共10分）1．下图是一个公园的平面图，能不能使游人走遍每一条路不重复？入口和出口又应设在哪儿？2．试建立下列问题的数学模型：有两组化学药品X 和Y ，每组各三类，设{}123,,x x x 和{}123,,y y y ，已知不同组的化学药品不能放在一起，否则会发生爆炸．现在将这些物品存放在三个仓库1，2，3中，但由于物品的特性及仓库自身的物理条件（如有无空调、通风条件等），1x 和1y 只允许放在1号和2号仓f 1 f 2 m 1f 3 f 4f 5m 2 m 3 m 4 m 5v 2v 3v 4v 1v 5库内，2x 和2y 只允许放在2号和3号仓库内，3x 和3y 只允许放在1号和3号仓库内，问：满足要求的存放方案是否存在？若存在，如何存放？ 五、证明题（每小题10分，共20分）1．设T 是一个无向（p ,q ）图，证明T 是树则T 无圈且q =p -1．2．设G 为p 阶连通平面图, 有q 条边, 且每个面的次数不小于l (l ³3), 证明 ()≤lq p -2l -2．**学院2013—2014学年第二学期期末考试 数学与应用数学专业2013级《图论》参考答案与评分标准A命题教师：***二、填空题 （每小题2分，共20分）参考答案：1．120；2．正则图；3．树；4．偶数；5．q ;6．环和；7．4；8．匹配；9．二部图；10．3 评分标准：本部分每小题2分．凡与答案一致或意义相同的得2分，不一致（含空白）的不得分．三、判断题（每小题2分，共20分）参考答案：1-5.√√×√√ 6-10.√√×√√ 评分标准：本部分每小题2分．凡与答案一致的得2分，不一致（含未做判断）的不得分．三、解答题（每小题5分，共30分）参考答案：1.解：建立一一映射,1,2,3,4,5,6i i v u i =a ，可知两图同构． ……（5分）2.解：因为图的生成树即其连通无圈的生成子图，因此，去掉图的一些边使其保持连通无圈即得其生成树．下图是其中的一种做法． …………（2分）关于这棵树的基本圈有6个：AEG ，ABG ，EFG ，BCE ，DEF ，CDF ．（5分）3.解： ………………（3分）其中一个可逆的大子阵100011001⎛⎫⎪ ⎪ ⎪⎝⎭123e e e …………………………………………（5分） 4.解：图的点连通度、边连通度、最小顶点的度数三者之间的关系为k (G )≤l (G )≤d (G )． …………………………………………（3分）下图是无向连通图，点连通度k (G )=1，边连通度l(G )=2，最小度d(G )=3，此图满足k (G )≤l (G )≤d (G )． …………………………………………（5分）100110110100110⎛⎫⎛⎫ ⎪ ⎪ ⎪ ⎪ ⎪⎪ ⎪⎝⎭⎝⎭2完全关联矩阵关联矩阵(v 为参考点)1001111000→0110100110EAB CDGF5.解：不是最大匹配，因为该图中存在M-可增广道路． ………………（5分） 6.该图是3色的，颜色1：v 1，v 5，颜色2：v 2，v 4，颜色3：v 3． ………（5分） 本部分每小题5分，由于某些题的结果不唯一，因此要求只要运用理论正确，结果与答案等价，即得满分；如果有些偏差，酌情扣分；如果关键部分错误，该得分点不得分．四、应用题（每小题5分，共10分）参考答案：1.这个问题可以归结为一笔画问题，一个连通图存在欧拉圈当且仅当图的顶点的度数是偶数．H 点和B 点是奇点，其余都是偶点，所以入口和出口应设在H 点和B 点． ………………（5分）2.解：以药品为点，两药品不能放在一起则连边，则得到一个二部图，然后再对图中每个点x ，指定一个集合()L x ，用以表示允许存放的仓库和集合，即令()(){}111,2L x L y ==，()(){}222,3L x L y ==，()(){}331,3L x L y ==，如下图所示，于是问题转化为对3,3K 的点着色，但要求对每个点x 的着色，应选用各自的中所罗列的“颜色”，如下图所示：f 1f 2m 1 f 3f 4f 5m 2 m 3 m 4 m 5{}11,2x{}22,3x{}31,3x实际上，本问题的着色不存在． ………………（5分） 评分标准：本部分每小题5分，考生每解出一个步骤，得相应的分数．由于某一步单纯计算错误而导致其后数据错误，但方法正确的，酌情给分． 五、证明题（每小题10分，共20分）参考答案：1.证明:由树的定义可知T 无圈．下证q =p -1．对p 进行归纳证明． 当p=1时，q=0，显然q =p -1．假设p=k 时结论成立，现证明p=k+1时结论也成立． ………… （2分）由于树是连通而无圈的，所以至少有一个度数为1的顶点v ，在T 中删去v 及其关联边，便得到k 个顶点的连通无圈图． ………… （4分）由归纳假设它有k-1条边．再将顶点v 及其关联边加回得到原图T ，所以T 中含有k+1个顶点和k 条边，故结论q =p -1成立．所以树是无圈且q =p -1的图．即q =k +1时结论成立． ……………… （10分）2.证明：由于在计算面数之和时，每个边被计算了两次，因此各面次数之和等于边数的2倍，再由欧拉公式得： ……………… （5分） 2q ³ lf = l (2+q-p )()1⎛⎫≥⇒≥⇒≤ ⎪⎝⎭2q 2l 2+q -p -q 2-p q p -2l l l -2 …… （10分）评分标准：本部分每小题10分，根据参考答案的答题要点给分。

习题四：3.（1）画一个有Euler 闭迹和Hamilton圈的图；（2）画一个有Euler 闭迹但没有Hamilton圈的图；（3）画一个有Hamilton圈但没有Euler闭迹的图；（4）画一个即没有Hamilton圈也没有Euler闭迹的图；解：找到的图如下：(1)一个有Euler 闭迹和Hamilton圈的图；(2)一个有Euler 闭迹但没有Hamilton圈的图；(3) 一个有Hamilton圈但没有Euler闭迹的图;(4)一个即没有Hamilton圈也没有Euler闭迹的图.4.设n阶无向简单图G有m条边，证明:若,则是图。

证明: G是H图。

若不然，因为G是无向简单图，则,由定理1：若G是的非单图，则G 度弱于某个.于是有：2,1()()(2)(1)(1)2111(1)(2)(1)(21)221 1.2m n E G E C m n m n m m m n m m m n m n ⎡⎤≤=+---+-⎣⎦-⎛⎫=+------- ⎪⎝⎭-⎛⎫≤+ ⎪⎝⎭这与条件矛盾！所以G 是H 图。

8.证明：若G 有个奇点，则存在条边不重的迹,使得.证明：不失一般性，只就G 是连通图进行证明。

设G=(n, m)是连通图。

令v l ，v 2，…,v k ,v k+1,…,v 2k 是G 的所有奇度点。

在v i 与v i+k 间连新边e i 得图G*（1≦i ≦k).则G*是欧拉图，因此，由Fleury 算法得欧拉环游C.在C 中删去e i （1≦i ≦k).得k 条边不重的迹Q i （1≦i ≦k):12()()()()k E G E Q E Q E Q =U UL U10.证明：若：（1）不是二连通图，或者 （2）是具有二分类的偶图，这里,则是非Hamilton 图。

证明：（1）不是二连通图，则不连通或者存在割点,有,由于课本上的相关定理：若是Hamilton 图，则对于的任意非空顶点集，有：,则该定理的逆否命题也成立，所以可以得出：若不是二连通图，则是非Hamilton 图 (2)因为是具有二分类的偶图，又因为，在这里假设,则有,也就是说：对于的非空顶点集，有：成立，则可以得出则是非Hamilton 图。

习题四：3. (1)画一个有Euler闭迹和Hamilton圈的图；(2)画一个有Euler闭迹但没有Hamilton圈的图；(3)画一个有Hamilton圈但没有Euler闭迹的图；(4)画一个即没有Hamilton圈也没有Euler闭迹的图; 解：找到的图如下：(1) 一个有Euler闭迹和Hamilton圈的图；(2) 一个有Euler闭迹但没有Hamilton圈的图;⑶一个有Hamilton圈但没有Euler闭迹的图;(4)一个即没有Hamilton圈也没有Euler闭迹的图.证明：G是H图。

若不然，因为G是无向简单图，则n >3,由定理1:若G是n > 3的非单图，贝U G 度弱于某个C m,n.于是有:E(G)|E(C m,n) 1 2 -m2(n 2m)(n m 1) m(m 1)4•设n阶无向简单图G有m条边，证明若m > (n-2)+ 2,则G是Hamilton 图n 111 - (m 1)(m2) (m 1)(n 2m 1)2n 11.2这与条件矛盾！所以G是H图。

8•证明：若G有2k > 0个奇点，则存在k条边不重的迹Q I,Q2-Q k,使得E(G)= E(Q) U E©) U E©) U? U E(Q)证明：不失一般性，只就G是连通图进行证明。

设G=(n, m)是连通图。

令v i,V2,…,v,v k+i,…邯是G的所有奇度点。

在V i与v i+k间连新边e i得图G* (1三i三k). 则G*是欧拉图，因此，由Fleury算法得欧拉环游C在C中删去e (1三i三k).得k条边不重的迹Q i (1三i三k):E(G) E(QJU EQ)UL UE(QQ10. 证明：若：(1)G不是二连通图，或者(2)G是具有二分类(X,Y)的偶图，这里|X|工|Y|,则G是非Hamilton图。

证明：(1) G不是二连通图，则G不连通或者存在割点v,有w(G - v) >2,由于课本上的相关定理：若G是Hamilton图，则对于v (G)的任意非空顶点集S,有:w(G -S) < IS,则该定理的逆否命题也成立，所以可以得出：若G不是二连通图，则G是非Hamilton 图⑵因为G是具有二分类(X,Y)的偶图，又因为|X|工|Y|，在这里假设凶< |Y|,则有w(G- X) = |Y| > |X|,也就是说：对于v (G)的非空顶点集S，有: w(G - S) > |S|成立，则可以得出则G是非Hamilton图。