(数学模型 定理1对于非空连通图G,下列命题等价: (1)G是欧拉图 (2)G无奇次顶点 (3)G的边集能划分为圈 欧拉图 非欧拉图 推论1设G是非平凡连通图,则G有欧拉道路的充要条 件是G最多只有两个奇次顶点 返回
定理１ 对于非空连通图 G，下列命题等价： （１）G 是欧拉图． （２）G 无奇次顶点． （３）G 的边集能划分为圈． 推论１ 设 G 是非平凡连通图，则 G 有欧拉道路的充要条 件是 G 最多只有两个奇次顶点． e3 v1 v2 v3 v4 e1 e4 e5 e2 e3 v1 v2 v3 v4 e1 e4 e5 e2 e6 欧拉图 非欧拉图 返回
(数学模型 中国邮递员问题-定义 邮递员发送邮件时,要从邮局出发,经过他投递范围内的 每条街道至少一次,然后返回邮局,但邮递员希望选择一条行 程最短的路线.这就是中国邮递员问题 若将投递区的街道用边表示,街道的长度用边权 表示,邮局街道交叉口用点表示,则一个投递区构成 个赋权连通无向图.中国邮递员问题转化为:在 个非负加权连通图中,寻求一个权最小的巡回.这样 的巡回称为最佳巡回
中国邮递员问题-定义 邮递员发送邮件时，要从邮局出发，经过他投递范围内的 每条街道至少一次，然后返回邮局，但邮递员希望选择一条行 程最短的路线．这就是中国邮递员问题. 若将投递区的街道用边表示，街道的长度用边权 表示，邮局街道交叉口用点表示，则一个投递区构成 一个赋权连通无向图．中国邮递员问题转化为：在一 个非负加权连通图中，寻求一个权最小的巡回．这样 的巡回称为最佳巡回．