运筹学教程课件六 图与网路分析资料.ppt

第六章图与网路分析图是最直观的模型1BACD图论GraphTheory哥尼斯堡七桥问题(KönigsbergBridgeProblem)LeonhardEuler(1707-1783)在1736年发表第一篇图论方面的论文,奠基了图论中的一些基本定理很多问题都可以用点和线来表示,一般点表示实体,(Vertex)物理实体、事物、概念一般用vi表示边(Edge)节点间的连线,表示有关系一般用eij表示图(Graph)节点和边的集合一般用G(V,E)表示点集V={v1,v2,…,vn}边集E={eij}work)边上具有表示连接强度的权值,如wij又称加权图(Weightedgraph),=eji,或(vi,vj)=(vj,vi)当边都有方向时,称为有向图,用G(V,A)表示在有向图中,有向边又称为弧,用aij表示,i,j的顺序是不能颠倒的,图中弧的方向用箭头标识图中既有边又有弧,,关联边,相邻,次图中可以只有点,而没有边;而有边必有点若节点vi,vj之间有一条边eij,则称vi,vj是eij的端点(endvertex),而eij是节点vi,vj的关联边(incidentedge)同一条边的两个端点称为相邻(adjacent)节点,具有共同端点的边称为相邻边一条边的两个端点相同,称为自环(self-loop);具有两个共同端点的两条边称为平行边(paralleledges)既没有自环也没有平行边的图称为简单图(simplegraph)在无向图中,与节点相关联边的数目,称为该节点的“次”(degree),记为d;次数为奇数的点称为奇点(odd),次数为偶数的点称为偶点(even);图中都是偶点的图称为偶图(evengraph),关联边,相邻,次有向图中,由节点指向外的弧的数目称为正次数,记为d+,指向该节点的弧的数目称为负次数,记为d–次数为0的点称为孤立点(isolatedvertex),次数为1的点称为悬挂点(pendantvertex)定理1:,圈,路径,回路,欧拉回路相邻节点的序列{v1,v2,…,vn}构成一条链(link),又称为行走(walk);首尾相连的链称为圈(loop),或闭行走在无向图中,节点不重复出现的链称为路径(path);在有向图中,节点不重复出现且链中所有弧的方向一致,则称为有向路径(directedpath)首尾相连的路径称为回路(circuit);,圈,路径,回路,连通图走过图中所有边且每条边仅走一次的闭行走称为欧拉回路定理2:偶图一定存在欧拉回路(一笔画定理),子图,成分设有两个图G1(V1,E1),G2(V2,E2),若V2V1,E2E1,则G2是G1的子图无向图中,若任意两点间至少存在一条路径,则称为连通图(connectedgraph),否则为非连通图(discon-nectedgraph);ponent)链,圈,路径(简称路),回路都是原图的子图平面图(planargraph),:倒置的树,根(root)在上,树叶(leaf)在下多级辐射制的电信网络、管理的指标体系、家谱、分类学、(tree),记为T树的性质:最少边的连通子图,树中必不存在回路任何树必存在次数为1的点具有n个节点的树T的边恰好为n1条,反之,任何有n个节点,n(spanningtree),若T是G的子图且包含图G的所有的节点;包含图G中部分指定节点的树称为steinertree每个节点有唯一标号的图称为标记图,标记图的生成树称为标记树(labeledtree)Caylay定理:n(2)个节点,有nn(depthfirstsearch):任选一点标记为0点开始搜索,选一条未标记的边走到下一点,该点标记为1,将走过的边标记;假设已标记到i点,总是从最新标记的点向下搜索,若从i点无法向下标记,即与i点相关联的边都已标记或相邻节点都已标记,则退回到i1点继续搜索,直到所有点都被标记广探法(breadthfirstsearch):是一种有层级结构的搜索,一般得到的是树形图10