PDF《欧拉图与哈密顿图》

12 IntroductionToCS--Xiaofeng Gao 欧拉道路(欧拉迹) 【 【 【 【推论 推论 推论 推论】 】 】 】若无向 若无向 若无向 若无向连通图 连通图 连通图 连通图G中只有 中只有 中只有 中只有2个度为奇数的顶 个度为奇数的顶 个度为奇数的顶 个度为奇数的顶 点.则点.则点.则点.则G中存在 中存在 中存在 中存在欧拉道路 欧拉道路 欧拉道路 欧拉道路. . . . 【 【 【 【证明 证明 证明 证明】 】 】 】设设设设vi和和和和vj是两个奇点,做 是两个奇点,做 是两个奇点,做 是两个奇点,做G'

=G+(vi,vj). . . . 则则则则G'

中各顶点的度都是偶数.由之前定理知, 中各顶点的度都是偶数.由之前定理知, 中各顶点的度都是偶数.由之前定理知, 中各顶点的度都是偶数.由之前定理知,G'

有欧拉回路,它包含 有欧拉回路,它包含 有欧拉回路,它包含 有欧拉回路,它包含(vi,vj)这条边.删去此边,即 这条边.删去此边,即 这条边.删去此边,即 这条边.删去此边,即 可得到一条从 可得到一条从 可得到一条从 可得到一条从vi到到到到vj的简单道路,它恰好经过了 的简单道路,它恰好经过了 的简单道路,它恰好经过了 的简单道路,它恰好经过了G 的所有边,即是一条欧拉道路. 的所有边,即是一条欧拉道路. 的所有边,即是一条欧拉道路. 的所有边,即是一条欧拉道路. 注:该推论实际是充分必要条件,即无向连通图 注:该推论实际是充分必要条件,即无向连通图 注:该推论实际是充分必要条件,即无向连通图 注:该推论实际是充分必要条件,即无向连通图 G中存在欧拉道路当且仅当 中存在欧拉道路当且仅当 中存在欧拉道路当且仅当 中存在欧拉道路当且仅当G中有零个或两个度为 中有零个或两个度为 中有零个或两个度为 中有零个或两个度为 奇数的节点. 奇数的节点. 奇数的节点. 奇数的节点. 2016/12/6

13 IntroductionToCS--Xiaofeng Gao 【 【 【 【例例例例】 】 】 】七桥问题既不存在欧拉回路也不存 七桥问题既不存在欧拉回路也不存 七桥问题既不存在欧拉回路也不存 七桥问题既不存在欧拉回路也不存 在欧拉道路 在欧拉道路 在欧拉道路 在欧拉道路. . . . 2016/12/6

14 IntroductionToCS--Xiaofeng Gao 范例 【 【 【 【例例例例】 】 】 】设连通图 设连通图 设连通图 设连通图G=(V,E)有有有有k个度为奇数的 个度为奇数的 个度为奇数的 个度为奇数的 节点,证明 节点,证明 节点,证明 节点,证明E(G)可以划分为 可以划分为 可以划分为 可以划分为k/2条简单道路. 条简单道路. 条简单道路. 条简单道路. 【 【 【 【证明 证明 证明 证明】 】 】 】易知 易知 易知 易知k是偶数.在这个 是偶数.在这个 是偶数.在这个 是偶数.在这个k个节点间 个节点间 个节点间 个节点间 添加 添加 添加 添加k/2条边,使得每个节点都与其中一条 条边,使得每个节点都与其中一条 条边,使得每个节点都与其中一条 条边,使得每个节点都与其中一条 边关联,得到 边关联,得到 边关联,得到 边关联,得到G'

,易知 ,易知 ,易知 ,易知G'

中各节点的度都 中各节点的度都 中各节点的度都 中各节点的度都 为偶数,故 为偶数,故 为偶数,故 为偶数,故G'

中有欧拉回路 中有欧拉回路 中有欧拉回路 中有欧拉回路C,这 ,这 ,这 ,这k/2条边 条边 条边 条边 都在 都在 都在 都在C上且不相邻接.故删去这些边,可以 上且不相邻接.故删去这些边,可以 上且不相邻接.故删去这些边,可以 上且不相邻接.故删去这些边,可以 得到 得到 得到 得到k/2条简单道路,它们包含了 条简单道路,它们包含了 条简单道路,它们包含了 条简单道路,它们包含了G的所有 的所有 的所有 的所有 边,即边,即边,即边,即E(G)划分成了 划分成了 划分成了 划分成了k/2条简单道路. 条简单道路. 条简单道路. 条简单道路. 2016/12/6