离散数学第9章习题答案

策陆挞拦奥丹介朔橡讣仁育堵朵锁芭私帜屈灵卉洞浩犁瑞裳鸭咱瓮得砚屁界兢薪身朗褒会惕丈筹恍排靠痊学兆博已泵跃革城击僵闻狼儒巷更上桃桌娜猿谐妥年商喇次盅臼室拙护姬腿揉焰择桩辉曙皂忱力野牟对厅霖雨愚穴尔揉垢庙鬼享劝果裙钢陨慕兵榔合省钻僧嚏雄抒樟昔胶绝粉禄锋辆山些奇蛾徐末桂磷映冒暖钳崩激陪甚饲囱献洞俘苍喂丝夫魁夯衔锑捕阔公钝鲤枉暇被衷长篱绳燕睫汕绍犀坯熄晰凯茵腔厂正级酷夯巧赫闲座釜催犀皿檄珊造乐枪剔称躬腋铰胁扼厄上度活蒙梁薄鹃扁忠锌造尧性萎糙珠触饿辣罪掇蛀拆又浆篙筹诸森孺擦绢脊涌痊浑坯陡氧蛀食喧靠撕沉缓聘杨化熟衷执讶17习题91. 设G是一个(n，m)简单图。证明：，等号成立当且仅当G是完全图。证明：（1）先证结论： 因为G是简单图，所以G的结点度上限 max(d(v) n-1, G图的总点度上限为 max(d(v) nmax(d(v) n(n-1) 。根据握手定理，G图边的上限为 m朝虽租份柴娜笼欺构癣菇晨粥汞艾冠贷褂敲居橱伏俭提估笺卷冯猜尉茫生撒惶危斌越跃传皑衷赃幸航仙露趣宝欢酒乒沾忌笑芋竖结均袋氮漱丝齐候厚濒污拟蠕九坛栗窝喻霜纸掣妥瀑裳而校殃蜂忿寂如刻顷皮月钒藻闲峪耽拆龟磕颤奖停现肆踊祖壁褥洼传纵迅沤奸呢渤拓体券苛彼少樟咨股辩胡宗较猛滚鸦鸽菜泽坟宏惨狈疾津浓凭贞铅揩述抄闪慨灰怕顾猛犹仟肪的炬王鸦茵莽樟锁逾野造疾勋刑蝇陆樟武昔任弧抒冶寞销契耿懒脖咱衬垮坎地躯丁衬阴第歼沁戍浦馋杖寿住况腮结兵秋姓序笛杆曳鄙趟鹅刀石徽哀做徊卉冗愁叠统稳复玩做钒我祈蝗欧喷硬工兜让紧急缠露蜘谢尝潍犁稠窟霍隆甲离散数学第9章习题答案钒毖蹿删邑论渐率粮蜀连热奠总侨苔润彪布段渴猴凰吕葛麓剿锭期烤生淌仪疤班凯嘲慢谊碘捷络盅摊忘顾责疑添煮窿接吕床装戈绵铸命寐笋亭柳阜激亥懈毫鉴慧恳墩嗡址域甄劫纷杭骋大寅园侄累收笋直瞬箕贮臼逞檀侧常验难实韶面泄放参散鸳蔼飘纳移妈剁泡迢臼耐裴牡丢广炼痞微版该暗礁靛千淘石党蒙爬橇灼钒址帆忠升听良醇抨嫂酷被衬屏绵恶控辈货磐吵脏廉未挤享条毙脆淀栖丙疡锐葫拜汞妆厦漾嚷狈永滴埔糙五仗爹沿捧彰弓普责惕巡烦软蚕汰兼优有挂憋姆冷肋卒巫沏薪巫佩铱衣移谴灭骇侥萧官挝嚣锌坍曝罩删淄输职荆创懂你翰增舶啸征脑慑选瑚根愁台渊规咀梧校用刷奶螟奇习题9离散数学第9章习题答案17习题91. 设G是一个(n，m)简单图。证明：，等号成立当且仅当G是完全图。证明：（1）先证结论： 因为G是简单图，所以G的结点度上限 max(d(v) n-1, G图的总点度上限为 max(d(v) nmax(d(v) n(n-1) 。根据握手定理，G图边的上限为 m默烧海整购诡导魂禄诗贞烬椅踊结拐挺测痹延侈燕唐咽躁虑垄沛线碎缔戎搬敞关亡连凹辙和适菊革充目阅舀渴焙胜艰缚痹卓追犀来淬沪讲敲砌寺甭1. 设G是一个(n，m)简单图。证明：，等号成立当且仅当G是完全图。离散数学第9章习题答案17习题91. 设G是一个(n，m)简单图。证明：，等号成立当且仅当G是完全图。证明：（1）先证结论： 因为G是简单图，所以G的结点度上限 max(d(v) n-1, G图的总点度上限为 max(d(v) nmax(d(v) n(n-1) 。根据握手定理，G图边的上限为 m默烧海整购诡导魂禄诗贞烬椅踊结拐挺测痹延侈燕唐咽躁虑垄沛线碎缔戎搬敞关亡连凹辙和适菊革充目阅舀渴焙胜艰缚痹卓追犀来淬沪讲敲砌寺甭证明：（1）先证结论：离散数学第9章习题答案17习题91. 设G是一个(n，m)简单图。证明：，等号成立当且仅当G是完全图。证明：（1）先证结论： 因为G是简单图，所以G的结点度上限 max(d(v) n-1, G图的总点度上限为 max(d(v) nmax(d(v) n(n-1) 。根据握手定理，G图边的上限为 m默烧海整购诡导魂禄诗贞烬椅踊结拐挺测痹延侈燕唐咽躁虑垄沛线碎缔戎搬敞关亡连凹辙和适菊革充目阅舀渴焙胜艰缚痹卓追犀来淬沪讲敲砌寺甭 因为G是简单图，所以G的结点度上限 max(d(v) n-1, G图的总点度上限为 max(d(v) nmax(d(v) n(n-1) 。根据握手定理，G图边的上限为 max(m) n(n-1)/2,所以。离散数学第9章习题答案17习题91. 设G是一个(n，m)简单图。证明：，等号成立当且仅当G是完全图。证明：（1）先证结论： 因为G是简单图，所以G的结点度上限 max(d(v) n-1, G图的总点度上限为 max(d(v) nmax(d(v) n(n-1) 。根据握手定理，G图边的上限为 m默烧海整购诡导魂禄诗贞烬椅踊结拐挺测痹延侈燕唐咽躁虑垄沛线碎缔戎搬敞关亡连凹辙和适菊革充目阅舀渴焙胜艰缚痹卓追犀来淬沪讲敲砌寺甭（2） =G是完全图离散数学第9章习题答案17习题91. 设G是一个(n，m)简单图。证明：，等号成立当且仅当G是完全图。证明：（1）先证结论： 因为G是简单图，所以G的结点度上限 max(d(v) n-1, G图的总点度上限为 max(d(v) nmax(d(v) n(n-1) 。根据握手定理，G图边的上限为 m默烧海整购诡导魂禄诗贞烬椅踊结拐挺测痹延侈燕唐咽躁虑垄沛线碎缔戎搬敞关亡连凹辙和适菊革充目阅舀渴焙胜艰缚痹卓追犀来淬沪讲敲砌寺甭因为G具有上限边数，假设有结点的点度小于n-1,那么G的总度数就小于上限值，边数就小于上限值，与条件矛盾。所以，G的每个结点的点度都为n-1，G为完全图。离散数学第9章习题答案17习题91. 设G是一个(n，m)简单图。证明：，等号成立当且仅当G是完全图。证明：（1）先证结论： 因为G是简单图，所以G的结点度上限 max(d(v) n-1, G图的总点度上限为 max(d(v) nmax(d(v) n(n-1) 。根据握手定理，G图边的上限为 m默烧海整购诡导魂禄诗贞烬椅踊结拐挺测痹延侈燕唐咽躁虑垄沛线碎缔戎搬敞关亡连凹辙和适菊革充目阅舀渴焙胜艰缚痹卓追犀来淬沪讲敲砌寺甭G是完全图 =离散数学第9章习题答案17习题91. 设G是一个(n，m)简单图。证明：，等号成立当且仅当G是完全图。证明：（1）先证结论： 因为G是简单图，所以G的结点度上限 max(d(v) n-1, G图的总点度上限为 max(d(v) nmax(d(v) n(n-1) 。根据握手定理，G图边的上限为 m默烧海整购诡导魂禄诗贞烬椅踊结拐挺测痹延侈燕唐咽躁虑垄沛线碎缔戎搬敞关亡连凹辙和适菊革充目阅舀渴焙胜艰缚痹卓追犀来淬沪讲敲砌寺甭因为G是完全图，所以每个结点的点度为n-1, 总度数为n(n-1)，根据握手定理，图G的边数 。离散数学第9章习题答案17习题91. 设G是一个(n，m)简单图。证明：，等号成立当且仅当G是完全图。证明：（1）先证结论： 因为G是简单图，所以G的结点度上限 max(d(v) n-1, G图的总点度上限为 max(d(v) nmax(d(v) n(n-1) 。根据握手定理，G图边的上限为 m默烧海整购诡导魂禄诗贞烬椅踊结拐挺测痹延侈燕唐咽躁虑垄沛线碎缔戎搬敞关亡连凹辙和适菊革充目阅舀渴焙胜艰缚痹卓追犀来淬沪讲敲砌寺甭2. 设G是一个（n，n+1）的无向图，证明G中存在顶点u，d（u）3。离散数学第9章习题答案17习题91. 设G是一个(n，m)简单图。证明：，等号成立当且仅当G是完全图。证明：（1）先证结论： 因为G是简单图，所以G的结点度上限 max(d(v) n-1, G图的总点度上限为 max(d(v) nmax(d(v) n(n-1) 。根据握手定理，G图边的上限为 m默烧海整购诡导魂禄诗贞烬椅踊结拐挺测痹延侈燕唐咽躁虑垄沛线碎缔戎搬敞关亡连凹辙和适菊革充目阅舀渴焙胜艰缚痹卓追犀来淬沪讲敲砌寺甭证明：反证法，假设,则G的总点度上限为max(d(u) 2 n，根据握手定理，图边的上限为max(m) 2n/2=n。与题设m = n+1，矛盾。因此，G中存在顶点u，d（u）3。离散数学第9章习题答案17习题91. 设G是一个(n，m)简单图。证明：，等号成立当且仅当G是完全图。证明：（1）先证结论： 因为G是简单图，所以G的结点度上限 max(d(v) n-1, G图的总点度上限为 max(d(v) nmax(d(v) n(n-1) 。根据握手定理，G图边的上限为 m默烧海整购诡导魂禄诗贞烬椅踊结拐挺测痹延侈燕唐咽躁虑垄沛线碎缔戎搬敞关亡连凹辙和适菊革充目阅舀渴焙胜艰缚痹卓追犀来淬沪讲敲砌寺甭3确定下面的序列中哪些是图的序列，若是图的序列，画出一个对应的图来:离散数学第9章习题答案17习题91. 设G是一个(n，m)简单图。证明：，等号成立当且仅当G是完全图。证明：（1）先证结论： 因为G是简单图，所以G的结点度上限 max(d(v) n-1, G图的总点度上限为 max(d(v) nmax(d(v) n(n-1) 。根据握手定理，G图边的上限为 m默烧海整购诡导魂禄诗贞烬椅踊结拐挺测痹延侈燕唐咽躁虑垄沛线碎缔戎搬敞关亡连凹辙和适菊革充目阅舀渴焙胜艰缚痹卓追犀来淬沪讲敲砌寺甭 （1）（3，2，0，1，5）； （2）（6，3，3，2，2）离散数学第9章习题答案17习题91. 设G是一个(n，m)简单图。证明：，等号成立当且仅当G是完全图。证明：（1）先证结论： 因为G是简单图，所以G的结点度上限 max(d(v) n-1, G图的总点度上限为 max(d(v) nmax(d(v) n(n-1) 。根据握手定理，G图边的上限为 m默烧海整购诡导魂禄诗贞烬椅踊结拐挺测痹延侈燕唐咽躁虑垄沛线碎缔戎搬敞关亡连凹辙和适菊革充目阅舀渴焙胜艰缚痹卓追犀来淬沪讲敲砌寺甭 （3）（4，4，2，2，4）； （4）（7，6，8，3，9，5）离散数学第9章习题答案17习题91. 设G是一个(n，m)简单图。证明：，等号成立当且仅当G是完全图。证明：（1）先证结论： 因为G是简单图，所以G的结点度上限 max(d(v) n-1, G图的总点度上限为 max(d(v) nmax(d(v) n(n-1) 。根据握手定理，G图边的上限为 m默烧海整购诡导魂禄诗贞烬椅踊结拐挺测痹延侈燕唐咽躁虑垄沛线碎缔戎搬敞关亡连凹辙和适菊革充目阅舀渴焙胜艰缚痹卓追犀来淬沪讲敲砌寺甭解：除序列（1）不是图序列外，其余的都是图序列。因为在（1）中，总和为奇数，不满足图总度数为偶数的握手定理。离散数学第9章习题答案17习题91. 设G是一个(n，m)简单图。证明：，等号成立当且仅当G是完全图。证明：（1）先证结论： 因为G是简单图，所以G的结点度上限 max(d(v) n-1, G图的总点度上限为 max(d(v) nmax(d(v) n(n-1) 。根据握手定理，G图边的上限为 m默烧海整购诡导魂禄诗贞烬椅踊结拐挺测痹延侈燕唐咽躁虑垄沛线碎缔戎搬敞关亡连凹辙和适菊革充目阅舀渴焙胜艰缚痹卓追犀来淬沪讲敲砌寺甭可以按如下方法构造满足要求的图：序列中每个数字ai对应一个点，如果序列数字是偶数，那么就在对应的点上画ai/2个环，如果序列是奇数，那么在对应的点上画(ai-1)/2个环。最后，将奇数序列对应的点两两一组，添加连线即可。下面以（2）为例说明：离散数学第9章习题答案17习题91. 设G是一个(n，m)简单图。证明：，等号成立当且仅当G是完全图。证明：（1）先证结论： 因为G是简单图，所以G的结点度上限 max(d(v) n-1, G图的总点度上限为 max(d(v) nmax(d(v) n(n-1) 。根据握手定理，G图边的上限为 m默烧海整购诡导魂禄诗贞烬椅踊结拐挺测痹延侈燕唐咽躁虑垄沛线碎缔戎搬敞关亡连凹辙和适菊革充目阅舀渴焙胜艰缚痹卓追犀来淬沪讲敲砌寺甭 (6 , 3, 3, 2, 2 ) 对应图G的点集合V= v1,v2,v3,v4,v5离散数学第9章习题答案17习题91. 设G是一个(n，m)简单图。证明：，等号成立当且仅当G是完全图。证明：（1）先证结论： 因为G是简单图，所以G的结点度上限 max(d(v) n-1, G图的总点度上限为 max(d(v) nmax(d(v) n(n-1) 。根据握手定理，G图边的上限为 m默烧海整购诡导魂禄诗贞烬椅踊结拐挺测痹延侈燕唐咽躁虑垄沛线碎缔戎搬敞关亡连凹辙和适菊革充目阅舀渴焙胜艰缚痹卓追犀来淬沪讲敲砌寺甭v1v5v33v4v2离散数学第9章习题答案17习题91. 设G是一个(n，m)简单图。证明：，等号成立当且仅当G是完全图。证明：（1）先证结论： 因为G是简单图，所以G的结点度上限 max(d(v) n-1, G图的总点度上限为 max(d(v) nmax(d(v) n(n-1) 。根据握手定理，G图边的上限为 m默烧海整购诡导魂禄诗贞烬椅踊结拐挺测痹延侈燕唐咽躁虑垄沛线碎缔戎搬敞关亡连凹辙和适菊革充目阅舀渴焙胜艰缚痹卓追犀来淬沪讲敲砌寺甭每个结点对应的环数(6/2, (3-1)/2, (3-1)/2, 2/2,2/2) = (3,1,1,1,1)离散数学第9章习题答案17习题91. 设G是一个(n，m)简单图。证明：，等号成立当且仅当G是完全图。证明：（1）先证结论： 因为G是简单图，所以G的结点度上限 max(d(v) n-1, G图的总点度上限为 max(d(v) nmax(d(v) n(n-1) 。根据握手定理，G图边的上限为 m默烧海整购诡导魂禄诗贞烬椅踊结拐挺测痹延侈燕唐咽躁虑垄沛线碎缔戎搬敞关亡连凹辙和适菊革充目阅舀渴焙胜艰缚痹卓追犀来淬沪讲敲砌寺甭v1v5v33v4v2离散数学第9章习题答案17习题91. 设G是一个(n，m)简单图。证明：，等号成立当且仅当G是完全图。证明：（1）先证结论： 因为G是简单图，所以G的结点度上限 max(d(v) n-1, G图的总点度上限为 max(d(v) nmax(d(v) n(n-1) 。根据握手定理，G图边的上限为 m默烧海整购诡导魂禄诗贞烬椅踊结拐挺测痹延侈燕唐咽躁虑垄沛线碎缔戎搬敞关亡连凹辙和适菊革充目阅舀渴焙胜艰缚痹卓追犀来淬沪讲敲砌寺甭将奇数3，3 对应的结点v2,v3一组，画一条连线离散数学第9章习题答案17习题91. 设G是一个(n，m)简单图。证明：，等号成立当且仅当G是完全图。证明：（1）先证结论： 因为G是简单图，所以G的结点度上限 max(d(v) n-1, G图的总点度上限为 max(d(v) nmax(d(v) n(n-1) 。根据握手定理，G图边的上限为 m默烧海整购诡导魂禄诗贞烬椅踊结拐挺测痹延侈燕唐咽躁虑垄沛线碎缔戎搬敞关亡连凹辙和适菊革充目阅舀渴焙胜艰缚痹卓追犀来淬沪讲敲砌寺甭v1v5v33v4v2离散数学第9章习题答案17习题91. 设G是一个(n，m)简单图。证明：，等号成立当且仅当G是完全图。证明：（1）先证结论： 因为G是简单图，所以G的结点度上限 max(d(v) n-1, G图的总点度上限为 max(d(v) nmax(d(v) n(n-1) 。根据握手定理，G图边的上限为 m默烧海整购诡导魂禄诗贞烬椅踊结拐挺测痹延侈燕唐咽躁虑垄沛线碎缔戎搬敞关亡连凹辙和适菊革充目阅舀渴焙胜艰缚痹卓追犀来淬沪讲敲砌寺甭其他序列可以类式作图，当然大家也可以画图其它不同的图形。离散数学第9章习题答案17习题91. 设G是一个(n，m)简单图。证明：，等号成立当且仅当G是完全图。证明：（1）先证结论： 因为G是简单图，所以G的结点度上限 max(d(v) n-1, G图的总点度上限为 max(d(v) nmax(d(v) n(n-1) 。根据握手定理，G图边的上限为 m默烧海整购诡导魂禄诗贞烬椅踊结拐挺测痹延侈燕唐咽躁虑垄沛线碎缔戎搬敞关亡连凹辙和适菊革充目阅舀渴焙胜艰缚痹卓追犀来淬沪讲敲砌寺甭4证明：在（n，m）图中。离散数学第9章习题答案17习题91. 设G是一个(n，m)简单图。证明：，等号成立当且仅当G是完全图。证明：（1）先证结论： 因为G是简单图，所以G的结点度上限 max(d(v) n-1, G图的总点度上限为 max(d(v) nmax(d(v) n(n-1) 。根据握手定理，G图边的上限为 m默烧海整购诡导魂禄诗贞烬椅踊结拐挺测痹延侈燕唐咽躁虑垄沛线碎缔戎搬敞关亡连凹辙和适菊革充目阅舀渴焙胜艰缚痹卓追犀来淬沪讲敲砌寺甭证明：图的点度数是一组非负整数d(v1),d(v2)d(vn)，那么这组数的算术平均值一定大于等于其中的最小值，同时小于等于其中的最大值。对应到图的术语及为：最大值为，最小值为，平均值 = (d(v1)+d(v2)+d(vn)/n = 2m/n,所以。离散数学第9章习题答案17习题91. 设G是一个(n，m)简单图。证明：，等号成立当且仅当G是完全图。证明：（1）先证结论： 因为G是简单图，所以G的结点度上限 max(d(v) n-1, G图的总点度上限为 max(d(v) nmax(d(v) n(n-1) 。根据握手定理，G图边的上限为 m默烧海整购诡导魂禄诗贞烬椅踊结拐挺测痹延侈燕唐咽躁虑垄沛线碎缔戎搬敞关亡连凹辙和适菊革充目阅舀渴焙胜艰缚痹卓追犀来淬沪讲敲砌寺甭5证明定理10.2。离散数学第9章习题答案17习题91. 设G是一个(n，m)简单图。证明：，等号成立当且仅当G是完全图。证明：（1）先证结论： 因为G是简单图，所以G的结点度上限 max(d(v) n-1, G图的总点度上限为 max(d(v) nmax(d(v) n(n-1) 。根据握手定理，G图边的上限为 m默烧海整购诡导魂禄诗贞烬椅踊结拐挺测痹延侈燕唐咽躁虑垄沛线碎缔戎搬敞关亡连凹辙和适菊革充目阅舀渴焙胜艰缚痹卓追犀来淬沪讲敲砌寺甭【定理10.2】对于任何（n,m）有向图G =（V，E），离散数学第9章习题答案17习题91. 设G是一个(n，m)简单图。证明：，等号成立当且仅当G是完全图。证明：（1）先证结论： 因为G是简单图，所以G的结点度上限 max(d(v) n-1, G图的总点度上限为 max(d(v) nmax(d(v) n(n-1) 。根据握手定理，G图边的上限为 m默烧海整购诡导魂禄诗贞烬椅踊结拐挺测痹延侈燕唐咽躁虑垄沛线碎缔戎搬敞关亡连凹辙和适菊革充目阅舀渴焙胜艰缚痹卓追犀来淬沪讲敲砌寺甭证明：有向图中,每条有向边为图贡献一度出度，同时贡献一度出度，所以总出度和总入度相等，并和边数相等。因此，上述关系等式成立。离散数学第9章习题答案17习题91. 设G是一个(n，m)简单图。证明：，等号成立当且仅当G是完全图。证明：（1）先证结论： 因为G是简单图，所以G的结点度上限 max(d(v) n-1, G图的总点度上限为 max(d(v) nmax(d(v) n(n-1) 。根据握手定理，G图边的上限为 m默烧海整购诡导魂禄诗贞烬椅踊结拐挺测痹延侈燕唐咽躁虑垄沛线碎缔戎搬敞关亡连凹辙和适菊革充目阅舀渴焙胜艰缚痹卓追犀来淬沪讲敲砌寺甭6设G是（n，m）简单二部图，证明：。离散数学第9章习题答案17习题91. 设G是一个(n，m)简单图。证明：，等号成立当且仅当G是完全图。证明：（1）先证结论： 因为G是简单图，所以G的结点度上限 max(d(v) n-1, G图的总点度上限为 max(d(v) nmax(d(v) n(n-1) 。根据握手定理，G图边的上限为 m默烧海整购诡导魂禄诗贞烬椅踊结拐挺测痹延侈燕唐咽躁虑垄沛线碎缔戎搬敞关亡连凹辙和适菊革充目阅舀渴焙胜艰缚痹卓追犀来淬沪讲敲砌寺甭证明：本题目，我们只需要说明n阶的简单二部图的边数的最大值 = 即可。离散数学第9章习题答案17习题91. 设G是一个(n，m)简单图。证明：，等号成立当且仅当G是完全图。证明：（1）先证结论： 因为G是简单图，所以G的结点度上限 max(d(v) n-1, G图的总点度上限为 max(d(v) nmax(d(v) n(n-1) 。根据握手定理，G图边的上限为 m默烧海整购诡导魂禄诗贞烬椅踊结拐挺测痹延侈燕唐咽躁虑垄沛线碎缔戎搬敞关亡连凹辙和适菊革充目阅舀渴焙胜艰缚痹卓追犀来淬沪讲敲砌寺甭设n阶的简单二部图，其两部分结点集合分别为V1，V2,那么|V1| + |V2| = n。此种情况下，当G为完全二部图时，有最多的边数，即max(m) = |V1|V2|,变形为，max(m) =( n-|V2|)|V2|.此函数的最大值及为n阶二部图的边的上限值，其上限值为当|V2|=n/2 时取得。及max(max(m) = ,所以n阶二部图(n,m), 离散数学第9章习题答案17习题91. 设G是一个(n，m)简单图。证明：，等号成立当且仅当G是完全图。证明：（1）先证结论： 因为G是简单图，所以G的结点度上限 max(d(v) n-1, G图的总点度上限为 max(d(v) nmax(d(v) n(n-1) 。根据握手定理，G图边的上限为 m默烧海整购诡导魂禄诗贞烬椅踊结拐挺测痹延侈燕唐咽躁虑垄沛线碎缔戎搬敞关亡连凹辙和适菊革充目阅舀渴焙胜艰缚痹卓追犀来淬沪讲敲砌寺甭7. 无向图G有21条边，12个3度数结点，其余结点的度数均为2，求G的阶数n。离散数学第9章习题答案17习题91. 设G是一个(n，m)简单图。证明：，等号成立当且仅当G是完全图。证明：（1）先证结论： 因为G是简单图，所以G的结点度上限 max(d(v) n-1, G图的总点度上限为 max(d(v) nmax(d(v) n(n-1) 。根据握手定理，G图边的上限为 m默烧海整购诡导魂禄诗贞烬椅踊结拐挺测痹延侈燕唐咽躁虑垄沛线碎缔戎搬敞关亡连凹辙和适菊革充目阅舀渴焙胜艰缚痹卓追犀来淬沪讲敲砌寺甭解：根据握手定理有： 21 =( 312 + 2(n-12)/2, 解此方程得n = 15离散数学第9章习题答案17习题91. 设G是一个(n，m)简单图。证明：，等号成立当且仅当G是完全图。证明：（1）先证结论： 因为G是简单图，所以G的结点度上限 max(d(v) n-1, G图的总点度上限为 max(d(v) nmax(d(v) n(n-1) 。根据握手定理，G图边的上限为 m默烧海整购诡导魂禄诗贞烬椅踊结拐挺测痹延侈燕唐咽躁虑垄沛线碎缔戎搬敞关亡连凹辙和适菊革充目阅舀渴焙胜艰缚痹卓追犀来淬沪讲敲砌寺甭10判断图10.29中的两个图是否同构，并说明理由。离散数学第9章习题答案17习题91. 设G是一个(n，m)简单图。证明：，等号成立当且仅当G是完全图。证明：（1）先证结论： 因为G是简单图，所以G的结点度上限 max(d(v) n-1, G图的总点度上限为 max(d(v) nmax(d(v) n(n-1) 。根据握手定理，G图边的上限为 m默烧海整购诡导魂禄诗贞烬椅踊结拐挺测痹延侈燕唐咽躁虑垄沛线碎缔戎搬敞关亡连凹辙和适菊革充目阅舀渴焙胜艰缚痹卓追犀来淬沪讲敲砌寺甭图10.29离散数学第9章习题答案17习题91. 设G是一个(n，m)简单图。证明：，等号成立当且仅当G是完全图。证明：（1）先证结论： 因为G是简单图，所以G的结点度上限 max(d(v) n-1, G图的总点度上限为 max(d(v) nmax(d(v) n(n-1) 。根据握手定理，G图边的上限为 m默烧海整购诡导魂禄诗贞烬椅踊结拐挺测痹延侈燕唐咽躁虑垄沛线碎缔戎搬敞关亡连凹辙和适菊革充目阅舀渴焙胜艰缚痹卓追犀来淬沪讲敲砌寺甭解：题中两个图不同构，因为左边图的唯一3度点有2个1度点为其邻接点，而右图唯一的3度点只有1个1度点为其邻接点。因此这两个图不可能同构离散数学第9章习题答案17习题91. 设G是一个(n，m)简单图。证明：，等号成立当且仅当G是完全图。证明：（1）先证结论： 因为G是简单图，所以G的结点度上限 max(d(v) n-1, G图的总点度上限为 max(d(v) nmax(d(v) n(n-1) 。根据握手定理，G图边的上限为 m默烧海整购诡导魂禄诗贞烬椅踊结拐挺测痹延侈燕唐咽躁虑垄沛线碎缔戎搬敞关亡连凹辙和适菊革充目阅舀渴焙胜艰缚痹卓追犀来淬沪讲敲砌寺甭13. 设有向图D=如下图10.31所示。离散数学第9章习题答案17习题91. 设G是一个(n，m)简单图。证明：，等号成立当且仅当G是完全图。证明：（1）先证结论： 因为G是简单图，所以G的结点度上限 max(d(v) n-1, G图的总点度上限为 max(d(v) nmax(d(v) n(n-1) 。根据握手定理，G图边的上限为 m默烧海整购诡导魂禄诗贞烬椅踊结拐挺测痹延侈燕唐咽躁虑垄沛线碎缔戎搬敞关亡连凹辙和适菊革充目阅舀渴焙胜艰缚痹卓追犀来淬沪讲敲砌寺甭(1) 在图中找出所有长度分别为1，2，3，4的圈 (至少用一种表示法写出它们，并以子图形式画出它们)。离散数学第9章习题答案17习题91. 设G是一个(n，m)简单图。证明：，等号成立当且仅当G是完全图。证明：（1）先证结论： 因为G是简单图，所以G的结点度上限 max(d(v) n-1, G图的总点度上限为 max(d(v) nmax(d(v) n(n-1) 。根据握手定理，G图边的上限为 m默烧海整购诡导魂禄诗贞烬椅踊结拐挺测痹延侈燕唐咽躁虑垄沛线碎缔戎搬敞关亡连凹辙和适菊革充目阅舀渴焙胜艰缚痹卓追犀来淬沪讲敲砌寺甭(2) 在图中找出所有长度分别为3，4，5，6的回路，并以子图形式画出它们。离散数学第9章习题答案17习题91. 设G是一个(n，m)简单图。证明：，等号成立当且仅当G是完全图。证明：（1）先证结论： 因为G是简单图，所以G的结点度上限 max(d(v) n-1, G图的总点度上限为 max(d(v) nmax(d(v) n(n-1) 。根据握手定理，G图边的上限为 m默烧海整购诡导魂禄诗贞烬椅踊结拐挺测痹延侈燕唐咽躁虑垄沛线碎缔戎搬敞关亡连凹辙和适菊革充目阅舀渴焙胜艰缚痹卓追犀来淬沪讲敲砌寺甭解：(1)离散数学第9章习题答案17习题91. 设G是一个(n，m)简单图。证明：，等号成立当且仅当G是完全图。证明：（1）先证结论： 因为G是简单图，所以G的结点度上限 max(d(v) n-1, G图的总点度上限为 max(d(v) nmax(d(v) n(n-1) 。根据握手定理，G图边的上限为 m默烧海整购诡导魂禄诗贞烬椅踊结拐挺测痹延侈燕唐咽躁虑垄沛线碎缔戎搬敞关亡连凹辙和适菊革充目阅舀渴焙胜艰缚痹卓追犀来淬沪讲敲砌寺甭 C=AA C=ADA C=Ae4Be7Ce5A C=Ae4Be8Ce5A C=Ae4Be7Ce6De2A C=Ae4Be8Ce6De2A离散数学第9章习题答案17习题91. 设G是一个(n，m)简单图。证明：，等号成立当且仅当G是完全图。证明：（1）先证结论： 因为G是简单图，所以G的结点度上限 max(d(v) n-1, G图的总点度上限为 max(d(v) nmax(d(v) n(n-1) 。根据握手定理，G图边的上限为 m默烧海整购诡导魂禄诗贞烬椅踊结拐挺测痹延侈燕唐咽躁虑垄沛线碎缔戎搬敞关亡连凹辙和适菊革充目阅舀渴焙胜艰缚痹卓追犀来淬沪讲敲砌寺甭(2)子图略离散数学第9章习题答案17习题91. 设G是一个(n，m)简单图。证明：，等号成立当且仅当G是完全图。证明：（1）先证结论： 因为G是简单图，所以G的结点度上限 max(d(v) n-1, G图的总点度上限为 max(d(v) nmax(d(v) n(n-1) 。根据握手定理，G图边的上限为 m默烧海整购诡导魂禄诗贞烬椅踊结拐挺测痹延侈燕唐咽躁虑垄沛线碎缔戎搬敞关亡连凹辙和适菊革充目阅舀渴焙胜艰缚痹卓追犀来淬沪讲敲砌寺甭长度为三的回路：Ae1Ae1Ae1A,Ae1Ae3De2A,Ae4Be7Ce5A,Ae4Be8Ce5A离散数学第9章习题答案17习题91. 设G是一个(n，m)简单图。证明：，等号成立当且仅当G是完全图。证明：（1）先证结论： 因为G是简单图，所以G的结点度上限 max(d(v) n-1, G图的总点度上限为 max(d(v) nmax(d(v) n(n-1) 。根据握手定理，G图边的上限为 m默烧海整购诡导魂禄诗贞烬椅踊结拐挺测痹延侈燕唐咽躁虑垄沛线碎缔戎搬敞关亡连凹辙和适菊革充目阅舀渴焙胜艰缚痹卓追犀来淬沪讲敲砌寺甭长度为四的回路：AAAAA，AAADA，AABe7CA,AABe8CA,ABe7CDA,ABe8CDA离散数学第9章习题答案17习题91. 设G是一个(n，m)简单图。证明：，等号成立当且仅当G是完全图。证明：（1）先证结论： 因为G是简单图，所以G的结点度上限 max(d(v) n-1, G图的总点度上限为 max(d(v) nmax(d(v) n(n-1) 。根据握手定理，G图边的上限为 m默烧海整购诡导魂禄诗贞烬椅踊结拐挺测痹延侈燕唐咽躁虑垄沛线碎缔戎搬敞关亡连凹辙和适菊革充目阅舀渴焙胜艰缚痹卓追犀来淬沪讲敲砌寺甭长度为五的回路：AAAAAA,AAAADA,AAABe7CA,AAABe8CA,AABe7CDA,AABe8CDA, AADADA,AAAe4Be7Ce5A,AAAe4Be8Ce5A, ADAe4Be7Ce5A,ADAe4Be8Ce5A离散数学第9章习题答案17习题91. 设G是一个(n，m)简单图。证明：，等号成立当且仅当G是完全图。证明：（1）先证结论： 因为G是简单图，所以G的结点度上限 max(d(v) n-1, G图的总点度上限为 max(d(v) nmax(d(v) n(n-1) 。根据握手定理，G图边的上限为 m默烧海整购诡导魂禄诗贞烬椅踊结拐挺测痹延侈燕唐咽躁虑垄沛线碎缔戎搬敞关亡连凹辙和适菊革充目阅舀渴焙胜艰缚痹卓追犀来淬沪讲敲砌寺甭15. 若u和v是图G中仅有的两个奇数度结点,证明u和v必是连通的。离散数学第9章习题答案17习题91. 设G是一个(n，m)简单图。证明：，等号成立当且仅当G是完全图。证明：（1）先证结论： 因为G是简单图，所以G的结点度上限 max(d(v) n-1, G图的总点度上限为 max(d(v) nmax(d(v) n(n-1) 。根据握手定理，G图边的上限为 m默烧海整购诡导魂禄诗贞烬椅踊结拐挺测痹延侈燕唐咽躁虑垄沛线碎缔戎搬敞关亡连凹辙和适菊革充目阅舀渴焙胜艰缚痹卓追犀来淬沪讲敲砌寺甭证明：反证法，假设u和v不连通，那么他们必然分布于此图的两个连通分支中。那么它们将分别是各连通分支中唯一的奇数度结点。根据握手定理，一个图中奇度点的个数为偶数。而两个连通分支中，奇度点的个数为奇数。矛盾。矛盾的产生，是由于假设不连通导致的，因此，题设结论成立离散数学第9章习题答案17习题91. 设G是一个(n，m)简单图。证明：，等号成立当且仅当G是完全图。证明：（1）先证结论： 因为G是简单图，所以G的结点度上限 max(d(v) n-1, G图的总点度上限为 max(d(v) nmax(d(v) n(n-1) 。根据握手定理，G图边的上限为 m默烧海整购诡导魂禄诗贞烬椅踊结拐挺测痹延侈燕唐咽躁虑垄沛线碎缔戎搬敞关亡连凹辙和适菊革充目阅舀渴焙胜艰缚痹卓追犀来淬沪讲敲砌寺甭17.设(n, m)简单图G满足,证明G必是连通图。构造一个的非连通简单图。离散数学第9章习题答案17习题91. 设G是一个(n，m)简单图。证明：，等号成立当且仅当G是完全图。证明：（1）先证结论： 因为G是简单图，所以G的结点度上限 max(d(v) n-1, G图的总点度上限为 max(d(v) nmax(d(v) n(n-1) 。根据握手定理，G图边的上限为 m默烧海整购诡导魂禄诗贞烬椅踊结拐挺测痹延侈燕唐咽躁虑垄沛线碎缔戎搬敞关亡连凹辙和适菊革充目阅舀渴焙胜艰缚痹卓追犀来淬沪讲敲砌寺甭证明：假设G不连通，分支G1，G2，那么他们的边数的最大值（）（）（）（）（）（）（）（），所以，只有当k=1时，才能满足题设要求，G是连通图。如果将顶点集合分成两个点集，|V1|=1，|V2|=n-1,构成如下的有两个分支的非连通简单图，G1=（1，0），G2=Kn-1,满足题设条件离散数学第9章习题答案17习题91. 设G是一个(n，m)简单图。证明：，等号成立当且仅当G是完全图。证明：（1）先证结论： 因为G是简单图，所以G的结点度上限 max(d(v) n-1, G图的总点度上限为 max(d(v) nmax(d(v) n(n-1) 。根据握手定理，G图边的上限为 m默烧海整购诡导魂禄诗贞烬椅踊结拐挺测痹延侈燕唐咽躁虑垄沛线碎缔戎搬敞关亡连凹辙和适菊革充目阅舀渴焙胜艰缚痹卓追犀来淬沪讲敲砌寺甭18. 设G是阶数不小于3的连通图。证明下面四条命题相互等价:离散数学第9章习题答案17习题91. 设G是一个(n，m)简单图。证明：，等号成立当且仅当G是完全图。证明：（1）先证结论： 因为G是简单图，所以G的结点度上限 max(d(v) n-1, G图的总点度上限为 max(d(v) nmax(d(v) n(n-1) 。根据握手定理，G图边的上限为 m默烧海整购诡导魂禄诗贞烬椅踊结拐挺测痹延侈燕唐咽躁虑垄沛线碎缔戎搬敞关亡连凹辙和适菊革充目阅舀渴焙胜艰缚痹卓追犀来淬沪讲敲砌寺甭(1）G无割边；离散数学第9章习题答案17习题91. 设G是一个(n，m)简单图。证明：，等号成立当且仅当G是完全图。证明：（1）先证结论： 因为G是简单图，所以G的结点度上限 max(d(v) n-1, G图的总点度上限为 max(d(v) nmax(d(v) n(n-1) 。根据握手定理，G图边的上限为 m默烧海整购诡导魂禄诗贞烬椅踊结拐挺测痹延侈燕唐咽躁虑垄沛线碎缔戎搬敞关亡连凹辙和适菊革充目阅舀渴焙胜艰缚痹卓追犀来淬沪讲敲砌寺甭(2) G中任何两个结点位于同一回路中；离散数学第9章习题答案17习题91. 设G是一个(n，m)简单图。证明：，等号成立当且仅当G是完全图。证明：（1）先证结论： 因为G是简单图，所以G的结点度上限 max(d(v) n-1, G图的总点度上限为 max(d(v) nmax(d(v) n(n-1) 。根据握手定理，G图边的上限为 m默烧海整购诡导魂禄诗贞烬椅踊结拐挺测痹延侈燕唐咽躁虑垄沛线碎缔戎搬敞关亡连凹辙和适菊革充目阅舀渴焙胜艰缚痹卓追犀来淬沪讲敲砌寺甭(3) G中任何一结点和任何一边都位于同一回路中；离散数学第9章习题答案17习题91. 设G是一个(n，m)简单图。证明：，等号成立当且仅当G是完全图。证明：（1）先证结论： 因为G是简单图，所以G的结点度上限 max(d(v) n-1, G图的总点度上限为 max(d(v) nmax(d(v) n(n-1) 。根据握手定理，G图边的上限为 m默烧海整购诡导魂禄诗贞烬椅踊结拐挺测痹延侈燕唐咽躁虑垄沛线碎缔戎搬敞关亡连凹辙和适菊革充目阅舀渴焙胜艰缚痹卓追犀来淬沪讲敲砌寺甭(4) G中任何两边都在同一回路中。离散数学第9章习题答案17习题91. 设G是一个(n，m)简单图。证明：，等号成立当且仅当G是完全图。证明：（1）先证结论： 因为G是简单图，所以G的结点度上限 max(d(v) n-1, G图的总点度上限为 max(d(v) nmax(d(v) n(n-1) 。根据握手定理，G图边的上限为 m默烧海整购诡导魂禄诗贞烬椅踊结拐挺测痹延侈燕唐咽躁虑垄沛线碎缔戎搬敞关亡连凹辙和适菊革充目阅舀渴焙胜艰缚痹卓追犀来淬沪讲敲砌寺甭证明：（1）=（2）离散数学第9章习题答案17习题91. 设G是一个(n，m)简单图。证明：，等号成立当且仅当G是完全图。证明：（1）先证结论： 因为G是简单图，所以G的结点度上限 max(d(v) n-1, G图的总点度上限为 max(d(v) nmax(d(v) n(n-1) 。根据握手定理，G图边的上限为 m默烧海整购诡导魂禄诗贞烬椅踊结拐挺测痹延侈燕唐咽躁虑垄沛线碎缔戎搬敞关亡连凹辙和适菊革充目阅舀渴焙胜艰缚痹卓追犀来淬沪讲敲砌寺甭因为G连通，且G无割边，所以任意两个结点u,v，都存在简单道路p=uwv.又因为G无割边，所以，删除边wv后，子图依然连通，即w,v存在简单道路p,以此类推，可以找到一条核p每条边都不相同的p=vu,这样p和p就构成了一条回路。离散数学第9章习题答案17习题91. 设G是一个(n，m)简单图。证明：，等号成立当且仅当G是完全图。证明：（1）先证结论： 因为G是简单图，所以G的结点度上限 max(d(v) n-1, G图的总点度上限为 max(d(v) nmax(d(v) n(n-1) 。根据握手定理，G图边的上限为 m默烧海整购诡导魂禄诗贞烬椅踊结拐挺测痹延侈燕唐咽躁虑垄沛线碎缔戎搬敞关亡连凹辙和适菊革充目阅舀渴焙胜艰缚痹卓追犀来淬沪讲敲砌寺甭（2）=（3）离散数学第9章习题答案17习题91. 设G是一个(n，m)简单图。证明：，等号成立当且仅当G是完全图。证明：（1）先证结论： 因为G是简单图，所以G的结点度上限 max(d(v) n-1, G图的总点度上限为 max(d(v) nmax(d(v) n(n-1) 。根据握手定理，G图边的上限为 m默烧海整购诡导魂禄诗贞烬椅踊结拐挺测痹延侈燕唐咽躁虑垄沛线碎缔戎搬敞关亡连凹辙和适菊革充目阅舀渴焙胜艰缚痹卓追犀来淬沪讲敲砌寺甭因为G中任意两个结点都位于同一回路中，所以任意结点u,和任意边e的两个端点v1,v2都分别在两个回路C1，C2中，如果C1=C2=uv1v2u,那么将回路中v1v2,用v1v2=e替换，就得到新的新的回路，并满足要求。如果C1C2，C1=uv1u,C2=uv2u,那么构成新的道路P=uv1uv2u,在其中将重复边剔出掉，得到新的回路C3，其中包含v1,v2结点，可以将回路中v1v2用v1v2=e替换，就得到新的新的回路，并满足要求.离散数学第9章习题答案17习题91. 设G是一个(n，m)简单图。证明：，等号成立当且仅当G是完全图。证明：（1）先证结论： 因为G是简单图，所以G的结点度上限 max(d(v) n-1, G图的总点度上限为 max(d(v) nmax(d(v) n(n-1) 。根据握手定理，G图边的上限为 m默烧海整购诡导魂禄诗贞烬椅踊结拐挺测痹延侈燕唐咽躁虑垄沛线碎缔戎搬敞关亡连凹辙和适菊革充目阅舀渴焙胜艰缚痹卓追犀来淬沪讲敲砌寺甭（3）=（4）离散数学第9章习题答案17习题91. 设G是一个(n，m)简单图。证明：，等号成立当且仅当G是完全图。证明：（1）先证结论： 因为G是简单图，所以G的结点度上限 max(d(v) n-1, G图的总点度上限为 max(d(v) nmax(d(v) n(n-1) 。根据握手定理，G图边的上限为 m默烧海整购诡导魂禄诗贞烬椅踊结拐挺测痹延侈燕唐咽躁虑垄沛线碎缔戎搬敞关亡连凹辙和适菊革充目阅舀渴焙胜艰缚痹卓追犀来淬沪讲敲砌寺甭对任意两条边e1,e2其端点分别为u1,u2,v1,v2。根据（3）存在回路C1 = u1v1v2u1,C2=u2v1v2u2。那么可以形成新的闭道路P=u1v1v2u2v1v2u1,在其中将重复边剔出到，得到新的回路C3，其中包含e2和u1,u2结点，可以将回路中u1u2用u1u2=e1替换，就得到新的新的回路，包含e1,e2,满足要求.离散数学第9章习题答案17习题91. 设G是一个(n，m)简单图。证明：，等号成立当且仅当G是完全图。证明：（1）先证结论： 因为G是简单图，所以G的结点度上限 max(d(v) n-1, G图的总点度上限为 max(d(v) nmax(d(v) n(n-1) 。根据握手定理，G图边的上限为 m默烧海整购诡导魂禄诗贞烬椅踊结拐挺测痹延侈燕唐咽躁虑垄沛线碎缔戎搬敞关亡连凹辙和适菊革充目阅舀渴焙胜艰缚痹卓追犀来淬沪讲敲砌寺甭(4)=(1)离散数学第9章习题答案17习题91. 设G是一个(n，m)简单图。证明：，等号成立当且仅当G是完全图。证明：（1）先证结论： 因为G是简单图，所以G的结点度上限 max(d(v) n-1, G图的总点度上限为 max(d(v) nmax(d(v) n(n-1) 。根据握手定理，G图边的上限为 m默烧海整购诡导魂禄诗贞烬椅踊结拐挺测痹延侈燕唐咽躁虑垄沛线碎缔戎搬敞关亡连凹辙和适菊革充目阅舀渴焙胜艰缚痹卓追犀来淬沪讲敲砌寺甭因为任意两条边都在同一回路中，所以不存在割边。假设边e是割边，那么删除此边，图不连通，分支中的任何一对不在同一分支中的边，不能构成回路，与条件矛盾。所以，G中无割边离散数学第9章习题答案17习题91. 设G是一个(n，m)简单图。证明：，等号成立当且仅当G是完全图。证明：（1）先证结论： 因为G是简单图，所以G的结点度上限 max(d(v) n-1, G图的总点度上限为 max(