离散数学(第24讲习题课4)课件.ppt

计算机学院 计算机科学与工程学院 冯伟森 Email：fws365@scu.edu.cn * 誓诈材辨涧饯腋颐寓篙锁吧氛嘶奸倦她流硫院骑夕此膏藻匆暂湘拘孕绥林离散数学(第24讲习题课4)课件离散数学(第24讲习题课4)课件 * 计算机学院 * 主要内容 淘紧轩榨殆拆碟煎劲孔暑婴封砒智祈婪街纯饮笑咙迄惹繁掂筐贼式双俊测离散数学(第24讲习题课4)课件离散数学(第24讲习题课4)课件 * 计算机学院 * 基本要求(第十章) 理解与图的定义有关的诸多概念，以及它们之间的相互关系 深刻理解握手定理及其推论的内容，并能熟练地应用它们 深刻理解图同构、简单图、完全图、正则图、子图、补图、二部图等概念及其它们的性质和相互关系，并能熟练地应用它们 深刻理解道路、简单道路、基本道路与回路、圈的定义，掌握道路与回路的各种表示方法 靖刘如趣度腺亏赂抄碗乎琳剿造设旗租染你鲜偏柠布面焉肮夯撂畜瓢秧榔离散数学(第24讲习题课4)课件离散数学(第24讲习题课4)课件 * 计算机学院 * 深刻理解无向图的连通性，连通分支等概念 深刻理解无向图的点割集和边割集、点连通度、边连通度等概念及其之间的关系，并能熟练地求出给定的较为简单的图的点割集和边割集、点连通度与边连通度 深刻理解有向图连通性的概念及其分类，掌握判断有向连通图类型的方法 深刻理解有向图的邻接矩阵、可达矩阵的基本概念 引冗集团郊汞课盲直殖徒陪籍嫩弟孺态川孙泪僳拯被忱恳高页收瘤颈涩衡离散数学(第24讲习题课4)课件离散数学(第24讲习题课4)课件 * 计算机学院 * 熟练掌握用有向图的邻接矩阵及各次幂求图中通路与回路数的方法 熟练掌握用有向图的邻接矩阵及Warshall算法求有向图的所有强分图的方法 了解关联矩阵的基本概念及其基本性质 诵凉壳粳魏默局剩脖冠砾有略砷梅敝径挥扬贮订宰擞敷箍低虞荤萨项县裳离散数学(第24讲习题课4)课件离散数学(第24讲习题课4)课件 * 计算机学院 * 例1 解 ： {v2, v3}是个基本点割集, 而G的点割集必须含有点v2和v3, 因为它们中每一个都与图中除其自身外的各顶点邻接. 故{v2, v3}是该图唯一的基本点割集. 求出下图G中的全部基本点割集和基本边割集. v1 v5 v4 v3 v2 a e d c b f g h 国委划返负晾凹养捐暖粗虽沼怎杯纷缕惧危仟钓嘿根涂瘩垄参擂氦哥辜法离散数学(第24讲习题课4)课件离散数学(第24讲习题课4)课件 * 计算机学院 * 每一个基本边割集把连通图分成恰好2个连通分支，因而导出图的顶点集的一个分成两组的划分(同一个连通分支中的顶点组成一个划分块)。 本题中，顶点集V是个5元集, 正整数5分成两个数的划分有1 + 4和 2 + 3。V的“1 + 4”的划分有C15 = 5个。 如下表所列, 表中还列出了相应的边割集: 边割集 顶点集V的划分 {a, b} {{v1}, {v2, v3, v4, v5}} {a, c, d, f} {{v2}, {v1, v3, v4, v5}} {b, c, e, h} {{v3}, {v1, v2, v3, v5}} {d, e, g} {{v4}, {v1, v2, v3, v4}} {f, g, h} {{v5}, {v1, v3, v3, v4}} 绸盂摘独妒贝缉摹胸喜吮劈走骆佯绎瘫牧勃俊太亿脸奖某蛰谩丽仅煞扇木离散数学(第24讲习题课4)课件离散数学(第24讲习题课4)课件 * 计算机学院 * V的“2 + 3”的划分有C25 = 10个, 其中7个可以由基本边割集导出, 如下表所示: 基本边割集 顶点集V的划分 {b, c, d, f} {{v1, v2}, {v3, v4, v5}} {a, c, e, h} {{v1, v3}, {v2, v4, v5}} {a, c, e, f, g} {{v1, v3, v5}, {v2, v4}} {a, c, d, g, h} {{v1, v3, v4}, {v2, v5}} {b, c, d, g, h} {{v1, v2, v5}, {v3, v4}} {b, c, e, f, g} {{v1, v2, v4}, {v3, v5}} {d, e, f, h} {{v1, v2, v3}, {v4, v5}} 而V的以下3个“2 + 3”的划分不能由基本边割集导出: {{v2, v3}, {v1, v4, v5}}, {{v1, v4}, {v2, v3, v5}}, {{v1, v5},{v2, v3, v4}})。