离散数学 货郎问题 货郎问题：有个城市，给定城市之间道路的长度（长度可以为 ∞，对应这两个城市之间无交通线).货郎从某个城市出发，要 经过每个城市一次且仅一次，最后回到出发的城市，问如何走 才能使他走的路线最短？ 图论方法描述如下：设G=<V,E,W为一个阶完全带权图Km, 各边的权非负，且可能为o.求G中的一条最短的哈密顿回路 不计出发点和方向，K(23)中有(-1)/2条不同的哈密顿回 路 16
16 货郎问题 货郎问题: 有n个城市, 给定城市之间道路的长度(长度可以为 , 对应这两个城市之间无交通线). 货郎从某个城市出发, 要 经过每个城市一次且仅一次, 最后回到出发的城市, 问如何走 才能使他走的路线最短? 图论方法描述如下: 设G=<V,E,W>为一个n阶完全带权图Kn , 各边的权非负, 且可能为. 求G中的一条最短的哈密顿回路. 不计出发点和方向, Kn (n3)中有(n−1)!/2 条不同的哈密顿回 路
离散数学 例题 例6求下面带权图K4中最短哈密回路. 3 1 d 2 2 4 3 解C=abeda, WC)=10 C2=abdca,W(C2)=11 C3=acbda,W(C3)=9 最短 17
17 解 C1= a b c d a, W(C1 )=10 C2= a b d c a, W(C2 )=11 C3= a c b d a, W(C3 )=9 最短 例6 求下面带权图K4中最短哈密顿回路. 例题
离散数学 13.3二部图与匹配 定义13.3设G=<V,E>为一个无向图，若能将分成V和 (VUV=V,V⌒V=⑦)，使得G中的每条边的两个端点都是一 个属于V,另一个属于V,则称G为二部图（或称二分图，偶 图)，称V和y为互补顶点子集，常将二部图G记为<V,V,E>. 又若G是简单二部图，V中每个顶点均与V,中所有的顶点相邻， 则称G为完全二部图，记为K,其中=V,s=V孔 18
18 13.3 二部图与匹配 定义13.3 设 G=<V,E>为一个无向图, 若能将 V分成 V1和V2 (V1V2=V, V1V2=), 使得 G 中的每条边的两个端点都是一 个属于V1 , 另一个属于V2 , 则称 G 为二部图( 或称二分图, 偶 图), 称V1和V2为互补顶点子集, 常将二部图G记为<V1 ,V2 ,E>. 又若G是简单二部图, V1中每个顶点均与V2中所有的顶点相邻， 则称G为完全二部图, 记为 Kr,s , 其中r=|V1 |, s=|V2 |
离散数学 实例 例 K23 K33 19
19 实例 例 K2,3 K3,3
离散数学 二部图的判别法 定理13.4无向图G=<V,V,E>是二部图当且仅当G中无奇圈. 证必要性.若G中无圈，结论成立.若G中有圈，设G中的一个 圈C=y2…yy1,22.不妨设y1∈V1,y1,y2,,y依次交替属于V1, V且y∈V,因而I为偶数.得证C为偶圈. 充分性.不妨设G为连通图，否则可对每个连通分支进行讨论， 孤立点可根据需要分属V和V,.设为G中任意一个顶点，令 V={y|v∈(G)Ad,)为偶数} V={v|vEG)Ad(o,)为奇数} d(,)是到的最短路径的边数（每条边的权为1）.Y≠0， V,V⌒V=,VUV=G).要证V中任意两点不相邻. 20
20 二部图的判别法 定理13.4 无向图G=<V1 ,V2 ,E>是二部图当且仅当G中无奇圈. 证 必要性. 若G中无圈, 结论成立. 若G中有圈, 设G中的一个 圈C=v1v2vlv1 , l≥2. 不妨设v1V1 , v1 ,v2 ,,vl 依次交替属于V1 , V2且vlV2 , 因而l为偶数. 得证C为偶圈． 充分性. 不妨设G为连通图, 否则可对每个连通分支进行讨论, 孤立点可根据需要分属V1和V2 . 设v0为G中任意一个顶点, 令 V1={v | vV(G)d(v0 ,v)为偶数} V2={v | vV(G)d(v0 ,v)为奇数} d(v0 ,v)是v0到v的最短路径的边数(每条边的权为1). V1， V2, V1V2=, V1V2=V(G). 要证V1中任意两点不相邻．