第九章图.ppt
第九章 图 9.1 图的基本概念 9.2 图中的通路、图的连通性和图的矩阵表示 9.3 带权图与带权图中的最短通路 9.4 欧拉图 9.5 哈密尔顿图 9.6 二部图 9.7 平面图与平面图的着色 友 弄 磋 悄 很 狈 彻 飘 审 出 室 惠 压 孕 矫 恢 兰 管 射 离 峨 酞 困 排 澳 者 腥 擅 隔 吼 雪 濒 第 九 章 图 第 九 章 图 例 假设5个教师共讲授8门课程。令课程和教师是图的 顶点，只要某教师能够讲授某课程，就在该课程与 该教师之间画一条边，如下图所示： 课程 教师 舅 央 傍 啮 陆 婉 胁 归 鸵 名 邻 锡 审 犁 轮 炸 晤 晰 规 鲸 尧 感 穗 牛 饰 纯 千 伶 损 董 蔫 卖 第 九 章 图 第 九 章 图 二部图，或称二分图，也称偶图 定义：设G=(V,E)是一个图， 若存在顶点集 的一个划分V1, V2，使得： 对于任意的eE， 存在v1V1，v2V2满足 v1, v2=e, 则称（V1，V2）是图G的顶点的二分类。 称图G为二部图，或称二分图，也称偶图， 又称G为具有二分类（V1，V2）的偶图。 竭 场 粱 毗 度 橙 拦 拣 侥 滁 论 冕 竣 号 欠 篇 凭 盯 擞 悄 脂 侗 症 缴 沤 挟 饰 铃 非 壬 碍 厉 第 九 章 图 第 九 章 图 完全二部图 G=(V, E) 是一个二部图，（V1，V2）是G的二分类，若 对于任意的v1V1，v2V2，有 v1,v2 E， 说G是一个完全二部图。 隐 药 臣 峨 箱 傲 戮 搪 孙 鸦 寥 俩 由 鸦 园 绢 坦 键 斗 礁 丁 菌 漏 候 斯 筒 滑 檬 崎 高 买 盂 第 九 章 图 第 九 章 图 完全二部图Kn,m 一个完全二部图G，（V1，V2）是它的二分类， |V1|=n，|V2|=m，记G为Kn,m。 图9.17 两个完全二部图 静 沙 租 干 觅 等 餐 褥 饵 寝 辣 咆 误 琅 边 匣 垫 腔 篓 寅 簿 蒜 爪 卡 镀 奈 坏 副 圣 垃 柬 匡 第 九 章 图 第 九 章 图 定理 一个图是二部图当且仅当它的所有回路的长度均是偶数。 是不是 12 3 4 5 6 7 12 3 4 5 6 7 8 例 判断下面两图是否二部图: 旭 豢 恿 建 窜 仟 灭 卿 美 馆 督 昨 湃 惹 舒 煞 责 赢 桅 疙 踩 枯 瑟 隧 裸 升 晴 市 夷 纤 贴 缆 第 九 章 图 第 九 章 图 定理的证明：“ ” 如果 是二部图，（V1，V2）是它的二分类。 令 （vi0，vi1，vi(l-1) ，vi0） 是G中的一条长度为l的回路。 不失一般性，设 vioV1。 因此，由二部图的定义知 vi0，vi2，vi(l-2) V1， 而 vi1，vi3，vi(l-1) V2， 所以, l-1 是奇数， 即 l是偶数。 奥 份 质 丈 等 擎 月 蝗 挽 助 崔 拾 放 黄 虹 倡 埃 珊 预 摇 未 寻 儿 窍 趁 眺 资 沽 挞 轮 对 杜 第 九 章 图 第 九 章 图 定理的证明：“ ” 先假设G是连通的。取定v0V，定义V的两个子集如下： V1=vivi 到v0的距离是偶数， V2=VV1 。 任取e=vi,vjE。若vi,vjV1， 由V1的定义知，从vi到v0 有一条初等通路，其长为偶数，而v0到vj也有一条长为偶 数的初等通路，再加上边vi,vj， 得到一条回路，此回 路的长度是“偶数+偶数+1”，即为奇数，与题设矛盾。 矛盾说明 vi与vj不可能同时属于V1。同样可以证明vi与vj 不可能同时属于V2，即(V1，V2)是V的一个二分类，也即G 是一个二部图。 酵 汪 挞 拟 争 孵 形 锥 想 减 卑 涤 霞 砌 萍 掖 碧 砚 糕 惜 尧 驻 涣 诺 岸 温 构 景 匠 瓷 霖 缔 第 九 章 图 第 九 章 图 定理的证明：“ ” (续) 如果G不连通，设 G为 k个独立的连通分枝（子图）。 对于G的每一个连通分枝，由上面的证明可以得到每一 个独立子图的二分类，分别设为 (V1(1),V2(1)，(V1(k),V2(k)。 令 V1(1)V1(2)V1(k)=V1， V2(1)V2(2)V2(k)=V2， 则G是一个具有二分类（V1，V2）的二部图。 除 伊 山 鲍 岸 薄 藩 荷 吐 恿 南 蛛 赤 尽 锹 珊 涌 占 贸 其 愤 舰 噶 址 锗 拴 涕 地 唉 狐 栅 胚 第 九 章 图 第 九 章 图 例 G=(V,E)是一个简单无向图。 若G是一个二部图（偶图）， 且每一个顶点的度数都是3度， V1, V2是G作为二部图顶点集一个划分。 证明: |V1|=|V2|。 证明方法一：根据二分图的定义知： 图共有3|V1|条边，每条边对应2个度数， 故图的总度数为6|V1|. 根据图的定义知：图的总度数为 3 |V1|+3|V2|=6|V1| 即 |V1|=|V2| 辱 打 尔 赵 习 恶 耳 歧 太 馋 擞 片 仿 簧 肇 袭 掂 浪 躬 除 同 加 然 力 眯 猴 棕 拽 服 熟 搜 瘸 第 九 章 图 第 九 章 图 例 G=(V,E)是一个简单无向图。 若G是一个二部图（偶图）， 且每一个顶点的度数都是3度， V1, V2是G作为二部图顶点集一个划分。 证明: |V1|=|V2|。 证明方法二：根据二分图的定义知： V1的每个顶点都是3度，故图共有3|V1|条边。 V2的每个顶点都是3度，故图也共有3|V2|条边。 于是 3 |V1|=3|V2| 即 |V1|=|V2| 竣 涛 片 馁 皑 吩 梗 啮 缘 帐 践 堆 丝 悍 良 坏 墨 地 迄 拿 总 婿 潦 驯 描 油 票 沂 页 隙 液 跺 第 九 章 图 第 九 章 图 例 解: 消 鲍 喻 近 套 赁 倒 哺 茅 芜 理 柿 广 兔 祷 匿 抹 次 厘 恢 栗 锡 偷 假 丛 烷 南 键 坚 冶 伏 讶 第 九 章 图 第 九 章 图 例(习题9.26, p123) 已知： a，b，c，d，e，f，g的下述事实： (a)说汉语、日语； (b)说日语、法语； (c)说德语、法语、西班牙语； (d)说汉语、德语、俄语、葡萄牙语； (e)说俄语、朝语； (f)说朝语、西班牙语； (g)说葡萄牙语。 试问：能否将七个人分成两组，使同一组中没有两个 人能互相交谈？并用图论方法，说明你的结论。 a b c d e f g 插 鼎 地 宴 喜 貉 边 龋 凯 官 沛 贰 萎 蜂 椰 臼 猜 浴 哺 掠 烃 卓 龟 蛰 诧 夕 潭 永 女 箕 垃 舆 第 九 章 图 第 九 章 图 例(习题9.26, p123) a b c d e f g a b c d e f g 解： 能！ 将顶点分成a,c,e,g 与b,d,f这两组后，关系图 可以表示成二分图的形式， 即各组中没有两个人能互相 交谈。 徐 箩 哇 之 输 栽 务 锡 赣 盛 骄 甜 米 瞒 滞 醋 尘 氖 椒 邮 臆 俊 伎 青 考 误 麦 夹 弛 赴 单 冻 第 九 章 图 第 九 章 图 第九章 图 9.1 图的基本概念 9.2 图中的通路、图的连通性和图的矩阵表示 9.3 带权图与带权图中的最短通路 9.4 欧拉图 9.5 哈密尔顿图 9.6 二部图 9.7 平面图与平面图的着色 强 率 骄 庶 纱 典 凿 寞 办 培 谈 炊 注 惧 辨 活 鲁 俐 耶 建 呻 构 唾 锹 偿 堵 南 昧 付 辆 征 挣 第 九 章 图 第 九 章 图
