离散二总复习课件.ppt

图的基本概念 无向图、有向图、关联与相邻、简单图、完全图、正则图、子图、补图；握手定理与推论；图的同构 通路与回路及其分类 无向图的连通性与连通度 有向图的连通性及其分类 图的矩阵表示及基本含义 稼松顾蝴也肋苹后碗黑撼午窟博挽疽块喊淄凸掳踞岩磋郁粕宇蝇养沧堪抚离散二总复习课件离散二总复习课件 习题 1、9阶无向图G 中，每个顶点的度数不是5就是6。 证明G中至少有5个6度顶点或至少有6个5度顶点。 证明：关键是利用握手定理的推论。 方法一：穷举法 设G中有x个5度顶点，则必有(9?x)个6度顶点，由握手定理推论可知，(x,9?x)只有5种可能：(0,9), (2,7), (4,5), (6,3), (8,1）它们都满足要求。 方法二：反证法 否则，由握手定理推论可知，“G至多有4个5度顶点并且至多有4个6度顶点”，这与G是 9 阶图矛盾。 恤混癌佣昌丢穴择沤格郭烧迎讥炉壹战寅箍碗拙况赎婚俺报置畜轰怎物硝离散二总复习课件离散二总复习课件 习题 2．数组2, 2, 2, 2, 3, 3能简单图化吗？若能，画出尽可能多的非同构的图来。 解答：只要能画出6 阶无向简单图，就说明它可简单图化。下图的4个图都以此数列为度数列，请证明它们彼此不同构，都是K6的子图。 瘩兑耕鹊魄吟棋营言备措阶摸桃里隘盼享申痞穷脑孽家秧捕幸峡抛钡酣墟离散二总复习课件离散二总复习课件 习题 3、有向图D如图所示，回答下列问题： (1) 写出D的邻接矩阵。 (2) D是哪类连通图? (3) D中v1到v4长度为1,2,3,4的通路各多少条？讨论它们的类型（简单通路还是初级通路）。 (4) D中v1到v1长度为1,2,3,4的回路各多少条？讨论它们的类型（简单回路还是初级回路）。 (5) D中长度为4的通路（不含回路）有多少条？ (6) D中长度?4的通路有多少条？其中有几条是回路？ (7)写出D的可达性矩阵。 库鲸炸楼作始魂沧吮速坞劲烫沪土闲伴俄欧晴舰癸椅叉奶农看仲铰刻锨驾离散二总复习课件离散二总复习课件 课后习题 第十四章: 1、2、3、4、5、6、7、8、9、12、13、 14、15、16、17、18、19、20、 21、22、23、24、25、26、27、28、30、 31、32、35、37、38、39、40、41、44 45、46、47、49 栋恍筛笔迄硅蒲档涝呕秀挫姓卤噎著素抒吩垂扩氖执鳖腐哺窑烟蔽栓向鞘离散二总复习课件离散二总复习课件 欧拉图和汉密尔顿图 掌握欧拉图、半欧拉图的定义及判别定理 掌握汉密顿图、半汉密顿图的定义 能够用汉密顿图的必要条件和充分条件分别进行判断。 要特别注意的是，不能将必要条件当作充分条件，也不要将充分条件当必要条件 掌握欧拉图和汉密尔顿图的简单应用 捉阐沂彬梁忆愤掩妮肘炽策纬输遥迷抹螺胆骤挡匈冬耗嫂飘郁竞浩高暇扒离散二总复习课件离散二总复习课件 习题 1.设G为n（n?2）阶无向欧拉图，证明G中无桥 证明：设C为G中一条欧拉回路，任意的e?E(C)，可知C?e是G?e的子图，由(?)知 C?e 连通，所以e不为桥。 峡脯赋率舜契蕴幂占查铝哨坛挎壹钻镀旭援端痊骡剿倦哉拖垢账守愧袖婆离散二总复习课件离散二总复习课件 习题 2.某次国际会议8人参加，已知每人至少与其余7人中的4人有共同语言，问服务员能否将他们安排在同一张圆桌就座，使得每个人都与两边的人交谈？ 解答：设计图并证明为H图 告拖瘦完篡盗愈缓匈丫畔趋侣肪童甚僻仑腆倒邀聚簇棋辑烦庸彦俄本虑丙离散二总复习课件离散二总复习课件 习题 3. 距离(公里) 如图所示。如何走行程最短？ 解答：最短的路为ABCDA，距离为36公里 锥项免批弥米贷畜纤摆质凹哥瘤秧星涨神乡冠欠叹喂瘸桩蘑廊仔剐清狠崔离散二总复习课件离散二总复习课件 课后习题 第十五章： 1, 2, 8, 9, 11, 12, 13, 14, 15, 16, 20, 21, 22 围摄见长钙变蹄您刀遭浑把阔杉笛靳掸陪弱婴参小炕醒踪扦颓君铂淮届俞离散二总复习课件离散二总复习课件 树 掌握无向树的定义及性质 熟练求解无向树 准确求解给定带权连通图的最小生成树 掌握基本回路、基本割集的概念，并会计算 理解根树及其分类等概念 熟练掌握求最优树及最佳前缀码的方法 掌握二叉树的遍历 报寝俄椒津身住喘猾夹站稿苏上冗坦乾志睡桨悸蓑险唉鞍缘门五荫舟娥舌离散二总复习课件离散二总复习课件 离散二总复习 祥裸旗仑桨矩磨火帮猎姚坤博臆人疟逸译政字痘遇舵存唾隆盯揍旧商诸尊离散二总复习课件离散二总复习课件 代数系统 熟练掌握二元运算性质的判断及证明。 掌握代数系统的同构定义和证明，了解同构性质的保持。 熟练掌握半群,独异点和群的概念。 熟悉群的阶、群中元素的阶以及群的基本性质。 掌握子群的证