6图与网络1讲解.ppt

图与网络分析 (Graph Theory and Network Analysis);B;一、 图与网络的基本知识 （一）、图与网络的基本概念 ; 一个图是由点集 和 中元素的无序对的一个集合 构成的二元组，记为G =(V，E)，其中 V 中的元素 叫做顶点，V 表示图 G 的点集合；E 中的元素 叫做边，E 表示图 G 的边集合。; 2、如果一个图是由点和边所构成的，则称其为无向图， 记作G = (V，E)，连接点的边记作[vi , vj]，或者[vj , vi]。; 4、一条边的两个端点是相同的,那么称为这条边是环。 5、若两个端点之间有两条以上的边，那么称为它们为多重边。;; 定理1 所有顶点次（度）数之和等于所有边数的2倍。 定理2 在任一图中，奇点的个数必为偶数。; 10、设 G1=（ V1 , E1 ），G2 =（ V2 ,E2 ）如果 V2 ?V1 , E2 ?E1 称 G2 是G1 的子图；如果 V2 = V1 , E2 ?E1 称 G2 是 G1 的部分图或支撑子图。 ; 在实际应用中，给定一个图G=（V，E）或有向图D=（V，A），在V中指定两个点，一个称为始点（或发点），记作v1 ，一个称为终点（或收点），记作vn ，其余的点称为中间点。对每一条弧 ，对应一个数 ，称为弧上的“权”。通常把这种赋权的图称为网络。 ;e3 ;偶图;（二）、 图的矩阵表示 对于网络（赋权图）G=（V，E），其中边 有权 ，构造矩阵 ，其中： 称矩阵A为网络G的权矩阵。;例;6.2 树及最小部分树问题 已知有六个城市，它们之间 要架设电话线，要求任意两个城市均可以互相通话，并且电话线的总长度最短。 ; 6.2.1树 的性质： （1）任何树中必存在次为1的点。 （2）n 个顶点的树必有n-1 条边。 （3）任何具有n个点、（n-1)条边的连通图是树。 （4）树 中任意两个顶点之间，恰有且仅有一条链（初等链）. （5）树连通，但去掉任一条边， 必变为不连通。 （6）树 无回路（圈），但不相邻的两个点之间加一条边，恰得到一个回路（圈）。; 2、 设图 是图G=(V , E )的部分图， 如果图 是一个树,那么称K 是G 的一个部分树（支撑树），或简称为图G 的树。图G中属于部分树的边称为树枝，不在部分树中的边称为弦。;6.2.2最小部分树问题 ;定??1. 图中任一个点i，若j是与i相邻点中距离最近的，则边[i , j]一定包含在该树的最小部分树内。;1、避圈法;2;2.用破圈法求部分树。 ;2.破圈法;; 最短路的一般提法为：设 为连通图，图中各边 有权 （ 表示 之间没有边）， 为图中任意两点，求一条路 ，使它为从 到 的所有路中总权最短。即： 最小。;教材步骤;例题3;L13=2;L16=6;L17=10;算法步骤 (其它教材步骤) 1.给始点vs以P标号 ，这表示从vs到 vs的最短距离为0，其余节点均给T标号， 。 2.设节点 vi 为刚得到P标号的点，考虑点vj，其中 ，且vj为T标号。对vj的T标号进行如下修改： 3.比较所有具有T标号的节点，把最小者改为P标号，即： 当存在两个以上最小者时，可同时改为P标号。若全部节点均为P标号，则停止，否则用vk代替vi，返回步骤（2）。;例一、 用Dijkstra算法求下图从v1到v6的最短路。 ;v1;2;;;2;2;2;2;2;2;求从V1 到 V8 的最短路线。 ;V1 ; 由此看到，此方法不仅求出了从V1 到 V8 的最短路长，同时也求出了从V1 到 任意一点 的最短路长。将从V1 到 任一点的最短路权标在图上，即可求出从V1 到 任一点的最短路线。本例中V1 到 V8 的最短路线是： v1 → v2 → v5→ v6 → v8 ;;6.3.2 矩阵算法;（二）、 逐次逼近法（