图论与网络优化.ppt

第五章图论与网络优化;;§5-3树及其优化问题;如果用六个点v1…v6代表这六个城市，在任意两个城市之间架设电话线，即在相应的两个点之间连一条边。这样，六个城市的一个电话网就作成一个图。;;定义6：一个无圈的连通图叫做树。;下面介绍树的一些重要性质：

【定理5】p个顶点的树含p–1条边。

定理5-1设图G=（V，E）是一个树p(G)?2，那么图G中至少有两个悬挂点。

定理5-2图G=（V，E）是一个树的充要条件是G不含圈，并且有且仅有p–1条边。

定理5-3图G=（V，E）是一个树的充要条件是G是连通图，并且有且仅有p–1条边。

定理5-4图G是一个树的充分必要条件是任意两个顶点之间有且仅有一条链。;从以上定理，不难得出以下结论：;定义7设图K=(V,E1)是图G=(V,E)的一个支撑子图(点相同并保持图的连通性)，如果图K=(V,E1)是一个树,那么称K是G的一个支撑树。;【定理6】一个图G有支撑树的充要条件是G是连通图。

证明：充分性:设图G是连通的，若G不含圈，则按照定义，G是一个树，从而G是自身的一个支撑树。若G含圈，则任取G的一个圈，从该圈中任意去掉一条边，得到图G的一支撑子图G1。若G1不含圈，则G1是G的一个支撑树。

若G1仍然含圈，则任取G1的一个圈，再从圈中任意去掉一条边，得到图G的一支撑子图G2。依此类推，可以得到图G的一个支撑子图GK，且不含圈，从而GK是一个支撑树。;定理6充分性的证明，提供了一个寻找连通图支撑树的方法叫做“破圈法”。

即：就是从图中任取一个圈，去掉一条边。再对剩下的图重复以上步骤，直到不含圈时为止，这样就得到一个支撑树。;取一个圈(v1,v2,v3,v1)，在一个圈中去掉边e3。;1．最小支撑树;设Tk＝（V，Ek，Wk）是图G＝（V，E，W）的一棵支撑树，则边集Ek中所有边的权数之和称为树Tk的权数，记为：;a;【定理7】树T*是图G中最小树的充分必要条件是：

对T*外的每一条边eij，有下列不等式成立：;(1)避圈法：

从图中任意节点开始寻找与该节点关联的权数最小的边，使之与以选边不构成为圈，直到选够n-1条边为止。;v1;(2)破圈法：

①在图中寻找一个圈。若不存在圈，则已经得到最短树或网络不??在最短树；

②去掉该圈中权数最大的边；

③反复重复①②两步，直到最小树。;;;;v1;§5-4最短路问题;如下图所示的单行线交通网，每个弧旁边的数字表示这条单行线的长度。现在有一个人要从v1出发，经过这个交通网到达v6，要寻求总路程最短的线路。;从v1到v6的路线是很多的。比如:

从v1－v2－v4－v6;

或者从v1－v2－v3－v5－v6等等。

不同的路线，经过的总长度是不同的。

例如，按照第一个线路，总长度是3+6+3=12单位，

按照第二个路线，总长度是3+1+1+6=11单位。

因此，如何选择路线，使得总长度最短，便是本部分要讨论的问题。;一、有向图;显然，给定一个有向图D，若去除弧上的方向，则对应得到唯一的无向图G。此时的G称为D的基础图；

反之，一个无向图G，由于可用不同的方式来标上方向，故可伴生多个有向图。无向图中的许多概念与术语（如链与圈等）可沿用于有向图中，但仍有一些不同之处。将有向图与其基础图相对照，有下列对应关系：;在D=(V,A)中，点vi的邻点集N(vi)可分解为两部分，即：;给定一个赋权有向图D＝(V，A),对每一条弧aij＝w(vi，vj)，相应地有权w(aij)=wij，又有两点vs、vt∈V,设r是D中从vs到vt的一条路，路r的权是r中所有弧的权之和,记为w(r)．最短路问题就是求从vs到vt的路中一条权最小的路r*:;最短路问题按其不同的要求，可分成下列三种类型：

1、求两个定点之间的最短路；

2、求一个定点到其他各点的最短路；

3、求各点对之间的最短路。

不失一般性，总假定图中无环，以及多重弧只是由两条互为反向的弧组成的二重弧。;【例4】（渡河问题）

一人携带狼、羊、菜，须从一条小河的此岸渡往对岸。河边仅有一条小船，容量为2。当人不在场时，狼要吃羊、羊要吃菜。问：应怎样渡河，才能使大家安全到达对岸，且小船在河上的来回次数最少。

(船上必须要有人);【解】

记M代表人、W代表狼、S代表羊、V代表菜。

以河的此岸为考察基点，则开始状态为MWSV，结束状态为Φ。