运筹学第7章 图与网络优化课件.ppt

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

1、第七章图与网络优化图是最直观的模型1BACD图论GraphTheory哥尼斯堡七桥问题(KönigsbergBridgeProblem)LeonhardEuler(1707-1783)在1736年发表第一篇图论方面的论文，奠基了图论中的一些基本定理很多问题都可以用点和线来表示，一般点表示实体，线表示实体间的关联27.1图与网络的基本概念1图与网络图节点(Vertex)物理实体、事物、概念一般用vi表示边(Edge)节点间的连线，表示有关联一般用eij表示图(Graph)节点和边的集合一般用G(V,E

2、)表示点集V={v1,v2,…,vn}边集E={eij}网络图(Network)边上具有表示连接强度的权值，如wij又称加权图(Weightedgraph)v1v5v4v3v2e12e34e13e24e22e'13e45图7.232无向图与有向图所有边都没有方向的图称为无向图，如图7.2在无向图中eij=eji，或(vi,vj)=(vj,vi)当所有边都有方向时，称为有向图，用D(V,A)表示在有向图中，有向边又称为弧，用aij表示，i,j的顺序是不能颠倒的，图中弧的方向用箭头标识图中既有边又有弧，

3、称为混合图43端点，关联边，相邻，次图中可以只有点，而没有边；而有边必有点若节点vi,vj之间有一条边eij，则称vi,vj是eij的端点(endvertex)，而eij是节点vi,vj的关联边(incidentedge)同一条边的两个端点称为相邻(adjacent)节点，具有共同端点的边称为相邻边一条边的两个端点相同，称为自环(self-loop)；具有两个共同端点的两条边称为平行（多重）边(paralleledges)既没有自环也没有平行边的图称为简单图(simplegraph)在无向图中，与节

4、点相关联边的数目，称为该节点的“次”(degree)，记为d；次数为奇数的点称为奇点(odd),次数为偶数的点称为偶点(even)；图中都是偶点的图称为偶点图(evengraph)53端点，关联边，相邻，次有向图中，由节点向外指的弧的数目称为正次数，记为d+，指向该节点的弧的数目称为负次数，记为d–次数为0的点称为孤立点(isolatedvertex)，次数为1的点称为悬挂点(pendantvertex)定理1：图中点的次数和是边数个2倍定理2：图中奇点的个数总是偶数个64链，圈，初等链，初等圈，简

5、单链（圈）相邻节点的序列{v1,v2,…,vn}构成一条链(link)p178；在无向图中，节点不重复出现的链称为初等链；首尾相连的链称为圈(loop)；首尾相连的初等链称为初等圈；边不重复出现的链（圈）称为简单链（圈）75完全图，偶图简单图中任意两点间都有边相连，则称为完全图。n个点的完全图有n（n-1）/2条边若图的顶点能分成两个互不相交的非空集合V1、V2，其在同一个集合中任意两点间都没有边相连，则称为偶图（二部图）。若偶图的顶点集合V1、V2之间的每一对不同顶点都有一条边相连，则称为完

6、全偶图。在完全偶图中，若顶点分别为n1、n2，有n1∙n2条边86子图，部分图；连通图，成分设有两个图G1(V1,E1),G2(V2,E2),若V2V1,E2E1，则G2是G1的子图。若V2=V1,E2E1，则G2是G1的部分图（支撑子图）。无向图中，若任意两点间至少存在一条链，则称为连通图(connectedgraph)，否则为非连通图(discon-nectedgraph)；非连通图中的每个连通子（分）图称为成分(component)链，圈，路径(简称路)，回路都是原图的子图支撑子图也是子

7、图，子图不一定是支撑子图。平面图(planargraph)，若在平面上可以画出该图而没有任何边相交97基础图，路，回路，欧拉回路在有向图D(V,A)中去掉箭头，称为D的基础图，G（D）在有向图中，链路圈回路走过图中所有边且每条边仅走一次的闭行走称为欧拉回路定理：偶点图一定存在欧拉回路(一笔画定理)107.2树图与最小支撑树一般研究无向图树图：倒置的树，根(root)在上，树叶(leaf)在下多级辐射制的电信网络、管理的指标体系、家谱、分类学、组织结构等都是典型的树图117.2.1树的定义及其性质任两

8、点之间有且只有一条链的图称为树(tree)。无圈的连通图称为树(tree)p180。记为T（V，E）树的性质：p180-181任何树必存在次数为1的点具有n个节点的树T的边恰好为n1条，反之，任何有n个节点，n1条边的连通图必是一棵树最少边的连通子图，树中必不存在回路127.2.2支撑树树T是连通图G的支撑树(spanningtree)，若T是G的支撑图且是树图树枝总长最小的支撑树称为最小支撑树。13支撑树连通图G最小支撑树？147.2.3最小支撑树有n个乡村，各