管理运筹学 第七章图与网络分析.ppt

《管理运筹学 第七章图与网络分析.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第七章图与网络分析北京物资学院信息学院2017年5月北京物资学院运筹学课件本章主要内容§1图的基本概念§2最小树问题§3最短路问题§4最大流问题§1图的基本概念具体问题的图抽象问题的图蛋白质相互作用图基因相互作用关系图具体问题的图：城市之间的铁路交通图、地铁线路图、航空线路图等。抽象问题的图：球队进行比赛的关系图、一群人的认识关系图、社交网络图、基因调控关系图等图是反映对象之间关系的一种工具，如果我们把对象用点表示，关系用线表示，就构成了一个图。关系对称的关系：甲与乙有这种关系，则乙与甲也有这种关系，如两点之间的距离等。不对称的关系：

2、甲与乙有这种关系，但乙与甲未必有这种关系：如两个人的认识关系，比赛结果、交通路线中的单行线等。关系的表示对称的关系用边表示：e=[vi,vj]或e=[vj,vi]不对称的关系用带箭头的弧表示：a=(vi,vj)图的分类：无向图：G=(V,E)有向图：D=(V,A)一般用p和q分别表示一个图中的顶点数和边数一、无向图中的一些概念边的端点e1=[v1,v2]称v1,v2相邻，e是v1及v2的关联边环：两个端点相同的边；多重边：两个端点之间多于一条的边；简单图：无环、无多重边的图；多重图：无环、但允许有多重边的图点次：以v为端点的边的条数，

3、称为v的点次，记为dG(v)或d(v).（在计算点次时，环算2次）悬挂点：次为1的点；悬挂边：悬挂点的关联边；孤立点：次为0的点；奇点：次为奇数的点；偶点：次为偶数的点。e5v4v1v3v2e4e2e1e6e7e3v6v5e8定理1.图G=(V,E)中，所有点的次之和是边数的两倍.即定理2.任一个图中，奇点的个数是偶数。证明：设V1和V2分别是G中奇点和偶点的集合，由定理1，有链：图G=(V,E)中一个点边交替的序列如果满足则称之为一条联结vi1和vik的链。简单图中的链可以简记为链的起点、中间点、终点圈：起点和终点重合的链。简单链（

4、圈）：链（圈）中所含的边均不相同。初等链（圈）：链（圈）中所含的点均不相同。又称为路（回路）连通图：任何两个顶点之间至少有一条链的图。连通分支：不连通图的每一个连通部分图。子图、支撑子图：图G=(V,E),G´=(V´,E´),若V´V，E´E，则称G´是G的子图；V´=V，E´E，则称G´是G的支撑子图。割集：设G=(V,E)，SV,T=VS,(S,T)={e

5、e=vivj,viS,viT}则称(S,T)是G的一个割集。完全图：一个简单图中若任意两点之间均有边相连，则称之为完全图。偶图（二分图）：如果一个图的顶点能够分

6、成两个不相交的非空集合V1，V2，使同一集合中任意两点之间均不相邻，则称之为偶图（二分图）。二、有向图中的一些概念给定有向图D=(V,A).基础图：从D中去掉所有弧上的箭头后得到的无向图称为D的基础图，记为G(D).弧的始点、终点：a=(u,v),u为始点，v为终点。链：D中的一个点弧交替序列，如果在基础图中对应的是一条链，则称之为D的一条链。（弧可以是逆向的）路：如果一条链中的所有弧都是正向的，则称为一条路。回路：起点和终点相同的路称为回路。（简单路回路）、初等路（回路）可以类似定义。引例:自来水管道的铺设问题校门A点(水源);需要

7、使用自来水的场所共有7个:v1,v2,…,v7;问题:为了各个场所都用上自来水,怎样铺设管道才能使挖开的道路数目最少?Av1v2v3v4v7v6v52374355245627Av1v2v3v4v7v6v5Av1v2v3v4v7v6v5共挖开9条路共挖开6条路§2最小树问题树的定义及性质图的支撑树最小树问题树的定义及性质定义:无圈的连通图称为树.e1e2e4e3v4v1v5v3v2v6v7v8e5e6e7树的性质：1.设G是一个树，p(G)2,则G中至少有两个悬挂点。2.如下三个论断中的两个保证G是树：（1）连通;（2）无圈;（3）q

8、(G)=p(G)-1.3.G=(V,E)是一个树的充要条件是G中任意两个顶点间有且仅有一条链。4.从一个树中去掉任意一条边，则余下的图是不连通的。5.在树中不相邻的两个点间添上一条边，恰好得到一个圈。e1e2e4e3v4v1v5v3v2v6v7v8e5e6e7图的支撑树定义：设T=(V,E´）是图G=(V,E)的支撑子图，如果T=(V,E´)是一个树，则称T是一个支撑树。v1v5v4v3v2e1e2e3e6e7e8e5e4v1v5v4v3v2e1e3e6e8图GG的一个支撑树连通图的支撑树满足：（1）支撑性；（2）连通性；（3）无圈性

9、。2.求连通图的支撑树的方法：支撑性连通性无圈性破圈法支撑性无圈性连通性避圈法连通性无圈性支撑性反圈法破圈法找圈、破圈、直到无圈为止Av1v2v3v4v7v6v5避圈法（1）由连通图的所有顶点生成一个不含边的子图；（2）