C类运筹学第5章图与网络ppt课件.ppt

《C类运筹学第5章图与网络ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、6.1图与网路的基本概念6.1.1图与网路节点(Vertex)物理实体、事物、概念一般用vi表示边(Edge)节点间的连线，表示有关系一般用eij表示图(Graph)节点和边的集合，一般用G(V,E)表示点集V={v1,v2,…,vn}边集E={eij}网络(Network)边上具有表示连接强度的权值，如wij又称加权图(Weightedgraph)无向图与有向图边都没有方向的图称为无向图，如图6.1在无向图中eij=eji，或(vi,vj)=(vj,vi)当边都有方向时，称为有向图，用G(V,A)表示在有向图中，有向边又称为弧，用ai

2、j表示，i,j的顺序是不能颠倒的，图中弧的方向用箭头标识图中既有边又有弧，称为混合图端点，关联边，相邻，次图中可以只有点，而没有边；而有边必有点若节点vi,vj之间有一条边eij，则称vi,vj是eij的端点(endvertex)，而eij是节点vi,vj的关联边(incidentedge)同一条边的两个端点称为相邻(adjacent)节点，具有共同端点的边称为相邻边一条边的两个端点相同，称为自环(self-loop)；具有两个共同端点的两条边称为平行边(paralleledges)既没有自环也没有平行边的图称为简单图(simplegr

3、aph)在无向图中，与节点相关联边的数目，称为该节点的“次”(degree)，记为d；次数为奇数的点称为奇点(odd),次数为偶数的点称为偶点(even)；图中都是偶点的图称为偶图(evengraph)有向图中，由节点指向外的弧的数目称为正次数，记为d+，指向该节点的弧的数目称为负次数，记为d–次数为0的点称为孤立点(isolatedvertex)，次数为1的点称为悬挂点(pendantvertex)定理1：图中奇点的个数总是偶数个链，圈，路径，回路，欧拉回路相邻节点的序列{v1,v2,…,vn}构成一条链(link)，又称为行走

4、(walk)；首尾相连的链称为圈(loop)，或闭行走在无向图中，节点不重复出现的链称为路径(path)；在有向图中，节点不重复出现且链中所有弧的方向一致，则称为有向路径(directedpath)首尾相连的路径称为回路(circuit)；走过图中所有边且每条边仅走一次的闭行走称为欧拉回路定理2：偶图一定存在欧拉回路(一笔画定理)设有两个图G1(V1,E1),G2(V2,E2),若V2V1,E2E1，则G2是G1的子图无向图中，若任意两点间至少存在一条路径，则称为连通图(connectedgraph)，否则为非连通图(disconn

5、ectedgraph)；非连通图中的每个连通子图称为成分(component)链，圈，路径(简称路)，回路都是原图的子图6.2树图与最小生成树一般研究无向图树图：倒置的树，根(root)在上，树叶(leaf)在下多级辐射制的电信网络、管理的指标体系、家谱、分类学、组织结构等都是典型的树图6.2.1树的定义及其性质任两点之间有且只有一条路径的图称为树(tree)，记为T树的性质：最少边的连通子图，树中必不存在回路任何树必存在次数为1的点具有n个节点的树T的边恰好为n1条，反之，任何有n个节点，n1条边的连通图必是一棵树6.2.2图的生

6、成树树T是连通图G的生成树(spanningtree)，若T是G的子图且包含图G的所有的节点；包含图G中部分指定节点的树称为steinertree每个节点有唯一标号的图称为标记图，标记图的生成树称为标记树(labeledtree)Caylay定理：n(2)个节点，有nn2个不同的标记树6.2.2图的生成树如何找到一棵生成树深探法(depthfirstsearch)：任选一点标记为0点开始搜索，选一条未标记的边走到下一点，该点标记为1，将走过的边标记；假设已标记到i点，总是从最新标记的点向下搜索，若从i点无法向下标记，即与i点相关联的

7、边都已标记或相邻节点都已标记，则退回到i1点继续搜索，直到所有点都被标记广探法(breadthfirstsearch)：是一种有层级结构的搜索，一般得到的是树形图6.2.3最小生成树有n个乡村，各村间道路的长度是已知的，如何敷设光缆线路使n个乡村连通且总长度最短显然，这要求在已知边长度的网路图中找最小生成树最小生成树的算法：Kruskal算法：将图中所有边按权值从小到大排列，依次选所剩最小的边加入边集T，只要不和前面加入的边构成回路，直到T中有n1条边，则T是最小生成树Kruskal算法基于下述定理定理3指定图中任一点vi，如果vj

8、是距vi最近的相邻节点，则关联边eij必在某个最小生成树中。推论：将网路中的节点划分为两个不相交的集合V1和V2，V2=VV1，则V1和V2间权值最小的边必定在某个最小生成树中。6.2.3最小生成树最小生