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

习题一1. 一个工厂为一结点；若两个工厂之间有业务联系，则此两点之间用边相联；这样就得到一个无向图。

若每点的度数为3，则总度数为27，与图的总度数总是偶数的性质矛盾。

若仅有四个点的度数为偶数，则其余五个点度数均为奇数，从而总度数为奇数，仍与图的总度数总是偶数的性质矛盾。

2. 若存在孤立点，则m 不超过K n-1的边数, 故 m <= (n-1)(n-2)/2, 与题设矛盾。

3.4. 用向量(a 1,a 2,a 3)表示三个量杯中水的量, 其中a i 为第i 杯中水的量, i = 1,2,3.以满足a 1+a 2+a 3 = 8 (a 1,a 2,a 3为非负整数)的所有向量作为各结点, 如果(a 1,a 2,a 3)中某杯的水倒满另一杯得到 ( a ’1, a ’2, a ’3 ) , 则由结点到结点画一条有向边。

这样可得一个有向图。

本题即为在此图中找一条由( 8, 0, 0 )到( 4, 4, 0 )的一条有向路，以下即是这样的一条：5. 可以。

7. 同构。

同构的双射如下：8. 记e 1= (v 1,v 2), e 2= ( v 1,v 4), e 3= (v 3,v 1), e 4= (v 2,v 5), e 5= (v 6,v 3), e 6= (v 6,v 4), e 7= (v 5,v 3), e 8= (v 3,v 4), e 9 = (v 6,v 1), 则邻接矩阵为： 关联矩阵为：∑∑∑∑∑∑∑==+====-=++=-==---=--=ni i n i i n i n i n i ni i i n i i n i i i i a a n n a a a n n n a n a v v 1111121212/)1()1(2)1(])1[(。

，　所以 因为 ，＋ 的负度数，则为结点的正度数，为结点记－－－－－22 222 i i C a a ⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡---------100110000001001000010100010011010100000001001100000111, 001101000100000000001001010000001010⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡( 8, 0, 0 ) ( 5, 3, 0 ) ( 5, 0, 3 ) ( 2, 3, 3 ) ( 2, 5, 1 )(7, 0, 1 ) ( 7, 1, 0 ) ( 4, 4, 0 )( 4, 1, 3 )边列表为：A= (1,1,3,2,6,6,5,3,6), B= (2,4,1,5,3,4,3,4,1). 正向表为：A= (1,3,4,6,6,7,10), B= (2,4,5,1,4,3,3,4,1).习题二1. 用数学归纳法。

数据结构——图选择题整理1.设完全图Kn,有n个结点(n≥2),m条边，当()时，K,中存在欧拉回路。

A.m为奇数B.n为偶数C.n为奇数D.m为偶数解析:答案C完全图是一个简单的无向图，其中每对不同的顶点之间都恰连有一条边相连。

n 个端点的完全图有n个端点以及n(n-1)/2条边，因此完全图Kn的每个结点的度都为n-1，所以若存在欧拉回路则n-1必为偶数。

n必为奇数。

选C。

2、若从无向图的任意顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是（）A、强连通图B、连通图C、有回路D、一棵树解析：选B对于A，强连通图的概念是在有向图中的。

对于B，连通图证明任意两个顶点之间一定能够相连，因此一定可以到达。

对于C，有环图不一定是连通图不一定任意两个顶点均能到达。

对于D，树是可以，但是不是树也可以，题目中说的太肯定了，不能选，比如下图就不是树，但可以完成题目中要求的功能。

2、对于一个有n个顶点的图：若是连通无向图，其边的个数至少为（）；若是强连通有向图，其边的个数至少为（）A、n-1,nB、n-1,n(n-1)C、n,nD、n,n(n-1)解析：选A对于连通无向图，至少需要n-1条边。

对于强连通有向图，只要能形成一个大环就可以从任意一点到另一点。

3、设有无向图G=(V,E)和G'=(V',E')，若G’是G的生成树，则下列不正确的是（）a.G'为G的连通分量b.G'为G的无环子图c.G'为G的极小连通子图且V'=VA、a和bB、只有cC、b和cD、只有a解析：选D极大连通子图简称连通分量，生成树是极小连通子图。

故a不对，c对。

生成树无环，故b对4.带权有向图G用邻接矩阵存储，则vi的入度等于邻接矩阵中（）A、第i行非∞的元素个数B、第i列非∞的元素个数C、第i行非∞且非0的元素个数D、第i列非∞且非0的元素个数解析：选D带权有向图的邻接矩阵中，非0和∞的数字表示两点间边的权值。

图论习题二答案图论习题二答案图论是数学中的一个分支，研究的是图的性质和图之间的关系。

在图论中，有很多经典的习题可以帮助我们更好地理解和应用图的概念。

本文将探讨一些图论习题二的答案，帮助读者更好地理解和掌握图论的知识。

1. 习题：给定一个无向图G=(V,E)，其中V={1,2,3,4,5,6}，E={(1,2),(1,3),(2,3),(2,4),(3,4),(4,5),(4,6)}，求图G的邻接矩阵和关联矩阵。

答案：邻接矩阵是一个n×n的矩阵，其中n是图的顶点数。

对于无向图G，邻接矩阵的元素a[i][j]表示顶点i和顶点j之间是否存在边。

如果存在边，则a[i][j]=1，否则a[i][j]=0。

对于给定的图G，邻接矩阵为：0 1 1 0 0 01 0 1 1 0 01 1 0 1 0 00 1 1 0 1 10 0 0 1 0 00 0 0 1 0 0关联矩阵是一个n×m的矩阵，其中n是图的顶点数，m是图的边数。

对于无向图G，关联矩阵的元素b[i][j]表示顶点i和边j之间的关系。

如果顶点i是边j 的起点，则b[i][j]=-1；如果顶点i是边j的终点，则b[i][j]=1；否则b[i][j]=0。

对于给定的图G，关联矩阵为：-1 -1 0 0 0 01 0 -1 -1 0 00 1 1 0 0 00 0 0 1 -1 -10 0 0 0 1 00 0 0 0 0 12. 习题：给定一个有向图G=(V,E)，其中V={1,2,3,4,5}，E={(1,2),(1,3),(2,3),(2,4),(3,4),(4,1),(5,4)}，求图G的邻接表和深度优先搜索遍历结果。

答案：邻接表是一种图的表示方法，用于存储图中每个顶点的邻接顶点。

对于有向图G，邻接表中的每个元素表示该顶点的出边。

对于给定的图G，邻接表为：1: 2, 32: 3, 43: 44: 15: 4深度优先搜索（DFS）是一种图的遍历算法，用于遍历图中的所有顶点。

二、应用题题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，)N G≥[n/2]；(x（2）对V的任一个子集S，只要S＝[n/2]，S中有两个顶点相邻或V-S中有两个顶点相邻。

需要证明G中有三个顶点两两相邻。

反证，若G中不存在三个两两相邻的顶点。

在G中取两个相邻的顶点x1和y1,记N G(x1)＝{y1,y2,……,y t}和N G(y1)={x1,x2,……,x k},则N G(x1)和N G(y1)不相交，并且N G(x1)（N G(y1)）中没有相邻的顶点对。

情况一；n=2r：此时[n/2]＝r，由（1）和上述假设，t=k=r且N G(y1)＝V-N G(x1)，但N G(x1)中没有相邻的顶点对，由（2），N G(y1)中有相邻的顶点对，矛盾。

情况二；n=2r+1: 此时[n/2]＝r，由于N G(x1)和N G(y1)不相交，t≥r,k≥r,所以r+1≥t,r+1≥k。

若t=r+1,则k=r，即N G(y1)=r，N G(x1)＝V-N G(y1)，由（2），N G(x1)或N G(y1)中有相邻的顶点对，矛盾。

故k≠r+1，同理t≠r+1。

所以t=r,k=r。

记w∈V- N G(x1) ∪N G(y1),由（2），w分别与N G(x1)和N G(y1)中一个顶点相邻，设wx i0∈E, wy j0∈E。

若x i0y j0∈E，则w，x i0, y j0两两相邻，矛盾。

若x i0y j0∉E，则与x i0相邻的顶点只能是(N G(x1)-{y j0})∪{w},与y j0相邻的顶点只能是(N G(y1)-{x j0})∪{w}。

习题一作者---寒江独钓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 3u 4u(b)6.证明:1)充分性:当G 是完全图时，每个顶点的度数都是n −1,共有n 个顶点，总的度数为n(n −1)，因此总的边数是n(n−1)2=(n 2). 2)必要性:因为G 是简单图,所以当G 是完全图的时候每个顶点的度数才达到最大:n −1.若G 不是完全图，则至少有一个顶点的度数小于n −1,这样的话，总的度数就要小于n (n −1)，因此总的边数小于(n 2)，矛盾。

图论测试题及答案一、选择题1. 在图论中，如果一个图的每个顶点的度数都是偶数，那么这个图一定存在欧拉路径吗？A. 是的B. 不一定C. 没有欧拉路径D. 无法确定答案：B2. 图论中的哈密顿路径是指什么？A. 经过图中所有顶点的路径B. 经过图中所有顶点的回路C. 经过图中某些顶点的路径D. 经过图中某些顶点的回路答案：A3. 如果一个图是完全图，那么它的边数是多少？A. 顶点数的一半B. 顶点数的平方C. 顶点数的两倍D. 顶点数减一答案：B二、填空题4. 在无向图中，如果存在一条路径，使得每个顶点只被经过一次，并且起点和终点相同，这样的路径被称为________。

答案：欧拉回路5. 图论中的二分图是指图中的顶点可以被分成两个不相交的集合，使得同一个集合内的顶点之间没有边，而不同集合之间的顶点之间有边，这种图也被称为________。

答案：二部图三、简答题6. 请简述图论中的最短路径问题，并给出解决该问题的一种算法。

答案：最短路径问题是在图中找到两个顶点之间的最短路径的问题。

解决该问题的一种算法是迪杰斯特拉算法（Dijkstra's algorithm），该算法通过维护一个顶点集合来记录已经找到最短路径的顶点，并迭代更新距离，直到找到从起点到所有顶点的最短路径。

7. 描述图论中的图着色问题，并说明其在实际生活中的应用。

答案：图着色问题是将图的顶点着色，使得任何两个相邻的顶点颜色不同。

在实际生活中，图着色问题可以应用于时间表的安排、频率分配、电路设计等领域，其中每个顶点代表一个任务或频道，而颜色则代表不同的时间段或频率。

结束语：以上是图论测试题及答案，希望能够帮助大家更好地理解和掌握图论的基本概念和算法。

二、应用题题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，)(xN G≥[n/2]；（2）对V的任一个子集S，只要S＝[n/2]，S中有两个顶点相邻或V-S中有两个顶点相邻。

需要证明G中有三个顶点两两相邻。

反证，若G中不存在三个两两相邻的顶点。

在G中取两个相邻的顶点x1和y1,记N G(x1)＝{y1,y2,……,y t}和N G(y1)={x1,x2,……,x k},则N G(x1)和N G(y1)不相交，并且N G(x1)（N G(y1)）中没有相邻的顶点对。

情况一；n=2r：此时[n/2]＝r，由（1）和上述假设，t=k=r且N G(y1)＝V-N G(x1)，但N G(x1)中没有相邻的顶点对，由（2），N G(y1)中有相邻的顶点对，矛盾。

情况二；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两两相邻，矛盾。

图论部分练习一、填空题1．已知图G中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G的边数是．2．设给定图G(如右由图所示)，则图G的点割集是．3．设G是一个图，结点集合为V，边集合为E，则G的结点等于边数的两倍．4．无向图G存在欧拉回路，当且仅当G连通且．5．设G=<V，E>是具有n个结点的简单图，若在G中每一对结点度数之和大于等于，则在G中存在一条汉密尔顿路．6．若图G=<V, E>中具有一条汉密尔顿回路，则对于结点集V的每个非空子集S，在G中删除S中的所有结点得到的连通分支数为W，则S中结点数|S|与W满足的关系式为．7．设完全图Kn 有n个结点(n≥2)，m条边，当时，Kn中存在欧拉回路．8．结点数v与边数e满足关系的无向连通图就是树．9．设图G是有6个结点的连通图，结点的总度数为18，则可从G中删去条边后使之变成树．10．设正则5叉树的树叶数为17，则分支数为i = ．二、判断说明题（判断下列各题，并说明理由．）1．如果图G是无向图，且其结点度数均为偶数，则图G存在一条欧拉回路．2．如下图所示的图G存在一条欧拉回路．3．如下图所示的图G不是欧拉图而是汉密尔顿图．G4．设G是一个有7个结点16条边的连通图，则G为平面图．5．设G是一个连通平面图，且有6个结点11条边，则G有7个面．三、计算题1．设G=<V，E>，V={ v1，v2，v3，v4，v5}，E={ (v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)，(v3,v5)，(v4,v5) }，试(1) 给出G的图形表示； (2) 写出其邻接矩阵；(3) 求出每个结点的度数； (4) 画出其补图的图形．2．图G=<V, E>，其中V={ a, b, c, d, e}，E={ (a, b), (a, c), (a, e), (b, d), (b, e), (c, e), (c, d), (d, e) }，对应边的权值依次为2、1、2、3、6、1、4及5，试（1）画出G的图形；（2）写出G的邻接矩阵；（3）求出G权最小的生成树及其权值．3．已知带权图G如右图所示．(1) 求图G的最小生成树； (2)计算该生成树的权值．4．设有一组权为2, 3, 5, 7, 17, 31，试画出相应的最优二叉树，计算该最优二叉树的权．四、证明题1．设G是一个n阶无向简单图，n是大于等于3的奇数．证明图G与它的补图G中的奇数度顶点个数相等．2．设连通图G 有k 个奇数度的结点，证明在图G 中至少要添加2k 条边才能使其成为欧拉图．。

第1章 图论预备知识1.1解：(1) p={φ,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}}(2) p={,{a},{{b,c}},{a,{b,c}}} (3) p={,{}}(4) p={,{},{{}},{,{}}}(5)p={,{{a,b}},{{a,a,b}},{{a,b,a,b}},{{a,b},{a,a,b}},{{a,b},{a,b,a,b}},{{a,b},{a,a,b},{a,b,a,b}}} 1.2 解：(1) 真 (2) 假 (3)假 (4)假 1.3 解：(1) 不成立，A={1} B={1,2} C={2} (2) 不成立，A={1} B={1,2} C={1,3}1.4 证明：设(x,y)∈(A ∩B)X(C ∩D) 说明x ∈A ∩B,y ∈C ∩D 由于 x ∈A,y ∈C 所以 (x,y) ∈A X C 由于x ∈B,y ∈D 所以 (x,y) ∈B X D 所以 (x,y) ∈（A X C ）∩（B X D ） 反过来，如果（x,y ）∈(A X C) ∩（B X D ） 由于 (x,y) ∈（A X C ）所以 x ∈A,y ∈C 由于 (x,y) ∈（B X D ）所以x ∈B,y ∈D 所以x ∈(A ∩B) y ∈(C ∩D) 所以 (x,y) ∈(A ∩B)X(C ∩D)所以(A ∩B)X(C ∩D)= (A X C) ∩（B X D ） 1.5 解：Hasse 图φφφφφφφφφ极大元{9,24,10,7} 极小元{3,2,5,7} 最大元{24} 最小元{2}1.6 解(2)关系图为：(3)不存在最大元，最小元为{2}1.7 解：(1)R={<1,1>,<2,2>,<3,3>,<4,4>,<1,2>,<2,1>,<2,3>,<3,2>} (2)略(3)I A ⊆R 故R 是自反的。

图论习题及答案(总24页)--本页仅作为文档封面，使用时请直接删除即可----内页可以根据需求调整合适字体及大小--作业解答练习题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= { 220, 208, 198, 192, 180, 180, 165, 162, 160, 158,155, 130, 125, i122, 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= {80, 82, 85, 70, 72, 70, 66, 50, 55, 25, 50, 55, 40, 48,50, 32,i22, 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}。

二、应用题题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 。

图论习题课作业1，3，6，8，10By jgy•作业1：第一章：1,2,4,12,20,29,35•作业3：第二章：14,28,30第三章：1,5,7,8•作业6：第五章：18,33•作业8：第六章：6,12,17•作业10：第七章10 第八章5,6,8作业1|E(G)|,2|E(G)|2G υυ⎛⎫≤ ⎪⎝⎭⎛⎫⎪⎝⎭1.1 举出两个可以化成图论模型的实际问题略1.2 证明其中是单图证明：（思路）根据单图无环无重边的特点，所以 最大的情形为任意两个顶点间有一条边相连，即极 端情况为。

•1.20证明每顶皆二次的连通图是圈•证明：（思路）易证每顶皆二次的连通图中有圈。

设图中最大圈为H，假设除H外还有其他顶点集U，任取u k，因为连通，u k 与H中任意顶均有一条道路，存在H中一顶h j与u k相邻，则h j为三次。

•1.29 证明二分图的子图是二分图•方法一：•定理1.2 图G是二分图当且仅当G中无奇圈•反证：设二分图为G，子图为S，假设S非二分图，由定理1.2知S中有奇圈，则G中有奇圈，这与G是二分图矛盾。

•方法二：•（思路）定义：V(G) = X U Y, X n Y=空, 且X中任二顶不相邻，且Y中任二顶不相邻。

•证明：•(a)第一个序列考虑度数7,第二个序列考虑6,6,2•(b)将顶点v分成两部分v’和v’’•v’ = {v|v= vi , 1≤ i≤ k},•v’’ = {v|v= vi , k< I ≤ n}•以v’点为顶的原图的导出子图度数之和小于•然后考虑剩下的点贡献给这k个点的度数之和最大可能为•2.14 画出带权0.2 0.17 0.13 0.1 0.1 0.08 0.06 0.06 0.07 0.03的huffman 树•排序：①0.03 0.06 0.06 0.07 0.08 0.1 0.1 0.13 0.17 0.2•②0.06 0.07 0.08 0.090.1 0.1 0.13 0.17 0.2•③0.08 0.090.1 0.1 0.130.13 0.17 0.2•④0.1 0.10.130.13 0.170.17 0.2•⑤0.130.13 0.170.17 0.20.2•⑥0.170.17 0.20.2 0.26•⑦0.20.20.26 0.34•⑧0.26 0.34 0.4•⑨0.4 0.60.030.060.090.030.060.090.060.070.130.030.060.090.060.070.130.170.08①③②0.030.060.090.060.070.130.170.080.10.10.20.130.26Huffman 树为0.170.340.20.40.61•2.28证明T是顶数至少为2的树，则T是二分图•证明1：•定理1.2 图G是二分图当且仅当G中无奇圈•T是树，所以T中无奇圈，由‘图G是二分图当且仅当G中无奇圈’知T是二分图。

《离散数学》图论部分习题《离散数学》图论部分习题1.已知⽆向图G有12条边，6个3度顶点，其余顶点的度数均⼩于3，问G⾄少有⼏个顶点？并画出满⾜条件的⼀个图形. （24-3*6）/2 +6=92.是否存在7阶⽆向简单图G，其度序列为1、3、3、4、6、6、7.给出相应证明.不存在；7阶⽆向简单图G中最⼤度≤63.设d1、d2、…、d n为n个互不相同的正整数. 证明：不存在以d1、d2、…、d n为度序列的⽆向简单图.Max{d1，d2，…，dn}≥n，n阶⽆向简单图G中最⼤度≤n-14.求下图的补图.5.1)试画⼀个具有5个顶点的⾃补图2)是否存在具有6个顶点的⾃补图，试说明理由。

对于n阶图，原图与其补图同构，边数应相等，均为(n*(n-1)/2)/2，即n*(n-1)/4且为整数，n=4k或n=4k+1，不存在6阶⾃补图。

6.设图G为n(n>2且为奇数)阶⽆向简单图，证明：G与G的补图中奇度顶点个数相等.n(n>2且为奇数)，奇度点成对出现7.⽆向图G中只有2个奇度顶点u和v，u与v是否⼀定连通.给出说明或证明。

只有2个奇度顶点u和v，如果不连通，在u和v在2个连通分⽀上，每个分⽀上仅有⼀个奇度顶点，与握⼿引理相⽭盾。

8.图G如下图所⽰：1)写出上图的⼀个⽣成⼦图.2)δ(G)，κ(G)，λ(G).δ(G)=2，κ(G)=1，λ(G)=2.说明：δ(G)=min{ d(v) | v V } ；κ(G)=min{ |V’| |V’是图G的点割集} ；λ(G)=min{ |E’| |E’是图G的边割集} 9.在什么条件下⽆向完全图K n为欧拉图？n为奇数时10.证明：有桥的图不是欧拉图.假设是欧拉图：桥的端点是u和v，并且图各顶点度均为偶数；桥为割边，删除桥，图不再连通，u和v应该在2各不同的连通分⽀上；且u和v度数变为奇数；由于其他顶点度数均为偶数，则u和v所在的连通分⽀上只有⼀个奇度顶点，与握⼿引理⽭盾。