中国邮路问题中国邮递员问题⼀个邮递员送信，要⾛完他负责投递的所有街道（所有街道都是双向通⾏的且每条街道能够经过不⽌⼀次），完毕任务后回到邮局，应按如何的路线⾛，他所⾛的路程才会最短呢？解决⽅式1、图论建模因为街道是双向通⾏的，我们能够把它看成是赋权⽆向连通图，将路⼝模型为点，街道模型为边，街道的长度就是每条边的权值，问题转化为在图中求⼀条回路，使得回路的总权值最⼩。
1.1最理想的情况若图中有欧拉回路，由于欧拉回路通过全部的边，因此不论什么⼀个欧拉回路即为此问题的解。
1.2若G仅仅有两个Vi,Vj则有从Vi到Vj的欧拉迹，从Vj回到Vi则必须反复⼀些边，使反复边的总长度最⼩，转化为求从Vi到Vj的最短路径。
算法：1）找出奇点Vi,Vj之间的最短路径P；2）令G’ = G + P；3）G’为欧拉图，G’的欧拉回路即为最优邮路。
1.3普通情况，奇点数⼤于2的时，邮路必须反复很多其它的边。
Edmonds算法（匈⽛利算法）思想：步骤：1）求出G全部奇点之间的最短路径和距离；2）以G的全部奇点为结点（必为偶数），以他们之间的最短距离为节点之间边的权值，得到⼀个全然图G1；3）将M中的匹配边（Vi，Vj）写成Vi与Vj之间的最短路径经过的全部边集合Eij；4）令G’ = G U { Eij | (Vi,Vj)属于M}，则G’是欧拉图，求出最优邮路。
2、详细模块实现2.1最短路径⽤ Dijkstra算法计算Dijkstra算法是⼀种最短路径算法，⽤于计算⼀个节点到其他全部节点的最短路径。
2.1.1算法思想：按路径长度递增次序产⽣最短路径算法： 把V分成两组： 1）S：已求出最短路径的顶点的集合 2）V-S=T：尚未确定最短路径的顶点集合将T中顶点按最短路径递增的次序增加到S中，保证：1）从源点V0到S中各顶点的最短路径长度都不⼤于从V0到T中不论什么顶点的最短路径长度 2）每⼀个顶点相应⼀个距离值 S中顶点：从V0到此顶点的最短路径长度 T中顶点：从V0到此顶点的仅仅包含S中顶点作中间顶点的最短路径长度2.1.2求最短路径步骤 1）初始时令 S={V0},T={ 其余顶点}，T中顶点相应的距离值 若存在<V0,Vi>，d(V0,Vi)为<V0,Vi>弧上的权值；若不存在<V0,Vi>，d(V0,Vi)为∝ 2）从T中选取⼀个其距离值为最⼩的顶点W且不在S中，增加S 3）对S中顶点的距离值进⾏改动：若加进W作中间顶点，从V0到Vi的距离值缩短，则改动此距离值；反复上述步骤2、3，直到S中包括全部顶点，即W=Vi为⽌2.2图的连通性測试检測⽤户输⼊的图是否是连通图，不是的话没办法求解，提醒⽤户⼜⼀次输⼊。
☐图的存储表示；☐顶点的度数；☐图的连通性；☐顶点间的最短路径；☐欧拉图的判断，欧拉回路输出；问题描述：一个邮递员从邮局出发走遍每条街道，最后返回邮局，找到一条最短的行走线路？最短欧拉回路！问题提出：我国数学家管梅谷先生在20世纪60年代提出一笔画游戏✈✈满足“一笔画”：☐凡是由偶点组成的连通图,一定可以一笔画成.画时可以把任一偶点为起点,最后一定能以这个点为终点画完此图☐凡是只有两个奇点的连通图（其余都为偶点）,一定可以一笔画成.画时必须把一个奇点为起点,另一个奇点终点☐其他情况的图都不能一笔画出实例：一个邮递员投递信件要走的街道如图所示，图中的数字表示各条街道的千米数，他从邮局出发，要走遍各街道，最后回到邮局。
怎样走才能使所走的行程最短？全程多少千米？ 2 1 2111怎么样使非欧拉图变为欧拉图？除去奇点！添加边或删除边。
怎么样除去奇点？这里应该采用的办法？重复某些边（添加边）2 1 23分析：图中共有8个奇点，不可能不重复地走遍所有的路。
必须在8个奇点间添加4条线，才能消除所有奇点，从而成为能从邮局出发最后返回邮局的一笔画。
当然要在距离最近的两个奇点间添加一条连线，图中虚线所示，共添加4条连线，这4条连线表示要重复走的路，显然，这样重复走的路程最短，全程34千米。
走法不唯一邮局2 1 2111 2 1 23☐建立街区无向网的邻接矩阵；☐求各顶点的度数；☐求出所有奇度点；☐图的连通性判断；☐求出每一个奇度点到其它奇度结点的最短路径；☐根据最佳方案添加边，对图进行修改，使之满足一笔画；☐对图进行一笔画，并输出；其一：“添加”哪些边？☐“添加”的边所依附的顶点必须均是奇度顶点☐“添加”的边必须是已有的边，也就是有的边不止走一次其二：如何选择代价最小的边？☐奇数顶点之间的最短路径☐Dijstra算法☐Floyd算法其三：输出一笔画？☐FE算法（F leury E uler）V4U1U6V3U5U2V1U4V2U31111111222222533V4V3V1V241.求奇度点的最短路径2.构造奇度点间的完全加权图3.求图的最佳（总权最小）完备匹配M={1,4;2,3}4.求1和4之间的最短轨V1 U1 V4；2和3之间的最短轨V2 U4 V3；5. 加同权边即可一个实例如果一个匹配中，图中的每个顶点都和图中某条边相关联，则称此匹配为完全匹配，也称作完备匹配给定一个图G ，M 为G 边集的一个子集，如果M 满足当中的任意两条边都不依附于同一个顶点，则称M 是一个匹配1.求奇度点的最短路径2.构造奇度点间的完全加权图3.求图的最佳（总权最小）完备匹配M={1,4;2,3}4.求1和4之间的最短轨V1 U1 V4；2和3之间的最短轨V2 U4 V3；5. 加同权边即可给定一个图G，M为G边集的一个子集，如果M满足当中的任意两条边都不依附于同一个顶点，则称M是一个匹配如果一个匹配中，图中的每个顶点都和图中某条边相关联，则称此匹配为完全匹配，也称作完备匹配1.取G 中的起始顶点V 0，令P 0=V 02.假设沿着P i = v 0e 1v 1e 2v 2…e i v i 走到顶点vi ，按下面方法从E(G)-{e 1,e 2,…,e i }中选e i+1①e i+1与v i 相关联；②除非没有别的边可供选择，否则e i+1不应该是G i =G-{e 1,e 2,…,e i }中的桥3.当2不能再进行时算法停止V4V1V2V5V6V7V8V3V4V1V2V5V6V7V8V3总结步骤1.求图G中奇度结点集合V0={v}；2.对V0中的每个顶点对u，v，用Dijkstra算法求距离d(u,v)；3.构造加权完全图；4.求加权图的总权最小的完备匹配M；5.在G中求M中同一边的结点间的最短轨；6.把G中在上一步求得的每条最短轨之边变成同权倍边，得到欧拉图G1；7.用FE算法求G1的一条欧拉回路W，W即为解；举例：邮递员要从邮局出发，走遍左下图(单位：千米)中所有街道，最后回到邮局，怎样走路程最短？全程多少千米？其二：如何选择代价最小的边？☐奇数顶点之间的最短路径☐Dijstra算法☐Floyd算法☐最小生成树的方法☐Prim算法☐Kruskal算法奇度结点间最短路径计算➢如果只有两个奇度结点，那么最短路径就是原来每条街道代价加上两个奇度顶点之间的最短代价之和；➢如果有多个奇度结点，要进行不同的组合。
