《《图与网络规划》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《图与网络规划》PPT课件.ppt（31页珍藏版）》请在三一办公上搜索。
1、第7章 图与网络规划,7.1 图的基本概念,图的基本概念,1.引言,如果用节点来代表事物，用连接两个节点之间的边来表示事物之间的联系，那么现实中的许多问题都可以用图论的语言来描述。,如，互联网，电话网，供应链网络，下水管道网络，天然气管道网络，朋友之间的友谊网络，亲戚关系网络等等,Power-law distribution,Scale-free Network,举例：群体中的朋友关系网络,内容框架,一、图的基本概念（讨论思路）,G=（V，E）,子图,矩阵表示,含元素的个数,点的次,边,特殊的图,点边关系,简单图,多重图,空 图,连通图,树,支撑树,G=(V,E),矩阵表示A 邻接矩阵B 关联
2、矩阵C 割集矩阵L 圈矩阵M 可达矩阵D 距离矩阵,边e=u,v,关联边,自回路,多重边 平行边,简单图,多重图,0 1 奇数 偶数,点边关系,点边关系,树(6个等价定义),支撑树,图的概念,1.图的定义：图G(V,E)是顶点和边的集合。表示顶点的集合（节点集）；表示边的集合（边集）。,图常用来描述系统的拓扑结构,节点代表具有相同属性的事物,边代表事物之间的各种关系或联系,图7-1,有关图的概念，以图7-1为例,顶点集：,边集：,7多重边或平行边：若两个端点之间有不止一条边，则称为多重边或平行边，包含这种边的图叫多重边图。无环也无多重边的图称为简单图。,8次（度）：节点作为边的端点的次数（或与
3、该节点邻接的边数）叫做该节点的次或度（Degree）。,9奇数节点（奇点）度为奇数的节点。偶数节点（偶点）度为偶数的节点。,10悬挂点与悬挂边：度为1 的点称为悬挂点，与悬挂点连接的边称为悬挂边。,11孤立点：度为0的点叫孤立点,12空图：若图G中所有点都是孤立点，则称图G为空图。,图的连通性,1链的概念：在图G中，由两两相邻的点 及其相关联的边 构成的点边序列（其中 与 关联）称为链。其中 称为链的起点，称为链的终点。,有向图,1.无向图：边是没有方向的，如沟通关系。,2.有向图：边是有方向的，如谁指挥谁的关系，表示为，V是顶点集，A是有向边的集合。,3.有向图中的链：在不考虑方向时，可以与
4、无向图一样定义链。,4.有向图中的路与初等路：若有向图 中，P是从u到v的链，且对P中每一条弧而言，在序列中位于该弧前面的点恰好是其起点，而位于该弧后面的点恰好是其终点，这个链P就称为是D中从u到v的一条路。顶点都不相同的路称为初等路。,5.有向图中的回路与初等回路：当有向图中路的起点和终点相同时，即 时，称作回路。除起点和终点外点均不相同的回路称为初等回路。,6.连通图与非连通图：若在有向图D中，任意两点间均存在一条链，则称D是连通图，否则称为非连通图。,7.强连通与非强连通：若在D的任意两点之间存在互通的路，则称D为强连通，否则称为非强连通图。,树,1.林：一个没有圈的图称为林。,2.树：
5、一个连通的无圈图称为树；一个林的每个连通子图都是一棵树。,3.部分树：若T是图 的部分图，且T是树，则称T为G的部分树。,4.余树：若T是图G的部分树，则从G中去掉T中所有的边，所得到的子图称为G中的T的余树，记为。,路(通路)初等路初等回路,例7-2 链、路、树,树无圈且连通,（3）权指与边或弧有关的数量指标。根据实 际背景可赋予不同含义，如距离、时间、费用、容量等。,1常用概念,（1）弧点与点之间有方向的连线。指从；,（5）网络指定了起点、终点和中间点的连通 的 赋权有向图。包括无向网络、有向网络、混合网络。,（4）赋权图图 连同边上的权总体。,（2）有向图由点集v和弧集A组成的图,2图论
6、在网络分析中的应用,最短路问题 最小树问题 最大流问题 最小费用最大流问题,7.2 最小树问题,在各式各样的图中，有一类图是极其简单然而却是很有用的，这就是树图。树图的定义是无圈的连通图。这类图与大自然中树的特征相似，因而得名树图。管理组织机构、学科分类和一些决策过程往往都可以用树图的形式表示。举一个现实生活中的例子，五个城市，要在它们之间架设电话线，要求任何两个城市都可以互相通话，并且电话线的根数最少。,用五个点代表五个城市，如果在某两个城市之间架设电话线，则在相应的两个点之间连一条边，这样一个电话线网就可以用一个图来表示了。为了使任何两个城市都可以通话，这样的图必须是连通的。其次，若图中有
7、圈的话，从圈上任意去掉一条边，余下的图仍是连通的，这样可以省去一条电话线。因而，满足要求的电话线网所对应的图必定是不含圈的连通图。图7-4代表了满足要求的一个电话线网。,如果G1是G2的部分图，又是树图，则称其是的支撑树。图（b）是（a）的一个支撑树。树图的各条边称为树枝（假定各边都有权重），一般图含有多个支撑树，设T是G的一棵支撑子树，称T中所有边的权之和为支撑树T的权，记为w(T)，如果支撑树T*权w(T*)是G所有支撑树的权中最小的，则T*称为G的最小支撑树(简称为最小树minimum spanning tree）。,求一个赋权连通图G的最小支撑树问题称为最小树问题。求最小树的方法有:,
8、破圈法：从网络图N任取一回路，去掉这个回路中权数最大的一条边，得一子网络图N1，在N1中再取任一回路，再去掉回路中权数最大的一条边，如此继续下去，一直到剩下的子图中不再含回路为止，该子图就是N的最小支撑树。,例7.1 如图7-6，v1，v2，v3，v4，v5，v6，v7代表村镇，它们之间连线表明各村镇间现有道路交通情况，连线旁数字代表道路的长度。现要求沿图中道路架设电线，使每个村庄都通上电，应如何架设使总的线路长度为最短。,分析：要使村镇都通上电，各点之间必须连通。又图中必不存在圈，否则从图中去掉一条边，图仍连通，原图就一定不是最短线路。故架设长度最短的线路就是从图7-6中寻找一颗最小支撑树。,总线路长度=1+4+9+3+17+23=57。,练习 用破圈法求下面网络的最小树,红线边及相连顶点构成最短树 最短树长等于 2+3+3+1+3=12,作业 P224P225：2，3；,
