运筹学 Operations Research §6.3中国邮递员问题(CPP) 欧拉迹( Euler trail):经过图的每条边恰好一次的迹; 欧拉环游( Euler tour):闭的欧拉迹; 欧拉图( Euler graph):含有欧拉环游的图; 半欧拉图( Semi Euler graph):仅含有欧拉迹,不含有欧拉 环游的图 非欧拉图( NonEuler graph): otherwise 欧拉图G 2021/2/20
2021/2/20 1 运 筹 学 Operations Research §6.3 中国邮递员问题（CPP） 欧拉迹（Euler trail）：经过图的每条边恰好一次的迹； 欧拉环游（Euler tour）：闭的欧拉迹； 欧拉图（Euler graph）：含有欧拉环游的图； 半欧拉图（SemiEuler graph）：仅含有欧拉迹，不含有欧拉 环游的图； 非欧拉图（NonEuler graph）：otherwise
运筹学 Operations Research 半欧拉图G 非欧控图G 2021/2/20 2
2021/2/20 2 运 筹 学 Operations Research
运筹学 Operations Research hl(1736,Euer)设G为非空连通图,则 G是欧拉图分G不含有奇顶点; G是半欧拉图分→G恰含有两个奇顶点 证:(1) (2) 起点 终点 2021/2/20 3
2021/2/20 3 运 筹 学 Operations Research . 1 (1736 uler ) 是半欧拉图 恰含有两个奇顶点 是欧拉图 不含有奇顶点； ， 设 为非空连通图，则 G G G G Th E G 证：（1） （2） ▌
运筹学 Operations Research 几个结论: (1)若图G为欧拉图,则E≥v 证:G必为连通图,由7h,26=∑()≥2v→E≥v (2)K,为欧拉图分1为奇数(v≥3); K为欧拉图分m,n都为偶数 它们何时为半欧拉图? (3)非平凡树树必非欧拉图 证:∵非平凡树均至少有两个叶.■ 树可否为半欧拉图? 2021/2/20 4
2021/2/20 4 运 筹 学 Operations Research (1)若图G为欧拉图，则 . 几个结论： h1 2 = ( ) 2 . vV 证：G必为连通图， 由T 有， d v , . (2) ( 3); , 为欧拉图 都为偶数 为欧拉图 为奇数 K m n K m n 它们何时为半欧拉图？ (3)非平凡树树必非欧拉图. 证：∵非平凡树均至少有两个叶.▌ 树可否为半欧拉图？ ▌
运筹学 Operations Research “一笔画”问题: 能否一笔(无重笔)画出整个图? 对欧拉图,任选一个顶点为始点和终点,即可一笔画 对半欧拉图,任选两个奇度顶点的一个为始点,另一个为终 点,即可一笔画; 对非欧拉图,不可一笔画 可一笔画 可一笔画 不可一笔画 2021/2/20
2021/2/20 5 运 筹 学 Operations Research “一笔画”问题： 能否一笔（无重笔）画出整个图？ 对欧拉图，任选一个顶点为始点和终点，即可一笔画； 对半欧拉图，任选两个奇度顶点的一个为始点，另一个为终 点，即可一笔画； 对非欧拉图，不可一笔画