离散数学及其应用图论部分课后习题答案-推荐下载
电子科技大学研究生试题《图论及其应用》(参考答案)
电子科技大学研究生试题 《图论及其应用》(参考答案) 考试时间：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 ） A C D A B C D
6．下列图中，不是偶图的是（ 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 1 3 图G
图论张先迪李正良课后习题答案
习题一 作者---寒江独钓 1.证明：在n 阶连通图中 (1) 至少有n-1条边； (2) 如果边数大于n-1，则至少有一条闭迹； (3) 如果恰有n-1条边，则至少有一个奇度点。 证明: (1) 若G 中没有1度顶点，由握手定理： ()2()21v V G m d v n m n m n ∈= ≥?≥?>-∑ 若G 中有1度顶点u ，对G 的顶点数作数学归纳。 当n=2时，结论显然；设结论对n=k 时成立。 当n=k+1时，考虑G-u,它仍然为连通图，所以，边数≥k-1.于是G 的边数≥k. (2) 考虑G 中途径： 121:n n W v v v v -→→→→L 若W 是路，则长为n-1;但由于G 的边数大于n-1,因此，存在v i 与v j ,它们相异，但邻接。于是： 1i i j i v v v v +→→→→L 为G 中一闭途径，于是 也就存在闭迹。 (3) 若不然，G 中顶点度数至少为2，于是由握手定理： ()2()21v V G m d v n m n m n ∈= ≥?≥?>-∑ 这与G 中恰有n-1条边矛盾！ 2.(1)2n ?12n 2?12n ?1 (2)2n?2?1 (3) 2n?2 。 证明 :u 1的两个邻接点与v 1的两个邻接点状况不同。所以， 两图不同构。 4.证明下面两图同构。 u 1 v 1
证明:作映射f : v i ? u i (i=1,2….10) 容易证明，对?v i v j ∈E ((a)),有f (v i v j,),=,u i,u j,∈,E,((b)) (1≤ i ≤ 10, 1≤j ≤ 10 ) 由图的同构定义知，图(a)与(b)是同构的。 5.指出4个顶点的非同构的所有简单图。 分析：四个顶点的简单图最少边数为0，最多边数为6，所以 可按边数进行枚举。 (a) v 2 v 3 u 4 u (b)
图论及其应用第三章答案电子科大
习题三： ● 证明：e 是连通图G 的割边当且仅当V(G)可划分为两个子集V1和V2，使对任意u ∈V 1及v ∈V 2, G 中的路（u ，v ）必含e . 证明：充分性: e 是G 的割边，故G ?e 至少含有两个连通分支，设V 1是其中一个连通分支的顶点集，V 2是其余分支的顶点集，对12,u V v V ?∈?∈，因为G 中的u,v 不连通，而在G 中u 与v 连 通，所以e 在每一条(u,v)路上，G 中的(u,v)必含e 。 必要性：取12,u V v V ∈∈，由假设G 中所有(u,v)路均含有边e ，从而在G ?e 中不存在从u 与到v 的 路，这表明G 不连通，所以e 是割边。 ● 3.设G 是阶大于2的连通图，证明下列命题等价： （1） G 是块 （2） G 无环且任意一个点和任意一条边都位于同一个圈上； （3） G 无环且任意三个不同点都位于同一条路上。 （1）→（2）： G 是块，任取G 的一点u ，一边e ，在e 边插入一点v ，使得e 成为两条边，由此得到新图G 1，显然G 1的是阶数大于3的块，由定理，G 中的u,v 位于同一个圈上，于是G 1中u 与边e 都位于同一个圈上。 （2）→（3）： G 无环，且任意一点和任意一条边都位于同一个圈上，任取G 的点u ，边e ，若u 在e 上，则三个不同点位于同一个闭路，即位于同一条路，如u 不在e 上，由定理，e 的两点在同一个闭路上，在e 边插入一个点v ，由此得到新图G 1，显然G 1的是阶数大于3的块，则两条边的三个不同点在同一条路上。 （3）→（1）： G 连通，若G 不是块，则G 中存在着割点u ，划分为不同的子集块V 1, V 2, V 1, V 2无环， 12,x v y v ∈∈，点u 在每一条(x,y)的路上，则与已知矛盾，G 是块。 ● 7.证明：若v 是简单图G 的一个割点，则v 不是补图G ?的割点。 证明：v 是单图G 的割点，则G ?v 有两个连通分支。现任取x,y ∈V(G ?v), 如果x,y 不在G ?v 的同一分支中，令u 是与x,y 处于不同分支的点，那么，x,与y 在G ?v 的补图中连通。若x,y 在G ?v 的同一分支中，则它们在G ?v 的补图中邻接。所以，若v 是G 的割点，则v 不是补图的割点。 ● 12.对图3——20给出的图G1和G2，求其连通度和边连通度，给出相应的最小点割和最小边割。 解：()12G κ= 最小点割 {6,8} 1()2G λ= 最小边割{（6,5），（8,5）} ()25G κ= 最小点割{6,7,8,9,10} 2()5G λ= 最小边割{（2,7）…（1,6）} ● 13.设H 是连通图G 的子图，举例说明：有可能k(H)> k(G). 解： 通常k (H ) 图论及其应用答案电子科 大 This model paper was revised by the Standardization Office on December 10, 2020 习题三： 证明：e是连通图G 的割边当且仅当V(G)可划分为两个子集V1和V2，使对任意u ∈V 1及v ∈V 2, G 中的路（u，v）必含e . 证明：充分性: e是G的割边，故G ?e至少含有两个连通分支，设V 1是其中一个连通分支的顶点集，V 2是其余分支的顶点集，对12,u V v V ?∈?∈，因为G中的u ,v不连通， 而在G中u与v连通，所以e在每一条(u ,v )路上，G中的(u ,v )必含e。 必要性：取12,u V v V ∈∈，由假设G中所有(u ,v )路均含有边e，从而在G ?e中不存在从 u与到v的路，这表明G不连通，所以e 是割边。 3.设G 是阶大于2的连通图，证明下列命题等价： （1） G 是块 （2） G 无环且任意一个点和任意一条边都位于同一个圈上； （3） G 无环且任意三个不同点都位于同一条路上。 （1）→（2）： G是块，任取G的一点u，一边e，在e边插入一点v，使得e成为两条边，由此得到新图G 1，显然G 1的是阶数大于3的块，由定理，G中的u,v 位于同一个圈上，于是G 1中u 与边e都位于同一个圈上。 （2）→（3）： G无环，且任意一点和任意一条边都位于同一个圈上，任取G的点u ，边e ，若u在e 上，则三个不同点位于同一个闭路，即位于同一条路，如u不在e上，由定理，e的两点在同一个闭路上，在e边插入一个点v ，由此得到新图G 1，显然G 1的是阶数大于3的块，则两条边的三个不同点在同一条路上。 （3）→（1）： G连通，若G不是块，则G中存在着割点u，划分为不同的子集块V 1, V 2, V 1, V 2无环，12,x v y v ∈∈，点u在每一条(x ,y )的路上，则与已知矛盾，G是块。 7.证明：若v 是简单图G 的一个割点，则v 不是补图G ?的割点。 证明：v是单图G的割点，则G ?v有两个连通分支。现任取x ,y ∈V (G ?v ), 如果x ,y 不在G ?v的同一分支中，令u是与x ,y处于不同分支的点，那么，x ,与y在G ?v的补图中连通。若x ,y在G ?v的同一分支中，则它们在G ?v的补图中邻接。所以，若v是G 的割点，则v不是补图的割点。 12.对图3——20给出的图G1和G2，求其连通度和边连通度，给出相应的最小点割和最小边割。 解：()12G κ= 最小点割 {6,8} 1()2G λ= 最小边割{（6,5），（8,5）} 一、填空 20% （每小题2分） 1、 P ：你努力，Q ：你失败。“除非你努力，否则你将失败”的翻译为 ；“虽然你努力了，但还是失败了”的翻译为 。 2、论域D={1，2}，指定谓词P 则公式),(x y yP x ??真值为 。 2、 设S={a 1 ，a 2 ，…，a 8}，B i 是S 的子集，则由B 31所表达的子集是 。 3、 设A={2，3，4，5，6}上的二元关系}|,{是质数x y x y x R ∨<><=，则R= （列举法）。 R 的关系矩阵M R = 。 5、设A={1，2，3}，则A 上既不是对称的又不是反对称的关系R= ； A 上既是对称的又是反对称的关系R= 。 6、设代数系统，其中A={a ，b ，c}, 则幺元是 ；是否有幂等 性 ；是否有对称性 。 7、4阶群必是 群或 群。 8、下面偏序格是分配格的是 。 9、n 个结点的无向完全图K n 的边数为 ，欧拉图的充要条件是 。 10、公式R Q P Q P P ?∧∨?∧∧?∨)(())(( 的根树表示为 。 二、选择 20% （每小题2分） 1、在下述公式中是重言式为（ ） A ．)()(Q P Q P ∨→∧； B ．))()(()(P Q Q P Q P →∧→??； C ．Q Q P ∧→?)(； D ．)(Q P P ∨→ 。 2、命题公式 )()(P Q Q P ∨?→→? 中极小项的个数为（ ），成真赋值的个数为（ ）。 A ．0； B ．1； C ．2； D ．3 。 3、设}}2,1{},1{,{Φ=S ，则 S 2 有（ ）个元素。 A ．3； B ．6； C ．7； D ．8 。 4、 设} 3 ,2 ,1 {=S ，定义S S ?上的等价关系 },,,, | ,,,{c b d a S S d c S S b a d c b a R +=+?>∈∈<><><<=则由 R 产 生的S S ?上一个划分共有（ ）个分块。 A ．4； B ．5； C ．6； D ．9 。 5、设} 3 ,2 ,1 {=S ，S 上关系R 的关系图为 电子科技大学研究生试卷 （考试时间： 至 ，共_____小时） 课程名称 图论及其应用 教师 学时 60 学分 教学方式 讲授 考核日期_2007__年___月____日 成绩 考核方式： （学生填写） 一．填空题(每题2分，共12分) 1．简单图G=(n,m)中所有不同的生成子图(包括G 和空图)的个数是___2m __个； 2．设无向图G=(n,m)中各顶点度数均为3，且2n=m+3,则n=_ 6__; m=_9__； 3．一棵树有i n 个度数为i 的结点，i=2,3,…,k,则它有2+(i ?2)∑n i i 个度数为1的结点； 4．下边赋权图中，最小生成树的权值之和为__20___; 5、某年级学生共选修9门课。期末考试时，必须提前将这9门课先考完，每天每人只在下午考一门课，则至少需要___9__天才能考完这9门课。 二．单项选择(每题2分，共10分) 1．下面给出的序列中，不是某简单图的度序列的是( D ) (A) (11123); (B) (22222); (C) (3333); (D) (1333). 2． 下列图中，是欧拉图的是（ D ） 学 号 姓 学 …………………… 密……………封…………… 线……………以……………内……………答…… ………题… …………无……………效…………………… v 5 v v 6A B 3．下列图中，不是哈密尔顿图的是（B） A B C D 4．下列图中，是可平面图的图的是（B） A B C D 5．下列图中，不是偶图的是（B） C A B D 三、 (8分)画出具有7个顶点的所有非同构的树 解：m=n?1=6 …… 四，用图论的方法证明：任何一个人群中至少有两个人认识的朋友数相同(10分) 证明：此题转换为证明任何一个没有孤立点的简单图至少有两个点的度数相同。 参考教材P5。 五．(10分) 设G为n 阶简单无向图，n>2且n为奇数，G与G的补图G中度数为奇数的顶点个数是否相等？证明你的结论 证明：根据补图定义d G(v i)+d G(v i)=n?1。相等。 由频序列相同证明有同样奇数的顶点个数。 参考教材P5。 离散数学图论部分综合练习 一、单项选择题 1．设图G 的邻接矩阵为 ??? ???? ? ????? ???0101 010******* 11100100110 则G 的边数为( )． A ．6 B ．5 C ．4 D ．3 2．已知图G 的邻接矩阵为 ， 则G 有（ ）． A ．5点，8边 B ．6点，7边 C ．6点，8边 D ．5点，7边 3．设图G ＝ 图三 7．设有向图（a ）、（b ）、（c ）与（d ）如图四所示，则下列结论成立的是 ( ) ． 图四 A ．（a ）是强连通的 B ．（b ）是强连通的 C ．（c ）是强连通的 D ．（d ）是强连通的 应该填写：D 8．设完全图K n 有n 个结点(n ≥2)，m 条边，当（ ）时，K n 中存在欧拉回路． A ．m 为奇数 B ．n 为偶数 C ．n 为奇数 D ．m 为偶数 9．设G 是连通平面图，有v 个结点，e 条边，r 个面，则r = ( )． A ．e －v ＋2 B ．v ＋e －2 C ．e －v －2 D ．e ＋v ＋2 10．无向图G 存在欧拉通路，当且仅当( )． A ．G 中所有结点的度数全为偶数 B ．G 中至多有两个奇数度结点 C ．G 连通且所有结点的度数全为偶数 D ．G 连通且至多有两个奇数度结点 11．设G 是有n 个结点，m 条边的连通图，必须删去G 的( )条边，才能确定G 的一棵生成树． A ．1m n -+ B ．m n - C ．1m n ++ D ．1n m -+ 12．无向简单图G 是棵树，当且仅当( )． A ．G 连通且边数比结点数少1 B ．G 连通且结点数比边数少1 C ．G 的边数比结点数少1 D ．G 中没有回路． 二、填空题 1．已知图G 中有1个1度结点，2个2度结点，3个3度结点，4个4度结 点，则G 的边数是 ． 2．设给定图G (如图四所示)，则图G 的点割 ο ο ο ο c a b f 图论第一次作业 By byh |E(G)|,2|E(G)|2G υυ??≤ ??? ?? ??? 1.1 举出两个可以化成图论模型的实际问题 略 1.2 证明其中是单图 证明：（思路）根据单图无环无重边的特点，所以 最大的情形为任意两个顶点间有一条边相连，即极 端情况为。 ?1.4 画出不同构的一切四顶单图 ?0条边：1条边： ?2条边：3条边： ?4条边：5条边：?6条边： 1.10G?H当且仅当存在可逆映射θ:V G→V H，使得uv∈E G?θuθv∈E H，其中G和H是单图。（证明充分性和必要性） ?必要性 ?若G?H，由定义可得，存在可逆映射θ:V G→V Hφ:E G→E(H)当且仅当ψ G e=uv时，ψHφe=θuθ(v)，所以uv∈E G? θuθv∈E H ?充分性 ?定义?:E G→E(H)，使得uv∈E G和θuθv∈E(H)一一对应，于是?可逆，且ψ e=uv的充要条件是ψHφe=θuθv，得G?H G 1.12求证(a)?K m ,n =mn，(b)G是完全二分图，则?G≤1 4 v G2 ?(a)对于K m ,n ，将顶集分为X和Y，使得X∪Y=V K m,n， X∩Y= ?，X=m，Y=n，对于X中的每一顶点，都和Y中所有顶点相连，所以?K m,n =mn ?(b)设G的顶划分为X,Y，X=m,Y=v?m，则?G≤ ??K m ,v-m =v?m m≤v2 4 ?证明： ?(a)第一个序列考虑度数7,第二个序列考虑6,6,1 ?(b)将顶点v分成两部分v’和v’’ ?v’ = {v|v= v i, 1≤ i≤ k}, ?v’’ = {v|v= v i, k< i≤ n} ?以v’点为顶的原图的导出子图度数之和小于 ?然后考虑剩下的点贡献给这k个点的度数之和最大可能为 离散数学图论部分综合练习 一、单项选择题 1.设图G 的邻接矩阵为 ??? ???? ? ????? ???01010 1001000001 1100100110 则G 的边数为( ). A.6 B.5 C.4 D.3 2.已知图G 的邻接矩阵为 , 则G 有( ). A.5点,8边 B.6点,7边 C.6点,8边 D.5点,7边 3.设图G ＝ 图三 7.设有向图(a )、(b )、(c )与(d )如图四所示,则下列结论成立的就是 ( ). 图四 A.(a )就是强连通的 B.(b )就是强连通的 C.(c )就是强连通的 D.(d )就是强连通的 应该填写:D 8.设完全图K n 有n 个结点(n ≥2),m 条边,当( )时,K n 中存在欧拉回路. A.m 为奇数 B.n 为偶数 C.n 为奇数 D.m 为偶数 9.设G 就是连通平面图,有v 个结点,e 条边,r 个面,则r = ( ). A.e －v ＋2 B.v ＋e －2 C.e －v －2 D.e ＋v ＋2 10.无向图G 存在欧拉通路,当且仅当( ). A.G 中所有结点的度数全为偶数 B.G 中至多有两个奇数度结点 C.G 连通且所有结点的度数全为偶数 D.G 连通且至多有两个奇数度结点 11.设G 就是有n 个结点,m 条边的连通图,必须删去G 的( )条边,才能确定G 的一棵生成树. A.1m n -+ B.m n - C.1m n ++ D.1n m -+ 12.无向简单图G 就是棵树,当且仅当( ). A.G 连通且边数比结点数少1 B.G 连通且结点数比边数少1 C.G 的边数比结点数少1 D.G 中没有回路. 二、填空题 1.已知图G 中有1个1度结点,2个2度结点,3个3度结点,4个4度结点,则G 的边数就是 . 2.设给定图G (如图四所示),则图G 的点割 集就是 . 3.若图G= 二、应用题 题0：（1996年全国数学联赛） 有n （n ≥6）个人聚会，已知每个人至少认识其中的[n /2]个人，而对任意的[n /2]个人，或者其中有两个人相互认识，或者余下的n -[n /2]个人中有两个人相互认识。证明这n 个人中必有3个人互相认识。 注：[n /2]表示不超过n /2的最大整数。 证明 将n 个人用n 个顶点表示，如其中的两个人互相认识，就在相应的两个顶点之间连一条边，得图G 。由条件可知，G 是具有n 个顶点的简单图，并且有 （1）对每个顶点x ， )(x N G ≥[n /2]； （2）对V 的任一个子集S ，只要S ＝[n /2]，S 中有两个顶点相邻或V-S 中有 两个顶点相邻。 需要证明G 中有三个顶点两两相邻。 反证，若G 中不存在三个两两相邻的顶点。在G 中取两个相邻的顶点x 1和y 1,记N G (x 1)＝{y 1,y 2,……,y t }和N G (y 1)={x 1,x 2,……,x k },则N G (x 1)和N G (y 1)不相交，并且N G (x 1)（N G (y 1)）中没有相邻的顶点对。 情况一；n=2r ：此时[n /2]＝r ，由（1）和上述假设，t=k=r 且N G (y 1)＝V-N G (x 1)，但N G (x 1)中没有相邻的顶点对，由（2），N G (y 1)中有相邻的顶点对，矛盾。 情况二；n=2r+1: 此时[n /2]＝r ，由于N G (x 1)和N G (y 1)不相交，t ≥r,k ≥r,所以r+1≥t,r+1≥k 。若t=r+1,则k=r ，即N G (y 1)=r ，N G (x 1)＝V-N G (y 1)，由（2），N G (x 1)或N G (y 1)中有相邻的顶点对，矛盾。故k ≠r+1，同理t ≠r+1。所以t=r,k=r 。记w ∈V- N G (x 1) ∪N G (y 1),由（2），w 分别与N G (x 1)和N G (y 1)中一个顶点相邻，设wx i0∈E, wy j0∈E 。若x i0y j0∈E ，则w ，x i0, y j0两两相邻，矛盾。若x i0y j0?E ，则与x i0相邻的顶点只能是(N G (x 1)-{y j0})∪{w},与y j0相邻的顶点只能是(N G (y 1)-{x j0})∪{w}。但与w 相邻的点至少是3，故N G (x 1)∪N G (y 1)中存在一个不同于x i0和y j0顶点z 与w 相邻，不妨设z ∈N G (x 1)，则z ，w ，x i0两两相邻，矛盾。 题1：已知图的结点集V ={a ,b ,c ,d }以及图G 和图D 的边集合分别为： E (G )={(a ,a ), (a ,b ), (b ,c ), (a ,c )} E (D)={, , 一、填空 20% 1、 P ：你努力，Q ：你失败。“除非你努力，否则你将失败”的翻译为 ；“虽然你努力了，但还是失败了”的翻译为 。 2、论域D={1，2}，指定谓词P 则公式),(x y yP x ??真值为 。 2、 设S={a 1 ，a 2 ，…，a 8}，B i 是S 的子集，则由B 31所表达的子集是 。 3、 设A={2，3，4，5，6}上的二元关系}|,{是质数x y x y x R ∨<><=，则R= （列举法）。 R 的关系矩阵M R = 。 5、设A={1，2，3}，则A 上既不是对称的又不是反对称的关系R= ； A 上既是对称的又是反对称的关系R= 。 6、设代数系统，其中A={a ，b ，c}, 则幺元是 ；是否有幂等 性 ；是否有对称性 。 7、4阶群必是 群或 群。 8、下面偏序格是分配格的是 。 9、n 个结点的无向完全图K n 的边数为 ，欧拉图的充要条件是 。 10、公式R Q P Q P P ?∧∨?∧∧?∨)(())(( 的根树表示为 。 二、选择 20% （每小题2分） 1、在下述公式中是重言式为（ ） A ．)()(Q P Q P ∨→∧； B ．))()(()(P Q Q P Q P →∧→??； C ．Q Q P ∧→?)(； D ．)(Q P P ∨→ 。 2、命题公式 )()(P Q Q P ∨?→→? 中极小项的个数为（ ），成真赋值的个数为（ ）。 A ．0； B ．1； C ．2； D ．3 。 3、设}}2,1{},1{,{Φ=S ，则 S 2 有（ ）个元素。 A ．3； B ．6； C ．7； D ．8 。 4、 设} 3 ,2 ,1 {=S ，定义S S ?上的等价关系 },,,, | ,,,{c b d a S S d c S S b a d c b a R +=+?>∈∈<><><<=则由 R 产 生的S S ?上一个划分共有（ ）个分块。 A ．4； B ．5； C ．6； D ．9 。 5、设} 3 ,2 ,1 {=S ，S 上关系R 的关系图为 习题三： ● 证明：是连通图G 的割边当且仅当V(G)可划分为两个子集V1和V2，使对任意及, G 中的路必含. 证明：充分性: 是的割边，故至少含有两个连通分支，设是其中一个连通分支的顶点集，是其余分支的顶点集，对12,u V v V ?∈?∈，因为中的不连通，而在中与连通，所以在每一条路上，中的必含。 必要性：取12,u V v V ∈∈，由假设中所有路均含有边，从而在中不存在从与到的路，这表明不连通，所以e 是割边。 ● 3.设G 是阶大于2的连通图，证明下列命题等价： （1） G 是块 （2） G 无环且任意一个点和任意一条边都位于同一个圈上； （3） G 无环且任意三个不同点都位于同一条路上。 ： 是块，任取的一点，一边，在边插入一点，使得成为两条边，由此得到新图，显然的是阶数大于3的块，由定理，中的u,v 位于同一个圈上，于是 中u 与边都位于同一个 圈上。 ： 无环，且任意一点和任意一条边都位于同一个圈上，任取的点u ，边e ，若在上，则三个不同点位于同一个闭路，即位于同一条路，如不在上，由定理，的两点在同一个闭路上，在边插入一个点v ，由此得到新图，显然的是阶数大于3的块，则两条边的三个不同点在同一条路上。 ： 连通，若不是块，则中存在着割点，划分为不同的子集块,,,无环，12,x v y v ∈∈，点在每一条的路上，则与已知矛盾，是块。 ● 7.证明：若v 是简单图G 的一个割点，则v 不是补图的割点。 证明：是单图的割点，则有两个连通分支。现任取, 如果不在的 同一分支中，令是与 处于不同分支的点，那么，与在的补图中连通。若在的同一分支中，则它们在的补图中邻接。所以，若是的割点，则不是补图的割点。 ● 12.对图3——20给出的图G1和G2，求其连通度和边连通度，给 出相应的最小点割和最小边割。 解：()12G κ= 最小点割 {6,8} 1()2G λ= 最小边割{（6,5），（8,5）} ()25G κ= 最小点割{6,7,8,9,10} 2()5G λ= 最小边割{（2,7）…（1,6）} ● 13.设H 是连通图G 的子图，举例说明：有可能k(H)> k(G). 解： 通常. 整个图为，割点左边的图为的的子图， ，则. e H 08信安专业离散数学期中考试试题 1.设A, B, C, D为4个集合. 已知A?B且C?D.证明: A∪C?B∪D; A∩C?B∩D . (15分) 2.化简以下公式: A∪((B―A)―B) (10分) 3.设R是非空集合A上的二元关系.证明:R∪R-1是包含R的 最小的对称的二元关系. (15分) 4.设A={1,2,…,20},R={ 期中考试试题解答 1.证明: ?x, x∈A∪C x∈A∩C ?x∈A∨x∈C ?x∈A∧x∈C ?x∈B∨x∈D (A?B,C?D) ?x∈B∧x∈D (A?B,C?D) ?x∈B∪D ?x∈B∩D ∴A∪C?B∪D ∴A∩C?B∩D 2.解: A∪((B―A)―B) =A∪((B∩∽A)∩∽B) =A∪(∽A∩(B∩∽B)) =A∪(∽A∩φ) =A∪ф =A . 3.证明:首先证R∪R-1是对称关系. ? **学院2016—2017学年第二学期期末考试2014级本科数学与应用数学专业《图论》试卷A （本试卷满分100分，考试时间110分钟） 一、填空题（每小题2分，共20分） 1.图G的两个子图G1，G2的环和表示为_______． 2.图G中的一圈，若它通过G中的每一条边(或弧)恰好一次，则称该圈为____． 3.图G的两个不同的生成的树T1，T2的顶点个数_______．（填相同或不相同）4．“3,3 K是欧拉图也是哈密顿图”这句话是_______。(填对或错) 5.图G的任意顶点的关联集都等于其余各顶点关联集的____． 6.(p,q)图G的基本圈有_________个． 7.连通图G的边连通度定义为． 8.设M是G的一个匹配，如果G的每一个顶点都是M-饱和点，则M为______． 9.使图G为n-着色的最小数值即为G的_________． 10.极大可平面图的每一个面的次数都是_________． 二、判断题（每小题1分，共10分） 1.同构的图保持邻接关系． 2.最小生成树即G的所有生成树中权值最小的生成树． K是欧拉图． 3. 5 4.设G是无向连通图，则G是一笔画 G中没有奇数度顶点． 5.图的秩等于图的完全关联矩阵的秩，而不等于其关联矩阵的秩． 6.图的关联矩阵是对称矩阵． 7.图的边连通度大于最小顶点的度数． 8.一个非完全连通图的连通度就是使这个图成为非连通图所需要去掉的最小顶点数． 9.完美匹配必定是最大匹配，但反之不然． K的子图． 10．一个图是平面图当且仅当它没有收缩到K5或 3,3 三、单项选择题（每小题2分，共20分） 1. 一个图的所有顶点的度数之和不可能是( ) A. 5 B. 6 C. 8 D. 10 2. 如果连通图G 的顶点个数为8，则其生成树中边的个数为( ) A. 7 B. 6 C. 9 D. 8 3. 在如下各图中（ ）欧拉图。 4．如下右图所示，以下说法正确的是 ( )． A ．{a, e }是点割集 B ．e 是割点 C ．{b , e }是点割集 D ．{d }是点割集 5. 如果连通图G 的顶点个数为7，边数为8，则其向量空间的维数为( ) A. 9 B. 8 C. 7 D. 1 6．设无向图G 的邻接矩阵为 ????????????????010******* 000011100100110， 则G 的边数为( )． A ．3 B ．4 C ．5 D ．6 7.如果连通图G 的点连通度为2，边连通度为3，图的最小顶点的度数可能为（ ） A. 0 B. 1 C. 3 D ．2 8.G 的一个匹配M 中的顶点（ ）M 饱和顶点 A. 都不是 B. 只有一个是 C. 有些是，有些不是 D.全部是 电子科技大学研究生试题图论及其应用参考答 案 HUA system office room 【HUA16H-TTMS2A-HUAS8Q8-HUAH1688】 电子科技大学研究生试题 《图论及其应用》(参考答案) 考试时间：120分钟 一．填空题(每题3分，共18分) 1．4个顶点的不同构的简单图共有__11___个； 2．设无向图G 中有12条边，已知G 中3度顶点有6个，其余顶点的度数均小于3。则G 中顶点数至少有__9___个； 3．设n 阶无向图是由k(k2)棵树构成的森林，则图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 ） 6．下列图中，不是偶图的是（ B ） 7．下列图中，存在完美匹配的图是（B ） 三．作图(6分) 1．画出一个有欧拉闭迹和哈密尔顿圈的图； 2．画出一个有欧拉闭迹但没有哈密尔顿圈的图； 3．画出一个没有欧拉闭迹但有哈密尔顿圈的图； 解： 四． A C D 1 2 3 A B C D 解：由克鲁斯克尔算法的其一最小生成树如下图： 权和为：20. 五．(8分) 求下图G 的色多项式P k (G). 解：用公式 )(e G P k -G 的色多项式： )3)(3)()(345-++=k k k G P k 。 六．(10分) 一棵树有n 2个顶点的度数为2，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 由上面两式可得：n 1=n 2+2n 3+…+(k -1)n k 七．证明：(8分) 设G 是具有二分类(X,Y)的偶图，证明(1)G 不含奇圈；（2）若|X |≠|Y |，则G 是非哈密尔顿图。 证明：(1) 若不然，设C=v 1v 2…v m v 1为G 的一个奇圈，不妨设v 1X, v 5 v v v 6 图G 习题一 1. （题14）：证明图1-28中的两图是同构的 证明 将图1-28的两图顶点标号为如下的(a)与(b)图 作映射f : f(v i )→u i (1≤ i ≤ 10) 容易证明，对?v i v j ∈E((a)),有f(v i v j )=u i u j ∈E((b)) (1≤ i ≤ 10, 1≤j ≤ 10 ) 由图的同构定义知，图1-27的两个图是同构的。 2. （题6）设G 是具有m 条边的n 阶简单图。证明：m =???? ??2n 当且仅当G 是 完全图。 证明 必要性 若G 为非完全图，则? v ∈V(G),有d(v)< n-1 ? ∑ d(v) < n(n-1) ? 2m 证明 由于G 为k 正则偶图，所以，k | V 1 | =m = k | V 2 | ? ∣V 1∣= ∣V 2 ∣。 4. （题12）证明：若δ≥2，则G 包含圈。 证明 只就连通图证明即可。设V(G)=｛v 1,v 2,…,v n ｝,对于G 中的路v 1v 2…v k ,若v k 与v 1邻接，则构成一个圈。若v i1v i2…v in 是一条路，由于δ≥ 2，因此，对v in ，存在点v ik 与之邻接，则v ik ?v in v ik 构成一个圈 。 5. （题17）证明：若G 不连通，则G 连通。 证明 对)(,_ G V v u ∈?,若u 与v 属于G 的不同连通分支，显然u 与v 在_ G 中连通；若u 与v 属于g 的同一连通分支，设w 为G 的另一个连通分支中的一个顶点，则u 与w ，v 与w 分别在_ G 中连通，因此，u 与v 在_ G 中连通。 习题二 2、证明：每棵恰有两个1度顶点的树均是路。 证明：设树T 为任意一个恰有两个1度顶点的树，则T 是连通的，且无圈，令V 1 、V 2 为度为1的顶点，由于其他的顶点度数均为0或者2，且T 中无圈，则从V 1到V 2 有且只有一条连通路。所以，每棵恰有两个1度顶点的树均是路。得证。 5、证明：正整数序列),...,,(21n d d d 是一棵树的度序列当且仅当 )1(21 -=∑=n d n i i 。 证明：设正整数序列),...,,(21n d d d 是一棵树T 的度序列，则满足 E d n i i 21 =∑=，E 为T 的边数，又有边数和顶点的关系1+=E n ，所以)1(21 -=? ∑=n d n i i 14、证明：若e 是n K 的边，则3 )2()(--=-n n n n e K τ。 若e 为Kn 的一条边，由Kn 中的边的对称性以及每棵生成树的边数为n-1，Kn 的所有生成树的总边数为：2 )1(--n n n ，所以，每条边所对应的生成树的棵数为： 32 2)1(2 1 )1(--=--n n n n n n n ，所以，K n - e 对应的生成树的棵数为： 332)2(2)(----=-=-n n n n n n n n e K τ 16、Kruskal 算法能否用来求： （1）赋权连通图中的最大权值的树？ （2）赋权图中的最小权的最大森林？如果可以，怎样实现？ **学院2013—2014学年第二学期期末考试 数学与应用数学专业2013级《图论》试卷B （本试卷满分100分，考试时间110分钟） 一、填空题 （每小题2分，共20分） 1.每一对不同的顶点都邻接的简单图称为完全图，n 阶完全图记为 。 2.树T 无圈，但增加任一新边，得到且仅得到一个 。 3.图G 中的一个圈，若它通过G 中每个顶点恰好一次，则该圈称为 。 4.图G (p ,q)的基本圈有 个。 5.图的所有顶点的关联集线性 （填相关与无关）。 6.6阶完全图的连通度是 。 7.图的边着色要求 的边着不同的颜色。 8.M 为 的充要条件是：图G 中不存在M -可增广道路。 9.若M 是图G =(V ,E )的边子集，且M 中的任意两条边在G 中不相邻，则称M 为G 中的一个 。 10. G 的所有面的次数之和等于边数的 倍。 二、判断题（每小题2分，共20分） 1.同构的两个图顶点数相同。 2.12G G ⊕中的边数一定比1G 中的边多。 3.最小生成树即G 的所有生成树中权最小的生成树。 4.连通图的秩与其关联矩阵的秩不相等。 5.在图的邻接矩阵中每一行中的1的个数表示相应顶点的度数。 6.图的连通度、边连通度、顶点的最小度数三者可能相等。 7.无向图G 为欧拉图当且仅当G 连通，并且所有顶点的度都是偶数。 8.一个非平凡连通图的连通度就是使这个图成为非连通图所需要去掉 的最小边数。 9.设G 为长度大于或等于3的奇圈，则()G χ'=3。 10. 一个图是平面图当且仅当它没有收缩到K 3,3 和K 5的子图。 专业：__________ 班级：______ 学号：_______________________ 姓名：_____________________ ——————————————密——————————————封————————————————线——————————— 专业：________ 班级：___________ 学号：_______________________ 姓名：_____________________ ——————————————密——————————————封————————————————线——————————— 作业解答 练习题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:n for j = 1:num + 1 if w(i) < bin(j) bin(j) = bin(j) - w(i); s{j} = [s{j},i]; if j == num + 1 num = num + 1; end break; end end end s = 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:n if v(i)>=max(V_Left) box_count=box_count+1; x(i,box_count)=1; V_Left=[V_Left V-v(i)]; else j=1; while(v(i)>V_Left(j)) j=j+1; end x(i,j)=1; V_Left(j)=V_Left(j)-v(i); end temp=find(x(i,:)==1); fprintf('第%d个物品放在第%d个容器\n',i,temp) end output: 第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:n j=1; while(j<=box_count) if x(i)>box(j) j=j+1; continue; else图论及其应用答案电子科大
离散数学试卷及答案(2)
07年研究生试卷(答案)
离散数学图论部分经典试题及答案
图论 王树禾 答案
离散数学图论部分经典试题及答案
图论习题参考答案
离散数学试卷及答案
图论及其应用 答案电子科大
集合论图论 期中考试试题及答案
图论试卷A卷-14数本
电子科技大学研究生试题图论及其应用参考答案完整版
图论及其应用13章习题答案电子科大
图论试卷及参考答案B-13级数学本科
图论习题及答案