《图与网络规划》PPT课件

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

1、第7章图与网络规划7.1图的基本概念图的基本概念1.引言如果用节点来代表事物，用连接两个节点之间的边来表示事物之间的联系，那么现实中的许多问题都可以用图论的语言来描述。如，互联网，电话网，供应链网络，下水管道网络，天然气管道网络，朋友之间的友谊网络，亲戚关系网络等等Power-lawdistributionScale-freeNetwork举例：群体中的朋友关系网络内容框架一、图的基本概念（讨论思路）G=（V，E）子图矩阵表示含元素的个数点的次边特殊的图点边关系简单图多重图空图连通图树支撑树空图不含边G=(V,E)矩阵表示A邻接矩阵B关联

2、矩阵C割集矩阵L圈矩阵M可达矩阵D距离矩阵边e=[u,v]关联边端点重合环自回路多重边平行边多于1条边简单图不含多重图含点的次01奇数偶数子图真子图支撑子图导出子图孤立点悬挂点奇点偶点悬挂边顶点数p边数q点边关系各种链的概念点边关系真子图支撑子图导出子图各种链的概念通路树(6个等价定义)连通图支撑树有向、无向图的概念1.图的定义：图G(V,E)是顶点和边的集合。表示顶点的集合（节点集）；表示边的集合（边集）。图常用来描述系统的拓扑结构节点代表具有相同属性的事物边代表事物之间的各种关系或联系图7-1有关图的概念，以图7-1为例顶点集：边集：

3、4．端点与关联边：若，则称节点是边的端点；而边称为与节点关联的边。5．相邻点与相邻边：若与同一条边相关联，则称为相邻点；若两条边有同一个端点，则称为相邻边。2．图G的顶点数：集合V中元素的个数。3．图G的边数:集合E中元素的个数。6．环：若一条边的两个端点（起点和终点）是同一个顶点，称该边为环（loop）。7．多重边或平行边：若两个端点之间有不止一条边，则称为多重边或平行边，包含这种边的图叫多重边图。无环也无多重边的图称为简单图。8．次（度）：节点作为边的端点的次数（或与该节点邻接的边数）叫做该节点的次或度（Degree）。9．奇数节点（

4、奇点）—度为奇数的节点。偶数节点（偶点）—度为偶数的节点。10．悬挂点与悬挂边：度为1的点称为悬挂点，与悬挂点连接的边称为悬挂边。11．孤立点：度为0的点叫孤立点12．空图：若图G中所有点都是孤立点，则称图G为空图。图的连通性1．链的概念：在图G中，由两两相邻的点及其相关联的边构成的点边序列（其中与关联）称为链。其中称为链的起点，称为链的终点。2．开链与闭链：若，则称该链为开链，反之称为闭链或回路。3．若链中所含的边均不相同，则称为简单链；若点均不相同，则称为初等链或通路。除起点和终点外点均不同的闭链，称为初等回路或圈。4．若一个图的任意

5、两点之间均至少有一条通路（初等链）连接起来，则称这个图G是一个连通图，否则称作非连通图。如果一个问题所对应的图是一个非连通图，则该问题一定可以分解成互不相关的子问题来加以研究，即可以把不连通的图分解成连通的子图来考虑。有向图1.无向图：边是没有方向的，如沟通关系。2.有向图：边是有方向的，，如谁指挥谁的关系，表示为，V是顶点集，A是有向边的集合。3.有向图中的链：在不考虑方向时，可以与无向图一样定义链。4.有向图中的路与初等路：若有向图中，P是从u到v的链，且对P中每一条弧而言，在序列中位于该弧前面的点恰好是其起点，而位于该弧后面的点恰好

6、是其终点，这个链P就称为是D中从u到v的一条路。顶点都不相同的路称为初等路。5.有向图中的回路与初等回路：当有向图中路的起点和终点相同时，即时，称作回路。除起点和终点外点均不相同的回路称为初等回路。6.连通图与非连通图：若在有向图D中，任意两点间均存在一条链，则称D是连通图，否则称为非连通图。7.强连通与非强连通：若在D的任意两点之间存在互通的路，则称D为强连通，否则称为非强连通图。树1.林：一个没有圈的图称为林。2.树：一个连通的无圈图称为树；一个林的每个连通子图都是一棵树。3.部分树：若T是图的部分图，且T是树，则称T为G的部分树。4

7、.余树：若T是图G的部分树，则从G中去掉T中所有的边，所得到的子图称为G中的T的余树，记为。路(通路)初等路初等回路例7-2链、路、树简单链初等链初等圈树无圈且连通（3）权——指与边或弧有关的数量指标。根据实际背景可赋予不同含义，如距离、时间、费用、容量等。1．常用概念（1）弧——点与点之间有方向的连线。指从；（5）网络——指定了起点、终点和中间点的连通的赋权有向图。包括无向网络、有向网络、混合网络。（4）赋权图—图连同边上的权总体。（2）有向图——由点集v和弧集A组成的图2．图论在网络分析中的应用最短路问题最小树问题最大流问题最小费用最

8、大流问题……7.2最小树问题在各式各样的图中，有一类图是极其简单然而却是很有用的，这就是树图。树图的定义是无圈的连通图。这类图与大自然中树的特征相似，因而得名树图。管理组织机构、学科分类和一些