第四部分图论练习题

1《离散数学》第四部分---图论练习题一、选择或填空1、设G是一个哈密尔顿图，则G一定是()。(1)欧拉图(2)树(3)平面图(4)连通图2、下面给出的集合中，哪一个是前缀码？()(1){0，10，110，101111}(2){01，001，000，1}(3){b，c，aa，ab，aba}(4){1，11，101，001，0011}3、一个图的哈密尔顿路是一条通过图中()的路。4、在有向图中，结点v的出度deg+(v)表示()，入度deg-(v)表示()。5、设G是一棵树，则G的生成树有()棵。(1)0(2)1(3)2(4)不能确定6、n阶无向完全图Kn的边数是()，每个结点的度数是()。7、一棵无向树的顶点数n与边数m关系是()。8、一个图的欧拉回路是一条通过图中()的回路。9、有n个结点的树，其结点度数之和是()。10、下面给出的集合中，哪一个不是前缀码()。(1){a，ab，110，a1b11}(2){01，001，000，1}(3){1，2，00，01，0210}(4){12，11，101，002，0011}11、n个结点的有向完全图边数是()，每个结点的度数是()。12、一个无向图有生成树的充分必要条件是()。13、设G是一棵树，n,m分别表示顶点数和边数，则(1)n=m(2)m=n+1(3)n=m+1(4)不能确定。14、设T=〈V,E〉是一棵树，若|V|1，则T中至少存在()片树叶。15、任何连通无向图G至少有()棵生成树，当且仅当G是()，2G的生成树只有一棵。16、设G是有n个结点m条边的连通平面图，且有k个面，则k等于:(1)m-n+2(2)n-m-2(3)n+m-2(4)m+n+2。17、设T是一棵树，则T是一个连通且()图。答：无简单回路18、设无向图G有16条边且每个顶点的度数都是2，则图G有()个顶点。(1)10(2)4(3)8(4)1619、设无向图G有18条边且每个顶点的度数都是3，则图G有()个顶点。(1)10(2)4(3)8(4)1220、设图G=V，E，V={a，b，c，d，e}，E={a,b,a,c,b,c,c,d,d,e},则G是有向图还是无向图？21、任一有向图中，度数为奇数的结点有()个。22、具有6个顶点，12条边的连通简单平面图中，每个面都是由()条边围成？(1)2(2)4(3)3(4)523、在有n个顶点的连通图中，其边数（）。(1)最多有n-1条(2)至少有n-1条(3)最多有n条(4)至少有n条24、一棵树有2个2度顶点，1个3度顶点，3个4度顶点，则其1度顶点为（）。(1)5(2)7(3)8(4)925、若一棵完全二元（叉）树有2n-1个顶点，则它（）片树叶。(1)n(2)2n(3)n-1(4)226、下列哪一种图不一定是树（）。(1)无简单回路的连通图(2)有n个顶点n-1条边的连通图(3)每对顶点间都有通路的图(4)连通但删去一条边便不连通的图327、连通图G是一棵树当且仅当G中（）。(1)有些边是割边(2)每条边都是割边(3)所有边都不是割边(4)图中存在一条欧拉路径二、证明或解答题1、证明在有n个结点的树中，其结点度数之和是2n-2。证明：2、任一图中度数为奇数的结点是偶数个。证明：3、连通无向图G的任何边一定是G的某棵生成树的弦。这个断言对吗？若是对的请证明之，否则请举例说明。证明：44、设T=V,E是一棵树，若|V|1，则T中至少存在两片树叶。证明：5、画一个使它分别满足：(1)有欧拉回路和哈密尔顿回路；(2)有欧拉回路，但无条哈密尔顿回路；(3)无欧拉回路，但有哈密尔顿回路；(4)既无欧拉回路，又无哈密尔顿回路。解6、设无向图G=V,E，|E|=12。已知有6个3度顶点，其他顶点的度数均小于3。问G中至少有多少个顶点？解：57、设图G=V,E，|V|=n，|E|=m。k度顶点有nk个，且每个顶点或是k度顶点或是k+1度顶点。证明：nk=(k+1)-2m。证明：8、设G=V,E是一个连通且|V|=|E|+1的图，则G中有一个度为1的结点。证明：9、若n阶连通图中恰有n-1条边，则图中至少有一个结点度数为1。证明：610、若G有n个结点，m条边，f个面，且每个面至少由k(k3)条边围成，则mk(ｎ－2)／(ｋ－2)。证明：11、设G=V,E是连通的简单平面图，|V|=n3，面数为k,则k2n-4。证明：12、证明对于连通无向简单平面图，当边数e＜30时，必存在度数≤4的顶点。证明：713、在一个连通简单无向平面图G=〈V，E，F〉中若|V|3，则|E|3|V|－6。证明：14、给定连通简单平面图G=V,E,F，且|V|=6,|E|=12,则对于任意fF,d(f)=3。证明：15、设G=V,E是n个顶点的无向图(n2)，若对任意u,vV，有d(u)+d(v)n，则G是连通图。证明：816、一次会议有20人参加，其中每个人都在其中有不下10个朋友。这20人围成一圆桌入席。有没有可能使任意相邻而坐的两个人都是朋友？为什么？证明：17、证明在任何两个或两个以上人的组内，存在两个人在组内有相同个数的朋友。证明：918、设有如下有向图G=V,E，（1）求G的邻接矩阵；（2）G中v1到v4的长度为4的通路有多少条？（3）G中经过v1的长度为3的回路有多少条？（4）G中长度不超过4的通路有多少条？其中有多少条通路？解：19、求下列无向图中每个顶点的度数；求下列有向图中每个顶点的出度、入度和度。解：1020、求下列无向图的子图、生成子图、由边集诱导的子图和由顶点集诱导的子图。解：21、求下列赋权图顶点间的距离。dae43571cb14f解1122、求下列赋权图中v1到其他顶点的距离。v210v43v1226434v6v32v523、求下图的可达矩阵。daebc解：1224、求下列图的生成树。解：25、已知一棵无向树中有2个2度顶点、1个3度顶点、3个4度顶点，其余顶点度数都为1。问它有多少个1度顶点？解：