资源描述
1 8.1 二部图 8.2 欧拉图 8.3 哈密尔顿图 8.4 平面图 第八章 一些特殊的图 若能将无向图 G=的顶点集 V划分成两 个子集 V1和 V2(V1V2=),使得 G中任何一 条边的两个端点一个属于 V1,另一个属于 V2, 则称 G为 二部图 (也称为偶图 ).V1,V2称为互 补顶点子集 ,此时可将 G记成 G=, 若 V1 =n, V2=m,则记完全二部图 G为 Kn,m. 二部图 定义 在下图中 ,(1)所示为 K2,3,(2)所示为 K3,3. K3,3是重要的完全二部图 ,它与 K5一 起在平面图中起着重要作用 . 判断二部图的定理 一个无向图 G=是二部图当 且仅当 G中无奇数长度的回路 . 图 8.2 1 2 3 4 5 6 6 2 4 1 5 3 图 8.2所示 3个图中 ,均无奇数长度的 回路 ,所以 ,它们都是二部图 . 其中图 (2)所示为 K2,3,图 (3)所示为 K3,3,它们分别与图 8.1中 (1),(2)所示 的图同构 . 设 G=为无向图 ,E*E,若 E*中任意两 条边均不相邻 ,则称 E*为 G中的 匹配 (或边独 立集 ). 若在 E*中再加入任何 1条边就都不是匹配了 , 则称 E*为 极大匹配 . 边数最多的极大匹配称为 最大匹配 ,最大匹 配中的元素 (边 )的个数称为 G的 匹配数 ,记为 1(G),简记为 1. 匹 配 今后常用 M表示匹配 .设 M为 G中一个匹配 .v V(G),若 存在 M中的边与 v关联 ,则称 v为 M饱和点 ,否则称 v为 M非饱和 点 ,若 G中每个顶点都是 M饱和 点 ,则称 M为 G中 完美匹配 . 在图 (1)中， e1,e1,e7,e5,e4,e6 等都是图中的 匹配 .其中 e5,e1,e7,e4,e6 是 极大匹配 ,e1,e7,e2,e6是 最大匹配 ,匹 配数 1=2. 图中不存在 完美匹配 . 在图 (2)中 ,e2,e5,e3,e6,e1,e7,e4都 是极大匹配 ,其中 e1,e7,e4是最大匹配 , 同时也是完美匹配 ,匹配数为 3. 完备匹配 设 G=为一个二部 图 ,M为 G中一个最大匹配 ,若 M =minV1,V2,则称 M 为 G中的 一个 完备匹配 . 此时若 V1 V2,则称 M为 V1到 V2 的一个 完备匹配 .如果 V1= V2, 这时 M为 G中的 完美匹配 . 图 8.4 存在完备匹配吗 ?存在完美匹配吗 ?. Hall定理 设二部图 G=,V1V2,G中 存在从 V1到 V2的完备匹配当且仅当 V1 中任意 k个顶点 (k=1,2, V1)至少邻 接 V2中的 k个顶点 . 设二部图 G=,如果 (1)V1中每个顶点至少关联 t(t 0)条 边 ; (2)V2中每个顶点至多关联 t条边 , 则 G中 存在 V1到 V2的完备匹配 . Hall定理中的条件称为“相异性条件” , 定理 8.3中的条件称为“ t条件” ,满足 t条 件的二部图 ,一定满足相异性条件 . 事实上 ,由条件 (1)可知 ,V1中 k个顶点至少 关联 kt条边 .由条件 (2)可知 ,这 kt条边至少 关联 V2中的 k个顶点 ,于是 若 G满足 t条件 , 则 G一定满足相异性条件 ,但反之不真 . 例 8.1 某中学有 3个课外小组 :物理组、化 学组、生物组 .今有张、王、李、赵、 陈 5名同学 .若已知 : (1)张、王为物理组成员 ,张、李、赵为 化学组成员 ,李、赵、陈为生物组成员 ; (2)张为物理组成员 ,王、李、赵为化学 组成员 ,王、李、赵、陈为生物组成员 ; (3)张为物理组和化学组成员 ,王、李、 赵、陈为生物组成员 . 问在以上 3种情况下能否各选出 3名不 兼职的组长？ 解 : 设 v1,v2,v3,v4,v5分别表示张、王、李、 赵、陈 .u1,u2,u3分别表示物理组、化学 组、生物组 .在 3种情况下作二部图分别 记为 G1,G2,G3,如图 8.5所示 . 图 8.5 G1满足 t=2的 t条件 ,所以 ,存在从 V1=u1,u2,u3到 V2=v1,v2,v3,v4,v5的 完备匹配 ,图中粗边所示的匹配就是其 中的一个 ,即选张为物理组组长、李为 化学组组长、赵为生物组组长 . G2不满足 t条件 ,但满足相异性条件 , 因而也存在完备匹配 ,图中粗边所 示匹配就是其中的一个完备匹配 . G3不满足 t条件 ,也不满足相异性条 件 ,因而不存在完备匹配 ,故选不出 3名不兼职的组长来 .
展开阅读全文