当前位置：文档库 › 电子科技大学图论第二章习题答案

电子科技大学图论第二章习题答案

电子科技大学研究生试题《图论及其应用》(参考答案)

电子科技大学研究生试题《图论及其应用》(参考答案) 考试时间：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

2004图论复习题答案

图论复习题答案一、判断题，对打，错打 1．无向完全图是正则图。 () 2．零图是平凡图。() 3．连通图的补图是连通图.() 4．非连通图的补图是非连通图。() 5．若连通无向简单图G中无圈，则每条边都是割边。() 6．若无向简单图G是（n，m）图，并且m=n-1，则G是树。() 7．任何树都至少有2片树叶。() 8．任何无向图G都至少有一个生成树。() 9．非平凡树是二分图。() 10．所有树叶的级均相同的二元树是完全二元树。() 11．任何一个位置二元树的树叶都对应唯一一个前缀码。() 12． K是欧拉图也是哈密顿图。() 3,3 13．二分图的对偶图是欧拉图。() 14．平面图的对偶图是连通图。() 页脚内容1

15．设G*是平面图G的对偶图，则G*的面数等于G的顶点数。() 二、填空题 1．无向完全图K6有15条边。 2．有三个顶点的所有互不同构的简单无向图有4个。 3．设树T中有2个3度顶点和3个4度顶点，其余的顶点都是树叶，则T中有10片树叶。 4．若连通无向图G是（n，m）图，T是G的生成树，则基本割集有n-1个，基本圈有m-n+1个。 5．设连通无向图G有k个奇顶点，要使G变成欧拉图，在G中至少要加k/2条边。 6．连通无向图G是（n，m）图，若G是平面图，则G有m-n+2个面。三、解答题 1．有向图D如图1所示，利用D的邻接矩阵及其幂运算求解下列问题：（1）D中长度等于3的通路和回路各有多少条。（2）求D的可达性矩阵。（3）求D的强分图。解：（1） a b c d e 图1 页脚内容2

页脚内容3 M=????????????????000101000000001 010*******M 2=?? ? ? ??????? ?????010******* 000101000001000 M 3=????????????????10000 01000010000001010000M 4=??? ???? ? ??? ?????00010 01000 100000100000010 由M 3可知，D 中长度等于3的通路有5条，长度等于3的回路有3条。（2） I+M+M 2+M 3+M 4=????????????? ???100000100000100 0001000001 +??????????? ?? ???000101000000001 010******* +??????????? ?? ???010000001000010 1000001000 +??? ???? ? ??? ?? ???100000100001000 0001010000 + ????????????????00010 01000100000100000010 =??? ???? ???? ?? ???21020 1301011111 020******* D 的可达性矩阵为 R=B （I+M+M 2+M 3+M 4）=??? ???? ? ????? ???110101********* 1101011011 b c d e 图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.证明：四个顶点的非同构简单图有11个。证明：设四个顶点中边的个数为m ，则有： m=0: m=1 ： m=2： m=3： m=4： (a) v 23 4 (b)

m=5： m=6：因为四个顶点的简单图最多就是具有6条边，上面所列出的情形是在不同边的条件下的不同构的情形，则从上面穷举出的情况可以看出四个顶点的非同构简单图有11个。 ● 11.证明：序列（7,6,5,4,3,3,2）和（6,6,5,4,3,3,1）不是图序列。证明：由于7个顶点的简单图的最大度不会超过6，因此序列（7,6,5,4,3,3,2）不是图序列；（6,6,5,4,3,3,1）是图序列 1 1 12312(1,1,,1,,,)d d n d d d d d π++=---是图序列（5,4,3,2,2,0）是图序列，然而（5,4,3,2,2,0）不是图序列，所以（6,6,5,4,3,3,1）不是图序列。 ● 12.证明：若，则包含圈。证明：下面仅对连通图的下的条件下进行证明，不连通的情形可以通过分成若干个连通的情形来证明。设 , 对于中的路若与邻接，则构成一个闭路。若是一条路，由于，因此，对于，存在与之邻接，则构成一个圈。 ● 17.证明：若G 不连通，则连通。证明：对于任意的 ,若与属于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)

图论及其应用答案电子科大

图论及其应用答案电子科大 Newly compiled on November 23, 2020

图论讲义第2章-连通性

第二章图的连通性在第一章中已经定义连通图是任二顶点间都有路相连的图。对于连通图，其连通的程度也有高有低。例如，下列三个图都是连通图。对于图G 1，删除一条边或一个顶点便可使其变得不连通；而对于图G 2，至少需要删除两条边才能使其不连通，也可以删除一个顶点使其不连通；对于图G 3，要破坏其连通性，则至少需要删除三条边或三个顶点。本章主要讨论如何通过图的顶点集、边集和不交的路集合的结构性质来获知图的连通性程度。通过研究割边和割点来刻画1连通图的特性；定义连通度和边连通度来度量连通图连通程度的高低；通过不交路结构和元素的共圈性质来反映图的2连通和k 连通性。 §2.1 割点和割边定义2.1.1 设)(G V v ∈，如果)()(G w v G w >?，则称v 为G 的一个割点。（注：该定义与某些著作中的定义有所不同，主要是在环边的顶点是否算作割点上有区别）。例如，下图中u , v 两点是其割点。定理2.1.1 如果点v 是简单图G 的一个割点，则边集E (G)可划分为两个非空子集1E 和2E ，使得][1E G 和][2E G 恰好有一个公共顶点v 。证明留作习题。推论2.1.1 对连通图G ，顶点v 是G 的割点当且仅当v G ?不连通。定理2.1.2 设v 是树T 的顶点，则v 是T 的割点当且仅当1)(>v d 。证明：必要性：设v 是T 的割点，下面用反证法证明1)(>v d 。若0)(=v d ，则1K T ?，显然v 不是割点。若1)(=v d ，则v T ?是有1)(??v T ν条边的无圈图，故是树。从而)(1)(T w v T w ==?。因此v 不是割点。以上均与条件矛盾。充分性：设1)(>v d ，则v 至少有两个邻点u ,w 。路uvw 是T 中一条),(w u 路。因T 是树，uvw 是T 中唯一的),(w u 路，从而)(1)(T w v T w =>?。故v 是割点。证毕。

图论1-3藏习题解答

学号：0441 姓名：张倩习题1 4．证明图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的两个图是同构的。 5.证明：四个顶点的非同构简单图有11个。证明：设四个顶点中边的个数为m ，则有： m=0: m=1 ： m=2： m=3： (a) v 1 v 2 v 3 v v 5 v 6 v 7 v 8 v 9 v 10 u 1 u 2 u 3 u 4 u 5 u 6 u 7 u 8 u 9 u 10 (b)

m=4： m=5： m=6：因为四个顶点的简单图最多就是具有6条边，上面所列出的情形是在不同边的条件下的不同构的情形，则从上面穷举出的情况可以看出四个顶点的非同构简单图有11个。 11.证明：序列（7,6,5,4,3,3,2）和（6,6,5,4,3,3,1）不是图序列。证明：由于7个顶点的简单图的最大度不会超过6，因此序列（7,6,5,4,3,3,2）不是图序列；（6,6,5,4,3,3,1）是图序列 ()1 1 123121,1,,1,,,=d d n d d d d d π++---是图序列（5,4,3,2,2,0）是图序列，然而（5,4,3,2,2,0）不是图序列，所以（6,6,5,4,3,3,1）不是图序列。 12.证明：若δ≥2，则G 包含圈。证明只就连通图证明即可。设V(G)=｛v1,v2,…,vn｝,对于G 中的路v1v2…vk,若vk 与v1邻接，则构成一个圈。若vi1vi2…vin 是一条路，由于?? 2，因此，对vin ，存在点vik 与之邻接，则vik?vinvik 构成一个圈。 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 中连通。

图论及其应用答案电子科大

图论及其应用答案电子科大 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）}

习题参考解答图论部分

（1）（3，2，0，1，5）；（2）（6，3，3，2，2）（3）（4，4，2，2，4）；（4）（7，6，8，3，9，5）解：除序列（1）不是图序列外，其余的都是图序列。因为在（1）中，总和为奇数，不满足图总度数为偶数的握手定理。可以按如下方法构造满足要求的图：序列中每个数字ai 对应一个点，如果序列数字是偶数，那么就在对应的点上画ai/2个环，如果序列是奇数，那么在对应的点上画(ai-1)/2个环。最后，将奇数序列对应的点两两一组，添加连线即可。下面以（2）为例说明： (6 , 3, 3, 2, 2 ) 对应图G 的点集合V= { v 1,v 2,v 3,v 4,v 5} 每个结点对应的环数(6/2, (3-1)/2, (3-1)/2, 2/2,2/2) = (3,1,1,1,1)

习题参考解答(图论部分)

习题十 1. 设G 是一个(n ，m)简单图。证明：，等号成立当且仅当G 是完全图。证明：（1）先证结论：因为G 是简单图，所以G 的结点度上限 max(d(v)) ≤ n-1, G 图的总点度上限为 max(Σ(d(v)) ≤ n ﹒max(d(v)) ≤ n(n-1) 。根据握手定理，G 图边的上限为 max(m) ≤ n(n-1)/2,所以。（2） =〉G 是完全图因为G 具有上限边数，假设有结点的点度小于n-1,那么G 的总度数就小于上限值，边数就小于上限值，与条件矛盾。所以，G 的每个结点的点度都为n-1，G 为完全图。 G 是完全图 =〉因为G 是完全图，所以每个结点的点度为n-1, 总度数为n(n-1)，根据握手定理，图G 的边数。■ 2. 设G 是一个（n ，n +1）的无向图，证明G 中存在顶点u ，d （u ）≥3。证明：反证法，假设,则G 的总点度上限为max(Σ(d(u)) ≤2 n ，根据握手定理，图边的上限为max(m) ≤ 2n/2=n 。与题设m = n+1，矛盾。因此，G 中存在顶点u ，d （u ）≥3。■ 3．确定下面的序列中哪些是图的序列，若是图的序列，画出一个对应的图来: （1）（3，2，0，1，5）；（2）（6，3，3，2，2）（3）（4，4，2，2，4）；（4）（7，6，8，3，9，5）解：除序列（1）不是图序列外，其余的都是图序列。因为在（1）中，总和为奇数，不满足图总度数为偶数的握手定理。可以按如下方法构造满足要求的图：序列中每个数字ai 对应一个点，如果序列数字是偶数，那么就在对应的点上画ai/2个环，如果序列是奇数，那么在对应的点上画(ai-1)/2个环。最后，将奇数序列对应的点两两一组，添加连线即可。下面以（2）为例说明： (6 , 3, 3, 2, 2 ) 对应图G 的点集合V= { v 1,v 2,v 3,v 4,v 5} 每个结点对应的环数(6/2, (3-1)/2, (3-1)/2, 2/2,2/2) = (3,1,1,1,1)

电子科大图论答案

图论第三次作业一、第六章 2.证明：根据欧拉公式的推论，有m ≦l*(n-2)/(l-2), (1)若deg(f)≧4,则m ≦4*(n-2)/2=2n-4; (2)若deg(f)≧5,则m ≦5*(n-2)/3,即：3m ≦5n-10; (3)若deg(f)≧6,则m ≦6*(n-2)/4,即：2m ≦3n-6. 3.证明： ∵G 是简单连通图，∴根据欧拉公式推论，m ≦3n-6; 又，根据欧拉公式：n-m+φ=2,∴φ=2-n+m ≦2-n+3n-6=2n-4. 4.证明： (1)∵G 是极大平面图，∴每个面的次数为3，由次数公式：2m==3φ, 由欧拉公式：φ=2-n+m, ∴m=2-n+m,即：m=3n-6. (2)又∵m=n+φ-2,∴φ=2n-4. (3)对于3n >的极大可平面图的的每个顶点v ，有()3d v ≥，即对任一一点或者

子图，至少有三个邻点与之相连，要使这个点或子图与图G 不连通，必须把与之相连的点去掉，所以至少需要去掉三个点才能使()(H)w G w G <-，由点连通度的定义知()3G κ≥。 5.证明：假设图G 不是极大可平面图，那么G 不然至少还有两点之间可以添加一条边e ，使G+e 仍为可平面图，由于图G 满足36m n =-，那么对图G+e 有36m n '=-，而平面图的必要条件为36m n '≤-，两者矛盾，所以图G 是极大可平面图。 6.证明： (1)由()4G δ=知5n ≥当n=5时，图G 为5K ，而5K 为不可平面图，所以6n ≥，（由()4G δ=和握手定理有24m n ≥，再由极大可平面图的性质36m n =-，即可得6n ≥）对于可平面图有()5G δ≤，而6n ≥，所以至少有6个点的度数不超过5. (2)由()5G δ=和握手定理有25m n ≥，再由极大可平面图的性质36m n =-，即可得12n ≥，对于可平面图有()5G δ≤，而12n ≥，所以至少有12个点的度数不超过5. 二、第七章 2.证明：设n=2k+1,∵G 是Δ正则单图，且Δ>0, ∴m(G)==>k Δ,由定理5可知χˊ(G)=Δ(G)+1.

图论习题参考答案

二、应用题题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)={, , , , } 试作图G 和图D ，写出各结点的度数，回答图G 、图D 是简单图还是多重图？解： a d a d b c b c 图G 图D 例2图