《图与网络规划》PPT课件.ppt

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