图与网络规划课件.ppt

《图与网络规划课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、图是最直观的模型第六章图与网络规划第六章图与网络规划6.1图的基本概念6.1.1图论导引图论的研究最早可以追溯到著名的七桥问题。18世纪欧洲的哥尼斯堡有一条流经全城的普雷格尔河，河的两岸和河中两个小岛有七座桥彼此相连如图。当时人们讨论，从陆地A、B、C、D中的任一个地方开始，能否通过每一座桥一次且仅通过一次就能返回原地。BACD瑞士数学家Euler将这个问题抽象化，用含有四个点，七个边的图表示。探讨从图的任一点出发，是否能一笔画出右图，Euler发表了一篇关于图的论文，证明七桥问题不能一笔画出，结束了人们当时的争论，Euler被认为是图论的奠基人。1840年，莫别

2、斯提出了著名的四色问题。1859年提出了Hamilton回路问题。1936年，哥尼格发表了第一本图论专著。目前图论与计算机科学、系统论、控制论等密切结合，在工程技术、生物化学、系统工程、通讯科学等领域得到了广泛的应用。第六章图与网络规划图论的方法同样可以应用到经济管理、辅助决策等领域，图论已成为运筹学的一个重要组成部分，它是建立和处理离散型数学模型的一个重要工具。第六章图与网络规划第六章图与网络规划6.1图与网路的基本概念6.1.1图与网络图节点(Vertex)物理实体、事物、概念一般用vi表示边(Edge)节点间的连线，表示有关系一般用eij表示图(Graph)

3、节点和边的集合一般用G(V,E)表示点集V={v1,v2,…,vn}边集E={eij}网络图(Network)边上具有表示连接强度的权值，如wij又称加权图(Weightedgraph)第六章图与网络规划6.1.2无向图与有向图边都没有方向的图称为无向图，如图6.1在无向图中eij=eji，或(vi,vj)=(vj,vi)当边都有方向时，称为有向图，用G(V,A)表示在有向图中，有向边又称为弧，用aij表示，i,j的顺序是不能颠倒的，图中弧的方向用箭头标识图中既有边又有弧，称为混合图第六章图与网络规划6.1.3端点，关联边，相邻，次图中可以只有点，而没有边；而有边

4、必有点若节点vi,vj之间有一条边eij，则称vi,vj是eij的端点(endvertex)，而eij是节点vi,vj的关联边(incidentedge)同一条边的两个端点称为相邻(adjacent)节点，具有共同端点的边称为相邻边一条边的两个端点相同，称为自环(self-loop)；具有两个共同端点的两条边称为平行边(paralleledges)既没有自环也没有平行边的图称为简单图(simplegraph)在无向图中，与节点相关联边的数目，称为该节点的“次”(degree)，记为d(vi)；次数为奇数的点称为奇点(odd),次数为偶数的点称为偶点(even)；图

5、中都是偶点的图称为偶图(evengraph)第六章图与网络规划有向图中，由节点指向外的弧的数目称为正次数，记为d+，指向该节点的弧的数目称为负次数，记为d–次数为0的点称为孤立点(isolatedvertex)，次数为1的点称为悬挂点(pendantvertex)定理1：图中奇点的个数总是偶数6.1.4链，圈，路径，回路，欧拉回路相邻节点的序列{v1,v2,…,vn}构成一条链(link)，又称为行走(walk)；首尾相连的链称为圈(loop)，或闭行走在无向图中，节点不重复出现的链称为路径(path)；在有向图中，节点不重复出现且链中所有弧的方向一致，则称

6、为有向路径(directedpath)首尾相连的路径称为回路(circuit)；第六章图与网络规划走过图中所有边且每条边仅走一次的闭行走称为欧拉回路，若图G上含有一个欧拉回路，则这个图称为欧拉图，简称E图。定理2：偶图一定存在欧拉回路(一笔画定理)。6.1.4连通图，子图，成分设有两个图G1(V1,E1),G2(V2,E2),若V2V1,E2E1，则G2是G1的子图无向图中，若任意两点间至少存在一条路径，则称为连通图(connectedgraph)，否则为非连通图(disconnectedgraph)；非连通图中的每个连通子图称为成分(component)链，

7、圈，路径(简称路)，回路都是原图的子图平面图(planargraph)，若在平面上可以画出该图而没有任何边相交6.1.5中国邮路问题中国邮路问题：一个邮递员负责街道的邮件投递工作，每次从邮局出发走遍他负责的所有街道再回到邮局。那么他应该怎样安排投递线路使所走的总路程最短？该问题可以归结为：如果一个连通图G=，它的每条边e都有一个长度W(e)。对于这个加权连通图，要求至少通过一次的闭回路P，使总权最小。如图所示，假定每条街道长一公里，其中v1是邮局。第六章图与网络规划用奇偶点图上作业法求解中国邮路问题的基本步骤：1.找出图上所有的奇点，两两配对，每对奇点间

8、加上重复边