第五章 可行遍性问题.pdfVIP

第五章 可行遍性问题 §5.1 一笔画与 Euler 回路 经过图 G 每边一次且只有一次，并且回到始点的回路， 称为 Euler 回路，图 G 称为 Euler 图，简称 E 图。 定理 1：（1） G 是 Euler 图⇔G 的每个顶点的次数均为偶数。 d ⇔ .C 是边互不相交的回路。 G C ∪ i i i 1 ⇒以任一点为起点可以一笔画。 （2）G 连通且恰有也只有两个奇次顶点时，G 可一 笔画，此两顶点可作为 Euler 路径的端点。 例 1 判别一笔画问题 两个三次顶点 四个奇次顶点 两个五次顶点 当图很简单时，Euler 回路 （路径）较易找，但当图较复杂 时，就不容易找了。 一个图若不是 E 图，但它的子图可以是 E 图，称为 E 子图 例 2 b b b a c a c a c d e d e e 可一笔画，但非E 图 G1 G2 两个E 子图 1 G G G G G ⊕ 定理 2：若 和 是图 的 E 子图，则环和 也是 G 的 E 1 2 1 2 子图 G G 证：令GG ⊕G ，它是由 和 所特有的边构成的图 1 2 1 2 ∀v ∈G G 对 ，设在 中与 v 相关联的边有 r 条，分别为 1