图论方法最小树最短路,邮路完整版

图论方法例：已知有6名运动员，赵，参加ABD三个项目钱，参加ABE三个项目孙，参加CDF三个项目李，参加ADF三个项目周，参加CE两个项目吴，参加DF两个项目如何安排比赛顺序，使每个运动员在2个项目之间有休息时间？A,C,B,F,E,DABFDBCDE最小树问题定义1：树------一个无圈的连通图称为树。定理：设图G=(V,E)是一个树，点数大于等于2，则G中至少有2个悬挂点。定理：图G=(V,E)是一个树的充分必要条件是图G不含圈。定理：图G=(V,E)是一个树的充分必要条件是图G是连通图，且边数等于点数减1.定理：图G=(V,E)是一个树的充分必要条件是任意2个顶点之间恰有一条链。树图可以描述组织机构、家谱、学科分支、通信网络、高压线路网络等等Vi表示自来水厂和用户，Vi和Vj之间的边表示两点间可以铺设管道，权为Vi和Vj之间铺设管道的距离或费用。如何铺设管道，使自来水厂V1将自来水送到5个用户并且使总费用最小。V1V2V3V4V5V68854375261演示破圈法V1V2V3V4V5V68854375261V1V2V3V4V5V64321最小树问题例4.已知有5个城市，要在它们之间架设电话线，要求任何2个城市都可以互通电话（允许通过其他城市），并且电话线的根数最少。树图：某工厂的组织结构图厂长行政办公室生产办公室生产计划科技术科供销科财务科行政科设计组工艺组一车间二车间三车间四车间铸造工段锻压工段图的支撑树

定义2：设图T=(V,E’)是图G=(V,E)的支撑子图，如果图T=(V,E’)是一个树，则称T是G的一个支撑树。定理：图G有支撑树的充分必要条件是图G是连通的。图的最小支撑树

定义3：给图G=(V,E)，对G中的每一条边[vi,vj]，相应地有一个数wij，则称这样的图G为赋权图，wij称为边[vi,vj]上的权。这里的权是指与边有关的数量指标，如距离、时间、费用等。图的最小支撑树

定义4：如果图T=(V,E’)是图G=(V,E)的支撑树，称E’中所有边的权之和为支撑树T的权，记为w(T)，如果支撑树T*的权w(T*)是G的所有支撑树的权中最小者，则称T*是G的最小支撑树，简称最小树。最小支撑树问题就是要求给定连通赋权图G的最小支撑树。避圈法，破圈法寻找图的最小支撑树

避圈法，破圈法81065498793寻找图的最小支撑树

避圈法，破圈法654873寻找图的最小支撑树

避圈法81065498793寻找图的最小支撑树

破圈法654873最短路问题给定一个赋权有向图D=(V,A)，对每一个弧a=(vi,vj)，相应地有权w(a)=wij,又给定D中的2个顶点Vs,Vt。设P是D中从Vs到Vt的一条路，定义路P的权是P中所有弧的权之和，记为w(P)。最短路就是要在所有从Vs到Vt的路中，求一条权最小的路P0，称为最短路。路P0的权称为从Vs到Vt的距离。最短路问题算法当所有的wij≥0时，Dijkstra算法，1959年。Dijkstra算法的基本思想是从Vs出发，逐步地向外探寻最短路。执行过程中，与每个点对应，记录下一个数（称为该点的标号），它或者表示从Vs到该点的最短路的权，（称为P标号），或者是从Vs到该点的最短路的权的上界（称为T标号），方法的每一步是去修改T标号，并且把某一个具T标号的点改变为具P标号的点，从而使D中具P标号的点数多一个，这样，至多经过p-1步，就可以求出从Vs到各点的最短路。251234652035147446251234652035147446020232628321-4年的时间段如何更换电脑弧上的数字表示与替换设备有关的总成本，包括购买价、运营成本和维修成本。确定4年内的最小设备更换成本。012346005008007000100020002800210016001400600100018002500服务网点设置问题在一个网络中设置一所学校、医院、消防站、购物中心，还有厂址选择、总部选址、公司销售中心选址等问题都属于最佳服务网点设置问题小学选址问题1234567603020252030151815从村庄1到村庄1234567的最短路12345676030202520301518150305063934560小学选址问题12345676030202520301518150152030303363各村庄之间一步直达的最短距离村庄V1v2v3v4v5v6v7D(vi)V1030MMMMMV230020MM15MV3M200206025MV4MM2003018MV5MM60300MMV6M152518M015v7MMMMM1507个村庄相互之间的最短路村庄V1v2v3v4v5v6v7D(vi)V1030506393456093V2300203363153063V3502002050254050V4633320030183363V5936350300486393V6451525184801548*v7603040336315063中国邮路问题255693444443中国邮路问题定理1图G=（V，E）中，所有点的次之和是边数的两倍。定理2任一个图中，奇点的个数为偶数。

给定一个连通多重图G，若存在一条链，过每边一次，且仅一次，则称这条链为欧拉链。若存在一个简单圈，过每边一次，且仅一次，称这个圈为欧拉圈。若一个图能