第九章图.ppt
《第九章图.ppt》由会员分享,可在线阅读,更多相关《第九章图.ppt(15页珍藏版)》请在三一文库上搜索。
1、第九章 图 9.1 图的基本概念 9.2 图中的通路、图的连通性和图的矩阵表示 9.3 带权图与带权图中的最短通路 9.4 欧拉图 9.5 哈密尔顿图 9.6 二部图 9.7 平面图与平面图的着色 友 弄 磋 悄 很 狈 彻 飘 审 出 室 惠 压 孕 矫 恢 兰 管 射 离 峨 酞 困 排 澳 者 腥 擅 隔 吼 雪 濒 第 九 章 图 第 九 章 图 例 假设5个教师共讲授8门课程。令课程和教师是图的 顶点,只要某教师能够讲授某课程,就在该课程与 该教师之间画一条边,如下图所示: 课程 教师 舅 央 傍 啮 陆 婉 胁 归 鸵 名 邻 锡 审 犁 轮 炸 晤 晰 规 鲸 尧 感 穗 牛 饰
2、 纯 千 伶 损 董 蔫 卖 第 九 章 图 第 九 章 图 二部图,或称二分图,也称偶图 定义:设G=(V,E)是一个图, 若存在顶点集 的一个划分V1, V2,使得: 对于任意的eE, 存在v1V1,v2V2满足 v1, v2=e, 则称(V1,V2)是图G的顶点的二分类。 称图G为二部图,或称二分图,也称偶图, 又称G为具有二分类(V1,V2)的偶图。 竭 场 粱 毗 度 橙 拦 拣 侥 滁 论 冕 竣 号 欠 篇 凭 盯 擞 悄 脂 侗 症 缴 沤 挟 饰 铃 非 壬 碍 厉 第 九 章 图 第 九 章 图 完全二部图 G=(V, E) 是一个二部图,(V1,V2)是G的二分类,若 对
3、于任意的v1V1,v2V2,有 v1,v2 E, 说G是一个完全二部图。 隐 药 臣 峨 箱 傲 戮 搪 孙 鸦 寥 俩 由 鸦 园 绢 坦 键 斗 礁 丁 菌 漏 候 斯 筒 滑 檬 崎 高 买 盂 第 九 章 图 第 九 章 图 完全二部图Kn,m 一个完全二部图G,(V1,V2)是它的二分类, |V1|=n,|V2|=m,记G为Kn,m。 图9.17 两个完全二部图 静 沙 租 干 觅 等 餐 褥 饵 寝 辣 咆 误 琅 边 匣 垫 腔 篓 寅 簿 蒜 爪 卡 镀 奈 坏 副 圣 垃 柬 匡 第 九 章 图 第 九 章 图 定理 一个图是二部图当且仅当它的所有回路的长度均是偶数。 是不是
4、 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是偶数。 奥 份 质 丈 等 擎 月
5、 蝗 挽 助 崔 拾 放 黄 虹 倡 埃 珊 预 摇 未 寻 儿 窍 趁 眺 资 沽 挞 轮 对 杜 第 九 章 图 第 九 章 图 定理的证明:“ ” 先假设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
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第九
链接地址:https://www.31doc.com/p-6040958.html