算法设计与分析.doc

《算法设计与分析.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、《算法设计与分析》第六小组讲稿小组成员：任务分工：1、基本概念——2、生成树算法——3、最小（大）耗费生成树算法——4、最大分枝算法——）13一、基本概念——毛科技1.一个无向图G是一个有序的二元组（V，E）表示：V≠Φ称为顶点集，其元素称为顶点或结点。E称为边集，它是无序积V&V的多重子集，其元素称为无向边，简称边。一个有向图是一个有序的二元组（V，E），记作D，其中：V同无向图E为边集，它是笛卡儿积V*V的多重子集，其元素称为有向边，简称边。（多重集合：元素可以重复出现的集合）V:{①,②,③,④}E:{a,b,c,d,e}④②例如：cde③①aba2.网络：图中的每

2、条边附有一个或几个数字。ab1212cbc3网络非网络3.自环：有向边（弧）的头部和尾部为同一个顶点。ba自环非自环4.某个顶点为某一条弧的一个端点（头或尾），则此顶点与该条弧相关联。5.如果两条弧都和同一个顶点关联，则该两条弧称为相互关联。如有一条弧将两个顶点连接起来，则这两个顶点称为邻接。abe1e2e3在上图中e1和a，e1和e2为相互关联，a和b为邻接6.链：给定任一顶点序列X1，X2，X3，…，Xn,Xn+1,若弧e1的两个端点是Xi和Xi+1，i=1，n。则称弧的序列e1，e2，…en为链。顶点X1，Xn+1分别称为链的始点和终点。链中弧的数目称为链的长度。1

3、3链：X4X3X1X2e1e2e3e4……在链中的顶点不可以重复，但是对弧的序列没有要求。如果一个链的始点和终点为同一点，这样的链称为圈。在链和圈中如果不存在和两条以上的弧相关联的顶点时，分别称为简单链和简单圈。X3X2X1简单圈1.路：若ei=（Xi，Xi+1），i=1，n，这样的链称为路。如果一条链的始点和终点为同一点，这样的链称为圈。如果一条路的始点和终点为同一点，这样的路称为回路。圈或回路的长度定义为这条相应的链的长度。路：X3X2X2X1e1e2e3e4在路中的弧的序列不可以重复。但是对顶点没有要求。简单回路：除了第一个顶点和最后一个顶点之外，其余顶点不重复出现

4、的路。简单路：在路中如果不存在和两条以上的弧相关联的顶点。2.连通图：在一个图内，如果每一对顶点都有一条链将它们连接起来。一个图可以看成是有连通图的一个集合组成，其中每一个连通图称为原图的一个分图。edcba非连通图edcba131.给定图G=（V，E），如果V’∈V，E’∈E，则图G’=（V’，E’）称为G的子图。从图中删去弧的一个子集时，若能增加图中分图的数目，则称删去的弧的集合为图的截。fdae1bec图中只有e1是截2.满足下列条件的弧的集合称为树：（1）这些弧构成一个连通图。（2）这些弧不构成圈。树的定义：是N（N≥0）个结点的有限集。在任意一棵非空树中：1，有

5、且仅有一个特定的称为根的结点。2，当N＞1时，其余结点可分为M（M>0）个互不相交的有限集T1，T2，T3……，Tm，其中每一个集合本身又是一棵树。aacbcbdeed树圈3.森林：不包含圈的任一弧的集合。其包含一棵或多棵树。给定图G=（V，E），G’=(V，E’)是G的连通子图，E’∈E，E’有且仅有N-1条边（G有N个顶点），则称G’是G的一棵生成树。每一个连通图都有一棵生成树；有两个或两个以上分图的图不存在生成树；一个连通图的生成树不一定是唯一的。设T是无向图G的子图并且为树，则称T为G的树。若T是G的树且为生成子图，则称T是G的生成树。131.最小耗费生成树：设G

6、是一个有顶点的无向图，图中的每一条边ei∈E都有一个权Ci，Ci称为ei的耗费。生成树的各边的耗费之和称为生成树的耗费。在图G的一切生成树中，各边耗费之和最小的一棵生成树称为G的最小耗费生成树。图G的最小耗费生成树不一定是唯一的。2.用矩阵来表示图：设G是N个顶点M条弧的任一无自环的图，H为一矩阵，它有N行（每个顶点对应于一行）和M列（每条弧对应于一列）。Hij表示第i行和第j列的元素，Hij的定义如下：+1如果第i行的顶点是第j列的弧的头部Hij=-1如果第i行的顶点是第j列的弧的尾部0不属于以上两种情况H的每一列只含+1各一个，其余元素均为0。e1e2e3e4e5a-

7、1-1+100H=b+1+10-1-1c00-1+1+1d000+1-1耗费矩阵：12345∞12751∞44324∞12741∞35323∞12345对于无向图，可以用邻接矩阵来表示。矩阵中只有0，1两个元素H=1顶点I与顶点j间有边相邻0否则13abcdea01100b10111H=c11010d01101e01010edbca13二、生成树算法——庞若蔚刚才毛科技同学介绍了图的一些相关基本概念，下面我们来探讨一下图的生成树。前面讲到，对于给定的图G=(V,E),G’=(V,E’)是G的连通子图，E’⊆E,E’有且仅有n-