22 欧拉图与哈密顿图.ppt

第十五章欧拉图和哈密顿图 哥尼斯堡七桥问题 定义15 1欧拉通路 含所有边的简单通路 通过图中所有边一次仅一次且行遍所有定点的通路 欧拉回路 含所有边的简单回路欧拉图 有欧拉回路的图 例1在图7 47里 哪些无向图具有欧拉回路 在没有欧拉回路的那些图里 哪些具有欧拉通路 解 图G1具有欧拉回路 例如a e c d e b a G2和G3都没有欧拉回路 但是G3具有欧拉通路 即a c d e b d a b G2没有欧拉通路 图H2具有欧拉回路 例如a g c b g e d f a H1和H3都没有欧拉回路 H3具有欧拉通路 即c a b c d b 但是H1没有欧拉通路 定理15 1无向图G是欧拉图 G是连通的且没有奇度顶点 证明 先直观描述 显然 1 回路的存在性从连通图G中的任一节点v0开始 取关联于v0的边e1 v0 v1 因为d v1 为偶数 所以可以在G中继续取关联于v1的边e2 v1 v2 直到取到一条边ek 1 vk v0 得到一条简单回路h1 v0 e1 v1 e2 v1 ei 1 ek 1 v0 这里 ei ej i j 显然 h1 G 接下页 2 若h1 G 则G是欧拉图 否则转下一步 3 记H G h1 因为G是连通图 所以H与h1至少有一个节点重合 不妨记为vi 又因为h1中d vi 是偶数 故在H中d vi 仍是偶数 从而从图H的节点vi出发 重复步骤1的做法 又可得简单回路h2 vi e 1 v1 e 2 vi 这里ei ej i j 那么h1 h2所对应的简单回路是 v0 e1 v1 e2 vi e1 v1 e2 vi ei 1 ek 1 v0 不妨将h1 h2仍记为h2 转步骤2 对于有限图G 我们总可以在有限步骤中构造出简单回路h1 使得h1 G 故G是欧拉图 定理15 2无向图G是半欧拉图 G是连通的且恰有两个奇度顶点 定理15 2有向图D是欧拉图 D是强连通的且每个顶点的出度等于入度 定理15 3有向图D是半欧拉图 D是单向连通的且恰有两个奇度顶点 其中一个顶点的入度比出度大1 另一个顶点的出度比入度大1 定理15 5G是非平凡的欧拉图 G是连通的且是若干个边不重的圈的并 欧拉回路的求法 逐步插入回路法Fleury算法 例3一笔画问题能否用一笔画的方法画出图7 50所示的穆罕默德短弯刀 其中图形是在同一个顶点上开始和结束 解 可以解决这个问题 因为图7 50所示的图G具有欧拉回路 它具有这样的回路是因为它的所有顶点偶有偶数度 用算法1来构造欧拉回路 首先形成回路a b d c b e i f e a 通过删除这条回路的边并且删除因此产生的孤立点 就得到子图H 然后形成H中的回路d g h j i h k g f d 形成这条回路之后就用完了G中的所有边 在适当的地方拼接这条回路和第一条回路 就产生出欧拉回路 a b d g h j i h k g f d c b e i f e a 这条回路给出了铅笔不离开纸面并且不重复地画出弯刀的方法 接下页 接上页 算法1构造欧拉回路procedureEuler G 所有顶点有偶数度的连通多重图 circuit 在G中任选的顶点开始连续地加入边所形成的回到该顶点的回路H 删除这条回路的边之后的GwhileH还有边beginsubcircuit 在既是H中的顶点也是circuit一条边的端点开始的H中的一条回路H 删除subcircuit的边和所有孤立点之后的HCircuit 在适当顶点上插入subcircuit之后的circuitend circuit是欧拉回路 哈密顿图定义15 2哈密顿通路 经过所有顶点一次且仅一次的通路哈密顿回路 经过所有顶点一次且仅一次的回路哈密顿图 有哈密顿回路的图 哈密顿的智力题 木质十二面体 有十二个正五边形表面 二十个顶点 顶点标记为不同的城市 每个顶点上有钉子 另有一细线 目标是从一个城市开始 沿十二面体的边旅行 访问其他19个城市 每个恰好一次 回到第一个城市结束 旅行经过的回路用钉子和细线来标记 哈密顿图的必要条件没有1度的顶点2度顶点的边必定在哈密顿回路上与一个顶点关联的边中有且仅有两条在哈密顿回路上哈密顿回路中没有小回路对V的任意非空子集S 有p G S S G S是从G中删除S中的顶点及其关联边 定理15 6 后余下的图 p G S 表示图G S的连通分支的数目 例6证明图7 35中的图没有哈密顿回路 证明 G中没有哈密顿回路 因为G有1度顶点 即e 现在考虑H 因为顶点a b d和e的度都为2 所以这些顶点关联的每一条边都必然属于任意一条哈密顿回路 现在容易看出H中不存在哈密顿回路 因为任何这样的哈密顿回路都不得不包含4条关联c的边 这是不可能的 例7Kn n 2 是哈密顿图解 从Kn中的任意一个顶点开始来形成哈密顿回路 以所选择的任意顺序来访问顶点 只要求通路在同一个顶点开始和结束 而且恰好访问其他每个顶点一次 这样做是可能的 因为在Kn中任意两个顶点之间都有边 定理哈密顿图的充分条件若G是n个节点的无向连通简单图 其任一节点v满足d v n 2 则G是哈密顿图 证明 为证这个结论 我们先给出一个引理 若G V E 是有n个节点的无向简单图 对于每一对不相邻的节点u v 有d u d v n 则G是哈密顿图的充分必要条件是H V E e 为哈密顿图 这里e是与节点u v关联的无向边 接下页 现在我们来证明 若G中对于每一对不相邻的节点u v 有d u d v n 则G是哈密顿图 因为若在G中每一对不相邻节点u v之间连一条无向边 得到图H 则H是n阶无向完全图 从而H是哈密顿图 由引理 可知G是哈密顿图 由2 我们可直接推出若任一节点v满足d v n 2 则G是哈密顿图 例8格雷码及其应用 构造长度为n的2进制编码的序列 使相邻的码仅相差1位用Qn来建模 接下页 解 格雷码是圆周的弧的一种标记 使得相邻的弧具有恰好相差一位的位串标记 在图7 56b 里的赋值是一个格雷码 可以这样找出格雷码 以下述的方式列出所有长度为n的位串 使得每一个位串与前一个位串恰好相差一位 而且最后一个位串与第一个位串恰好相差一位 可以用n立方体Qn来为这个问题建模 解决这个问题所需要的是Qn中的一条哈密顿回路 这样的哈密顿回路容易求出 例如 Q3的一条哈密顿回路所产生的前后恰好相差一位的位