离散数学 第十五讲(全).pdf

2006 5 31北京邮电大学电子工程学院1 第第8章 一些特殊的图章 一些特殊的图 8 1 二部图二部图 8 2 欧拉图欧拉图 8 3 汉密顿图汉密顿图 8 4 平面图平面图 8 5 题例分析 略 题例分析 略 2006 5 31北京邮电大学电子工程学院2 第第8章 一些特殊的图章 一些特殊的图 理解二部图的判别定理 会用二部图描述某些实际 问题 理解 理解二部图的判别定理 会用二部图描述某些实际 问题 理解Hall定理并会求解一些实际问题 定理并会求解一些实际问题 理解欧拉通路 回路和欧拉图的概念 熟练掌握判 定欧拉图的方法 理解欧拉通路 回路和欧拉图的概念 熟练掌握判 定欧拉图的方法 理解哈密顿通路 回路和哈密顿图的概念 会判断 某些图是或不是哈密顿图 理解哈密顿通路 回路和哈密顿图的概念 会判断 某些图是或不是哈密顿图 理解平面图 面及次数等概念 理解欧拉公式及相 关定理的内容 会简单地判断一个图是否为平面 图 理解平面图 面及次数等概念 理解欧拉公式及相 关定理的内容 会简单地判断一个图是否为平面 图 2006 5 31北京邮电大学电子工程学院3 8 1 二部图二部图 本节均讨论无向图 本节均讨论无向图 定义定义8 1 若无向图若无向图G 的顶点集的顶点集V可划分成 两个子集 可划分成 两个子集V1和和V2 使得 使得G中任何一条边的两个端点 一个属于 中任何一条边的两个端点 一个属于V1 一个属于 一个属于V2 则称 则称G为二部图 若为二部图 若V1中 任何一个顶点与 中 任何一个顶点与V2中每一个顶点有且仅有一条边相关 联 则称 中每一个顶点有且仅有一条边相关 联 则称G为完全二部图 为完全二部图 K2 3K3 3 2006 5 31北京邮电大学电子工程学院4 定理定理8 1 一个无向 图 一个无向 图G 是二部图 是二部图 G中无奇数长度的回 路 中无奇数长度的回 路 定义定义8 2 一个无向图一个无向图G 若存在 若存在E E 且 且 E 中任意两条边不相邻 则称中任意两条边不相邻 则称E 为为G的匹配 边独立 集 若在 的匹配 边独立 集 若在E 中再加上任何一条边就不是匹配的了 则称 中再加上任何一条边就不是匹配的了 则称E 为为G的极大匹配 边数最多的极大匹配称为最 大匹配 最大匹配所含边的条数称为 的极大匹配 边数最多的极大匹配称为最 大匹配 最大匹配所含边的条数称为G的匹配数 记 为 的匹配数 记 为 1 G 2006 5 31北京邮电大学电子工程学院5 e1 e7 e2 e6 e5 1 e7 e1 e2 e4 e3 e6 e5 2 e1 e5 e2 e6 e1 e7 是匹配 是匹配 e5 e2 e6 e1 e7 是极大匹配 是极大匹配 e2 e6 e1 e7 是最大匹配 是最大匹配 e2 e5 e3 e6 e1 e4 e7 是极大匹配 是极大匹配 e1 e4 e7 是最大匹配 是最大匹配 2006 5 31北京邮电大学电子工程学院6 设设M为为G的一个匹配 的一个匹配 v V G 若存在 若存在M中的边 与 中的边 与v关联 则称关联 则称v为为M饱和点 若饱和点 若G中每个顶点都是中每个顶点都是M饱 和点 则称 饱 和点 则称M为为G的完美匹配 的完美匹配 定义定义8 3 一个无向图一个无向图G 为一个二部图 为一个二部图 M为为G的一个最大匹配 若 的一个最大匹配 若 M min V1 V2 则称 则称 M为为G的一个完备匹配 若 的一个完备匹配 若 V1 V2 则称 则称M为为V1 到到 V2的一个完备匹配 若 的一个完备匹配 若 V1 V2 则称 则称M为为G中的完 美匹配 中的完 美匹配 2006 5 31北京邮电大学电子工程学院7 e e1 e2是上图的 最大匹配 但 不是完备匹 配 更不是完 美匹配 是上图的 最大匹配 但 不是完备匹 配 更不是完 美匹配 e1 e2是上图 的完备匹 配 但不是 完美匹配 是上图 的完备匹 配 但不是 完美匹配 e1 e2 e3是上图 的完美匹配 是上图 的完美匹配 e1 e2 e1 e2 e1 e2 e3 2006 5 31北京邮电大学电子工程学院8 定理定理8 2 Hall定理 定理 设二部图设二部图G V1 V2 G中存在中存在V1 到到V2的完备匹配 的完备匹配 V1 中的任意中的任意k个顶点至少 邻接 个顶点至少 邻接V2 的的k个顶点个顶点 相异性条件 相异性条件 定理定理8 3 设二部图设二部图G 如果 如果 1 V1 中每个顶点至少关联中每个顶点至少关联 t t 0 条边 条边 2 V2 中每个顶点至多关联中每个顶点至多关联 t 条边 则 条边 则G中存在中存在V1 到到V2的完备匹配的完备匹配 t 条件 条件 注意 注意 t 条件 相异性条件条件 相异性条件 分析 由 分析 由 1 V1 中每个顶点至少关联中每个顶点至少关联 t 条边 则条边 则k 个顶点至少关联个顶点至少关联 kt 条边 由 条边 由 2 这 这kt 条边至少关联条边至少关联V2 的的 k个顶点 则满足相异性条件 个顶点 则满足相异性条件 反之不真 反之不真 2006 5 31北京邮电大学电子工程学院9 例例8 1 某中学有某中学有3个课外小组 物理 化 学 生物组 今有张 王 李 赵 陈 个课外小组 物理 化 学 生物组 今有张 王 李 赵 陈5 名同学 若已知 名同学 若已知 1 张 王为物理组成员 张 李 赵 为化学组成员 李 赵 陈为生物组成 员 张 王为物理组成员 张 李 赵 为化学组成员 李 赵 陈为生物组成 员 2 张为物理组成员 王 李 赵为化 学组成员 王 李 赵 陈为生物组成 员 张为物理组成员 王 李 赵为化 学组成员 王 李 赵 陈为生物组成 员 3 张为物理组和化学组成员 王 李 赵 陈为生物组成员 问在以上 张为物理组和化学组成员 王 李 赵 陈为生物组成员 问在以上3种情况下能否各选出种情况下能否各选出3名不兼 职的组长 名不兼 职的组长 生物生物 物理化 学 张王李赵陈 物理化 学 张王李赵陈 物理化 学生物 陈赵李王张 生物 物理化 学生物 陈赵李王张 生物物理 化 学 陈赵李王张 物理化 学 陈赵李王张 2006 5 31北京邮电大学电子工程学院10 8 2 欧拉图欧拉图 问题的提出 问题的提出 1736年欧拉关于哥尼斯堡七桥问题 能否设计一 次遍游 使得从某地出发对每座桥只走一次 遍历了 这七桥之后回到原地 年欧拉关于哥尼斯堡七桥问题 能否设计一 次遍游 使得从某地出发对每座桥只走一次 遍历了 这七桥之后回到原地 D AB C 结论 七桥问题是无解的 结论 七桥问题是无解的 2006 5 31北京邮电大学电子工程学院11 定义定义8 4 给定无孤立点的无向图给定无孤立点的无向图G 若存在一条 路 经过图中每边一次且仅一次 则称这条路为欧拉 路 若存在一条回路 经过图中每边一次且仅一次 则称这条路为欧拉回路 若存在一条 路 经过图中每边一次且仅一次 则称这条路为欧拉 路 若存在一条回路 经过图中每边一次且仅一次 则称这条路为欧拉回路 具有欧拉回路的图称为欧拉图 具有欧拉回路的图称为欧拉图 2006 5 31北京邮电大学电子工程学院12 定理定理8 4 无向图无向图G具有一条欧拉路 具有一条欧拉路 G是连通的 且 有零个或两个奇数度顶点 证明 是连通的 且 有零个或两个奇数度顶点 证明 设设G具有欧拉路 不妨假设具有欧拉路 不妨假设v0e1v1e2 ekvk 其中顶点可以重复出现 但边一定不重复 而 欧拉图一定是经过图 其中顶点可以重复出现 但边一定不重复 而 欧拉图一定是经过图G的所有顶点的 因此图的所有顶点的 因此图G连 通 对任何一个不是端点的顶点 连 通 对任何一个不是端点的顶点vi 在欧拉路中只要 出现一次必关联两条边 故 在欧拉路中只要 出现一次必关联两条边 故vi虽可重复出现 但虽可重复出现 但deg vi 必为偶数 对于端点 若必为偶数 对于端点 若v0 vk 则 则deg v0 必为偶数 若 必为偶数 若v0 vk 则 则deg v0 和和 deg vk 必为奇数 充分性 构造一条欧拉路 略 必为奇数 充分性 构造一条欧拉路 略 2006 5 31北京邮电大学电子工程学院13 推论推论 无向图无向图G具有一条欧拉回路 具有一条欧拉回路 G是连通的 且所有顶点的度数为偶数 由上述判断定理 显然哥尼斯堡七桥问题无解 与哥尼斯堡七桥问题类似的有一笔画问题 从图 是连通的 且所有顶点的度数为偶数 由上述判断定理 显然哥尼斯堡七桥问题无解 与哥尼斯堡七桥问题类似的有一笔画问题 从图 G中某一顶点出发 经过图中某一顶点出发 经过图G的每一边一次且仅一次 到达另一顶点 或从图 的每一边一次且仅一次 到达另一顶点 或从图G中某一顶点出发 经过图中某一顶点出发 经过图G 的每一边一次且仅一次再回到该顶点 它也分别可用 欧拉路和欧拉回路来解决 的每一边一次且仅一次再回到该顶点 它也分别可用 欧拉路和欧拉回路来解决 2006 5 31北京邮电大学电子工程学院14 下面讨论对有向图的情形 定义 下面讨论对有向图的情形 定义8 5 给定有向图给定有向图G 经过图中每边一次且仅 一次的一条单向路 称为单向欧拉路 经过图中每边一次且仅 一次的一条单向路 称为单向欧拉路 定理定理8 5 有向图有向图G具有一条单向欧拉回路 具有一条单向欧拉回路 G是 连通的 且每个顶点的入度等于出度 有向图 是 连通的 且每个顶点的入度等于出度 有向图G具有 单向欧拉路 具有 单向欧拉路 G是连通的 且除两个顶点外 每个顶 点的入度等于出度 对这两个顶点 一个顶点的入度 比出度大 是连通的 且除两个顶点外 每个顶 点的入度等于出度 对这两个顶点 一个顶点的入度 比出度大1 另一个顶点的入度比出度小 另一个顶点的入度比出度小1 分析 分析 若入度与出度相等 则该点的总度数为偶 数 若入度与出度之差为 若入度与出度相等 则该点的总度数为偶 数 若入度与出度之差为1 则其总度数为奇数 则其总度数为奇数 2006 5 31北京邮电大学电子工程学院15 例例8 2 证明彼得森图既不是二部图 也不是欧拉图 证明彼得森图既不是二部图 也不是欧拉图 证明 彼得森证明 彼得森Petersen图中 存在奇数长度的回路 因此不 是二部图 每个顶点的度数均 为 图中 存在奇数长度的回路 因此不 是二部图 每个顶点的度数均 为3 不满足欧拉图的判别条 件 因此不是欧拉图 不满足欧拉图的判别条 件 因此不是欧拉图 2006 5 31北京邮电大学电子工程学院16 8 3 哈密顿图哈密顿图 定义定义8 6 经过图中每个顶点一次且仅一次的通路 称 为 经过图中每个顶点一次且仅一次的通路 称 为哈密顿通路哈密顿通路 经过图中每个顶点一次且仅一次的回 路 称为 经过图中每个顶点一次且仅一次的回 路 称为哈密顿回路哈密顿回路 具有哈密顿回路的图称为哈密 顿图 具有哈密顿回路的图称为哈密 顿图 显然 左图中存在哈密顿通 路 但无哈密顿回路 因此不 是哈密顿图 一个 显然 左图中存在哈密顿通 路 但无哈密顿回路 因此不 是哈密顿图 一个n阶简单图是哈密顿 图 必须有 阶简单图是哈密顿 图 必须有m n 2006 5 31北京邮电大学电子工程学院17 显然 左图 显然 左图 7个顶点 个顶点 6条 边 既无哈密顿回路 也无哈 密顿通路 更不是哈密顿图 条 边 既无哈密顿回路 也无哈 密顿通路 更不是哈密顿图 一个一个n阶简单图是哈密顿 图 必须有 阶简单图是哈密顿 图 必须有m n 左图红色标注为哈密顿回路 因此是哈密顿图 左图红色标注为哈密顿回路 因此是哈密顿图 2006 5 31北京邮电大学电子工程学院18 定理定理8 6 设无向图设无向图G 是哈密顿图 是哈密顿图 V1 是任意的非空子集 则 是任意的非空子集 则 p G V1 V1 其中 其中 p G V1 是从是从G中删除中删除V1 后所得图的连 通分支数 证明 设 后所得图的连 通分支数 证明 设C是是G中的一条哈密顿回路 中的一条哈密顿回路 1 若 若V1 中的顶点在中的顶点在C上彼此相邻 则 上彼此相邻 则 p C V1 1 V1 2 若 若V1 中的顶点在中的顶点在C上存在上存在r 2 r V1 个互不相邻 则 个互不相邻 则 p C V1 r V1 一般地 一般地 V1 中的顶点在中的顶点在C上既有相邻的 也有不相邻的 则 上既有相邻的 也有不相邻的 则 p C V1 V1 而 而C是是G的生成子图 则 的生成子图 则 p G V1 p C V1 V1 2006 5 31北京邮电大学电子工程学院19 上述定理虽然不是哈密顿图的判别条件 但是上述定理虽然不是哈密顿图的判别条件 但是p G V1 V1 是该图为哈密顿图的必要条件 因此可借助 于该定理判断一些图不是哈密顿图 是该图为哈密顿图的必要条件 因此可借助 于该定理判断一些图不是哈密顿图 v 设设V1 v 则 则p G V1 2 1 V1 所以左图不是哈密顿图 所以左图不是哈密顿图 2006 5 31北京邮电大学电子工程学院20 v 设设V1 v 则 则 p G V1 2 V1 1 则由定 理 则由定 理8 6知左上图不 是哈密顿图 知左上图不 是哈密顿图 2006 5 31北京邮电大学电子工程学院21 对对Petersen图 在图中删去 任一顶点或任意 图 在图中删去 任一顶点或任意2个顶点 所得到的图仍然连通 删去 个顶点 所得到的图仍然连通 删去 3个顶点 最多只能得到个顶点 最多只能得到2个 连通分支的子图 删去 个 连通分支的子图 删去4个 顶点 最多只能得到 个 顶点 最多只能得到3个连 通分支的子图 删去 个连 通分支的子图 删去5个及个及5 个以上的顶点 余下子图的 顶点数必小于等于 个以上的顶点 余下子图的 顶点数必小于等于5 则所 有情况均满足定理 则所 有情况均满足定理8 6 但 但 Petersen图确实不是哈密尔 顿图 图确实不是哈密尔 顿图 定理定理8 6只是必要条件 不是充分条件 只是必要条件 不是充分条件 2006 5 31北京邮电大学电子工程学院22 虽然哈密尔顿回路问题与欧拉回路问题在形式上 非常相似 但我们已经找到一个图是否是欧拉图的判 别条件 但对一个图是否是哈密顿图却还没有判别条 件 直到目前为止 只有某些特殊情况下才有判别 法 虽然哈密尔顿回路问题与欧拉回路问题在形式上 非常相似 但我们已经找到一个图是否是欧拉图的判 别条件 但对一个图是否是哈密顿图却还没有判别条 件 直到目前为止 只有某些特殊情况下才有判别 法 2006 5 31北京邮电大学电子工程学院23 定理定理8 7 设设G 是是n阶无向简单图 若阶无向简单图 若G中每一 对不相邻的顶点的度数之和大于等于 中每一 对不相邻的顶点的度数之和大于等于n 1 则在 则在G中存 在一条哈密顿路 证明 首先说明 中存 在一条哈密顿路 证明 首先说明G是连通图 若是连通图 若G中有中有2个或更多个互 不连通的子图 设第 个或更多个互 不连通的子图 设第1个子图有个子图有n1个顶点 任取其中的 一个顶点 个顶点 任取其中的 一个顶点V1 设第 设第2个子图有个子图有n2个顶点 任取其中的一 个顶点 个顶点 任取其中的一 个顶点V2 因为 因为d V1 n1 1 d V2 n2 1 则 则 d V1 d V2 n1 n2 1 与已知条件矛盾 则与已知条件矛盾 则G必 连通 其次 从一条边出发构造一条哈密顿路 略 必 连通 其次 从一条边出发构造一条哈密顿路 略 2006 5 31北京邮电大学电子工程学院24 推论推论 设设G 是是n阶无向简单图 若阶无向简单图 若G中每一 对不相邻的顶点的度数之和大于等于 中每一 对不相邻的顶点的度数之和大于等于n 则 则G是哈密顿 图 是哈密顿 图 注意 定理注意 定理8 7 和推论只是无向图和推论只是无向图G具有哈密顿通路和 哈密顿回路的充分条件 而不是必要条件 关于有向图的哈密顿通路和哈密顿回路在某些特 殊情况下的充分条件见定理 具有哈密顿通路和 哈密顿回路的充分条件 而不是必要条件 关于有向图的哈密顿通路和哈密顿回路在某些特 殊情况下的充分条件见定理8 8 略 略 2006 5 31北京邮电大学电子工程学院25 8 4 平面图平面图 在图论中 图的平面化问题非常重要 如印刷线 路板的布线 交通道的设计等 下面就无向图进行讨 论 在图论中 图的平面化问题非常重要 如印刷线 路板的布线 交通道的设计等 下面就无向图进行讨 论 定义定义8 7 若能够把图若能够把图G的所有顶点和边画在平面 上 且使得任何两条边除了端点外没有其它的交点 则称 的所有顶点和边画在平面 上 且使得任何两条边除了端点外没有其它的交点 则称G是一个平面图 是一个平面图 表面看它 不是平面 图 表面看它 不是平面 图 实质上它是 平面图 实质上它是 平面图 2006 5 31北京邮电大学电子工程学院26 有的图无论怎样改画 除去顶点外 总有边相交 这种图就不是平面图 如下图 有三间房子 分别连接水 煤气和电 有的图无论怎样改画 除去顶点外 总有边相交 这种图就不是平面图 如下图 有三间房子 分别连接水 煤气和电3个 接口 个 接口 无论怎样改画 至少有一条边与其它边相交 无论怎样改画 至少有一条边与其它边相交 左图不 是平面图 左图不 是平面图 2006 5 31北京邮电大学电子工程学院27 定义定义8 8 设设G是一个连通的平面图 由是一个连通的平面图 由G中的边所包围的区 域 在区域中既不包含图的顶点 也不包含图的边 这样的区 域称为 中的边所包围的区 域 在区域中既不包含图的顶点 也不包含图的边 这样的区 域称为G的一个面 包围该面的诸边所构成的回路称为这个面 的边界 边界的长度称为该面的次数 的一个面 包围该面的诸边所构成的回路称为这个面 的边界 边界的长度称为该面的次数 R的次数记为的次数记为deg R A B C D E 1 23 4 6 5 右图 右图 6个顶点个顶点9条边 它把 平面分成 条边 它把 平面分成5个区域个区域A B C D E 其中 其中A B C D四 个面由回路构成边界 四 个面由回路构成边界 E为无 限面 显然 为无 限面 显然 deg A 3 deg B 4 deg C 3 deg E 3 deg D 5 5 4 3 4 6 5 deg A deg B deg C deg D deg E 18 2 9 2006 5 31北京邮电大学电子工程学院28 定理定理8 8 一个有限平面图 面的次数之和等于其 边数的 一个有限平面图 面的次数之和等于其 边数的2倍 证明 任何一条边 或者是两个面的公共边 或者在 一个面中作为边界被重复计算两次 则定理成立 倍 证明 任何一条边 或者是两个面的公共边 或者在 一个面中作为边界被重复计算两次 则定理成立 2006 5 31北京邮电大学电子工程学院29 定理定理8 9 欧拉定理 欧拉定理 设有一个连通的平面图设有一个连通的平面图G 共 有 共 有n个顶点 个顶点 m条边 条边 r个面 则 个面 则 n m r 2 证明 对边数 证明 对边数m进行归纳证明 进行归纳证明 1 m 0 G为孤立点 此时为孤立点 此时n 1 r 1 结论成立 结论成立 2 m 1 即 即n 2 r 1 结论成立 结论成立 3 设 设m k成立 即成立 即nk mk rk 2 考察考察m k 1的情形 的情形 v 情形情形1 加上一个新的顶点 加上一个新的顶点V V 与图中的一个顶点相连 此时顶 点和边数都增加 与图中的一个顶点相连 此时顶 点和边数都增加1 而面数不改 变 因此结论仍然成立 而面数不改 变 因此结论仍然成立 2006 5 31北京邮电大学电子工程学院30 情形情形2 用一条边连接图上已知 的两个顶点 此时边和面均增加 用一条边连接图上已知 的两个顶点 此时边和面均增