现在学习第五个知识点:1、图的基本概念2、通路、回路和连通性3、图的矩阵表示4、欧拉图和哈密顿图5、偶图与匹配6、平面图7、树1、图的基本概念2、通路、回路和连通性3、图的矩阵表示4、欧拉图和哈密顿图5、偶图与匹配6、平面图7、 偶图与匹配偶图是一种具有特定性质的图。一、偶图1、,满足G中任何一条边的两个端点,一个在V1中,另一个在V2中,则称G 是偶图或二分图,记。EVG,?,,2121VVVVV?????EVVG,,21?1、偶图的定义(续)若V1中的每个顶点与V2中的每个顶点有且仅有一条边相关联,则称偶图G 为完全偶图。若则记完全偶图为Kn,m。,,21mVnV??完全偶图有什么性质(特点)???2、 一个图是偶图当且仅当G中没有奇数长度的回路。请自学P242-P243的证明。请问:如果G中有一条回路的长度是奇数,则G??例题讲解例1判断下列各图是否为偶图,为什么?,、匹配1、,。若M 中任何两条边均无公共点,则称M是G的一个匹配;G中边数最多的匹配称为最大匹配,其元素的个数称为G的匹配数;若M 是最大匹配,且,则称M 是G的一个完备匹配;若,则称M 是G的一个完美匹配。??21,minVVM?EVVG,,21?EM?21VVM???例题讲解例2 指出下列各偶图是什么匹配?,
离散数学16 来自淘豆网m.daumloan.com转载请标明出处.
