PDF《欧拉图与哈密顿图》

欧拉图与哈密顿图 欧拉图与哈密顿图 欧拉图与哈密顿图 欧拉图与哈密顿图 高晓h 高晓h 高晓h 高晓h ( ( ( (Xiaofeng Gao) ) ) ) Euler and Hamilton Graph Department of Computer Science Shanghai Jiao Tong Univ.

1 2 欧拉道路与欧拉回路 欧拉道路与欧拉回路 欧拉道路与欧拉回路 欧拉道路与欧拉回路 哈密顿道路与哈密顿回路 哈密顿道路与哈密顿回路 哈密顿道路与哈密顿回路 哈密顿道路与哈密顿回路 目录 目录 目录 目录 2016/12/6

2 IntroductionToCS--Xiaofeng Gao Euler Path and Euler Circuit 欧拉道路与欧拉回路 2016/12/6

3 IntroductionToCS--Xiaofeng Gao 欧拉回路 【 【 【 【定义 定义 定义 定义】 】 】 】给定无向连通图 给定无向连通图 给定无向连通图 给定无向连通图G=(V, E),包含 ,包含 ,包含 ,包含 图图图图G的所有边 的所有边 的所有边 的所有边的简单道路称为 的简单道路称为 的简单道路称为 的简单道路称为欧拉道路 欧拉道路 欧拉道路 欧拉道路(或或或或欧拉 欧拉 欧拉 欧拉通道 通道 通道 通道、 、 、 、欧拉迹 欧拉迹 欧拉迹 欧拉迹) , , , , 包含 包含 包含 包含图 图图图G的所有边 的所有边 的所有边 的所有边的简单回路称为 的简单回路称为 的简单回路称为 的简单回路称为欧拉回路 欧拉回路 欧拉回路 欧拉回路 (或或或或欧拉闭迹 欧拉闭迹 欧拉闭迹 欧拉闭迹) . . . . 假设 假设 假设 假设G没有孤立点,若 没有孤立点,若 没有孤立点,若 没有孤立点,若G含有 含有 含有 含有欧拉回路 欧拉回路 欧拉回路 欧拉回路, , , ,则则则则称称称称G是是是是欧拉图 欧拉图 欧拉图 欧拉图. . . . 2016/12/6

4 IntroductionToCS--Xiaofeng Gao 【 【 【 【定理 定理 定理 定理】 】 】 】图图图图G是欧拉图的充要条件是 是欧拉图的充要条件是 是欧拉图的充要条件是 是欧拉图的充要条件是G连通 连通 连通 连通 且没有奇点. 且没有奇点. 且没有奇点. 且没有奇点. 【 【 【 【证证证证】 】 】 】必要性 必要性 必要性 必要性 : : : : 若若若若G中有 中有 中有 中有欧拉回路 欧拉回路 欧拉回路 欧拉回路C,则则则则C过每一条边有且仅 过每一条边有且仅 过每一条边有且仅 过每一条边有且仅 有一次.对 有一次.对 有一次.对 有一次.对任一节点 任一节点 任一节点 任一节点v,如果 如果 如果 如果C由由由由ei进入 进入 进入 进入v, 则则则则一定通过另一条边 一定通过另一条边 一定通过另一条边 一定通过另一条边ej从从从从v离开.因此 离开.因此 离开.因此 离开.因此v的度是 的度是 的度是 的度是 偶数 偶数 偶数 偶数. . . . 欧拉图定理 2016/12/6

5 IntroductionToCS--Xiaofeng Gao 充分性 充分性 充分性 充分性 :由于 :由于 :由于 :由于G是有穷图,因此可断定从 是有穷图,因此可断定从 是有穷图,因此可断定从 是有穷图,因此可断定从 G的任一节点 的任一节点 的任一节点 的任一节点v0出发一定存在 出发一定存在 出发一定存在 出发一定存在G的一条简单 的一条简单 的一条简单 的一条简单 回路 回路 回路 回路C.这是因为各节点的度都是偶数,所 .这是因为各节点的度都是偶数,所 .这是因为各节点的度都是偶数,所 .这是因为各节点的度都是偶数,所 以这条简单回路不可能停留在 以这条简单回路不可能停留在 以这条简单回路不可能停留在 以这条简单回路不可能停留在v0以外的某个 以外的某个 以外的某个 以外的某个 节点,而不能再向前伸延以构成闭通道 节点,而不能再向前伸延以构成闭通道 节点,而不能再向前伸延以构成闭通道 节点,而不能再向前伸延以构成闭通道C. . . . 如果 如果 如果 如果E=C, 则则则则C就是欧拉回路,充分性得证. 就是欧拉回路,充分性得证. 就是欧拉回路,充分性得证. 就是欧拉回路,充分性得证. 否则在 否则在 否则在 否则在G中删去 中删去 中删去 中删去C的各边,得到 的各边,得到 的各边,得到 的各边,得到G1=GD D D DC. . . . 2016/12/6