第10章第12节.ppt

《第10章第12节.ppt》由会员分享，可在线阅读，更多相关《第10章第12节.ppt（71页珍藏版）》请在第壹文秘上搜索。

1、1第1节图的基本概念第2节 树运筹学（第三版）运筹学教材编写 组第10章 图与网络优化清华大学出版社2 图论是应用非常广泛的运筹学分支，它已经广泛地应用于物理学控制论，信息论，工程技术，交通运输，经济管理，电子计算机等各项领域。对于科学研究，市场和社会生活中的许多问题，可以同图论的理论和方法来加以解决。例如，各种通信线路的架设，输油管道的铺设，铁路或者公路交通网络的合理布局等问题，都可以应用图论的方法，简便、快捷地加以解决。3 1736年瑞士科学家欧拉发表了关于图论方面的第一篇科学论文，解决了著名的哥尼斯堡七座桥问题。德国的哥尼斯堡城有一条普雷格尔河，河中有两个岛屿，河的两岸和岛屿之间有七座桥

2、相互连接，4BDACABCD哥尼斯堡七空桥哥尼斯堡七空桥一笔画问题一笔画问题欧拉（1736）5第1节图的基本概念 例1是我国北京、上海、重庆等十四个城市之间的铁路交通图，这里用点表示城市，用点与点之间的线表示城市之间的铁路线。诸如此类还有城市中的市政管道图，民用航空线图等等。太原重庆武汉南京徐州连云港上海郑州石家庄塘沽青岛济南天津北京6 例例 2 表示五个球队比赛请况。用五个点表示五个球队比赛请况。用五个点v1,v2,v3,v4,v5分别表示五个球队，点与分别表示五个球队，点与点之间的连线表示对应的两个球队已经点之间的连线表示对应的两个球队已经比赛过。比赛过。甲甲 v1乙乙 v2 v3 丙丙

3、v4 丁丁戊戊 v57 例例 3 用八个点用八个点v1,v2,v3,v4,v5,v6,v7,v8 表示八种表示八种化学药品，其间有连线的表示该两种化学药品化学药品，其间有连线的表示该两种化学药品不能存放在一个仓库里，问至少要设几个仓库不能存放在一个仓库里，问至少要设几个仓库来存放这些药品？由图可见，至少要设四个仓来存放这些药品？由图可见，至少要设四个仓库。库。v1v8v2v3v4v5v6v78图是反映对象之间关系的一种工具，其中点表示对象，点间连图是反映对象之间关系的一种工具，其中点表示对象，点间连线表示对象之间的关系。线表示对象之间的关系。一般而言，图中点的位置，点间连线的长短曲直对于反映对

4、象一般而言，图中点的位置，点间连线的长短曲直对于反映对象及其之间的关系并不重要。及其之间的关系并不重要。v1v2 v3 v4 v5v1v2 v3 v4 v5 在前面两例中，对象之间的关系是在前面两例中，对象之间的关系是“对称的对称的”，这种对称的关，这种对称的关系可用两点之间的连线表示。但有些关系不是对称的，不可用系可用两点之间的连线表示。但有些关系不是对称的，不可用两点之间的连线表示，却可以用两点之间的一条箭线来表示。两点之间的连线表示，却可以用两点之间的一条箭线来表示。如两个球队进行过比赛，这种关系是对称的；但谁胜谁负就不如两个球队进行过比赛，这种关系是对称的；但谁胜谁负就不是对称的。若甲

5、胜乙负，那么可以用从甲到乙划一条箭线来表是对称的。若甲胜乙负，那么可以用从甲到乙划一条箭线来表示。示。甲甲乙乙。9甲甲 v1乙乙 v2 v3 丙丙 v4 丁丁戊戊 v5 图论中的图论中的图图，是指，是指点点以及点与点之间的以及点与点之间的连线连线所组成的集合。所组成的集合。如果如果联线没有方向（不是箭线）就叫做联线没有方向（不是箭线）就叫做边边，如果，如果联线有方向联线有方向（即箭线）就叫做（即箭线）就叫做弧。弧。如果一个图如果一个图 G(Graph)是由点与边组成，就叫是由点与边组成，就叫无向图无向图（也简称（也简称为图）。记为为图）。记为 G=（V，E），其中），其中V表示点的集合，表示点

6、的集合，E 表示边表示边(Edge)的集合。的集合。如果一个图如果一个图 D(Diagram)是点与弧是点与弧的集合就叫的集合就叫有向图有向图，记为：记为：D=（V，A），），其中其中V表示点的集合，表示点的集合，A表示弧表示弧（Arc)的集合。的集合。连接连接 vi与与vj 的边记为的边记为 vi ，vj 或或 vj ,vi。由由 vi指向指向vj 的弧记的弧记为为（vi ，vj）。10V1V2V3V4253 页页 图图 107例如右图（无向图，见例如右图（无向图，见 253页）可表为：页）可表为：e1e7e6e5e4e3e2G=V,E,其中：其中：V=，E=e1，e2，e3，e4，e5，e

7、6，e7 V1V2 V3V 4V1V2V3V4a1a6a5a4a3a2其中其中又又：e1=V1,V2,e2=V1,V2e3=V3,V2,e4=V4,V3,e5=V1,V4,e6=V1,V3,e7=V4,V4又例如右图（为一有向图）可表为：又例如右图（为一有向图）可表为：D=V,A,其中：其中：V=，A=a1，a2，a3，a4，a5，a6 V1V2 V3V 4其中其中又又：a1=(V1,V2),a2=(V1,V2),a3=(V2,V3),a4=(V4,V3),a5=(V1,V4),a6=(V1,V3),图的实例图的实例11 图图G(或图或图D)的点数记为的点数记为p（G）(或或P（D）)，边（或

8、弧）的条数记为边（或弧）的条数记为q(G)(或或q(D),在不会引起误会时，也分别简记为在不会引起误会时，也分别简记为p,q.下面介绍一些基本名词和记号，先考虑无向图下面介绍一些基本名词和记号，先考虑无向图 G=（V，E）：）：若若 e=u,v,则称则称 u,v 是是 e 的的端点端点,也称也称 u,v 是是相邻相邻的。称的。称 e 是点是点 u,v 的的关关联边联边。若边的两个端点相同，则该边成为。若边的两个端点相同，则该边成为环环（如图（如图107中的中的 e7）；如两）；如两点之间有多条边，则称这些边为点之间有多条边，则称这些边为多重边多重边。（如图（如图107中的中的e1，e2）。）。

9、一个无环、无多重边的图称一个无环、无多重边的图称简单图简单图，无环但，无环但有多重边的图称有多重边的图称多重图多重图。以。以 v 为端点的边的为端点的边的条数称为点条数称为点 v 的的次数，次数，记为记为 d(v)，如在右，如在右图中：图中：d(v1)=4,d(v2)=3,d(v 4)=4(环环 e7在计算在计算d(v 4)时算作两次时算作两次)。称次数为一的点为称次数为一的点为悬挂点悬挂点，悬挂点，悬挂点的关联边为的关联边为悬挂边悬挂边，次数为，次数为 0 的点称为的点称为孤立点孤立点（点击）。次数为奇数的点称为（点击）。次数为奇数的点称为奇点奇点，次数为偶数的点称为，次数为偶数的点称为偶点

10、偶点.V1V2V3V4253 页页 图图 107e1e7e6e5e4e3e2V5V6次与简次与简单图单图12端点的度 d(v)：点 v 作为边端点的个数；奇点：d(v)=奇数；偶点：d(v)=偶数；悬挂点：d(v)=1；悬挂边：与悬挂点连接的边；孤立点：d(v)=0；空图：E=，无边图13 定理1 所有顶点次数之和等于所有边数的2倍。定理2 在任一图中，奇点的个数必为偶数。基本定理基本定理14链：由两两相邻的点及其相关联的边构成的点边序列;如:v0,e1,v1,e2,v2，e3,v3,vn-1,en,vn;v0，vn分别为链的起点和终点；初等链：链中所含的点均不相同 简单链：链中所含的边均不相

11、同；链15圈 第一个点和最后一个点相同的链叫第一个点和最后一个点相同的链叫圈圈。中间点皆不相同的圈叫中间点皆不相同的圈叫初等圈初等圈。所有边。所有边皆不相同的圈叫皆不相同的圈叫简单圈简单圈。16连通图给定图给定图G，若其中任何两点之间至少有，若其中任何两点之间至少有一条链，则称一条链，则称G为为连通图连通图，否则称为，否则称为不不连通图连通图；若若G 不是连通图，则可将它分不是连通图，则可将它分为若干个连通的为若干个连通的分图分图。17v8v9e10v2v1v4e4e1e2e3v3v6v5v7e5e6e9e7e8在图10-9中，链（v1,v2,v3,v4,v5,v3,v6,v7)是简单链，非初

12、等链。链（v1,v2,v3,v6,v7)是初等链。（v1,v2,v3,v4,v1)是初等圈。（v4,v1,v2,v3,v5,v7,v6,v3,v4)是简单圈，非初等圈（中间有相同点）。18V1V3V4V5V2图图 G图图 G V V3图图 G的一个的一个支撑子图支撑子图V1V4V5V2V1V3V4V5V2给定一个图给定一个图G=（V，E）如果图）如果图G=（V，E），满足条），满足条件：件：V=V，E E，则称，则称 G是是 G 的一个的一个支撑子图支撑子图。即去掉。即去掉G的一些的一些边（边的端点并不随边一起去掉）后所得的图称边（边的端点并不随边一起去掉）后所得的图称G的支撑的支撑子图。子图

13、。设设 vV(G),用用 Vv表示从表示从 G中去掉点中去掉点v及其关联边后所及其关联边后所的到的图。的到的图。19V1V3V4V5V2图图 GV1V3V4V5V2V1V3V4V5V2V1V3V4V5V2图图 G的支撑子图的支撑子图V1V3V4V5V2基本概念420以下讨论有向图。设有一个有向图以下讨论有向图。设有一个有向图D=（V，A），去掉），去掉D中所有弧上的箭中所有弧上的箭头，得一无向图，叫头，得一无向图，叫D 的的基础图基础图，记为，记为G（D）。）。给定弧给定弧a=(u,v),称称 u 为为 a 的的始点始点，称，称 v 为为 a 的的终点终点。有向图有向图D中的一个点弧交错序列，

14、如果在其基础图中的一个点弧交错序列，如果在其基础图G（D）中对应一条链，则称中对应一条链，则称D的这一点弧交错序列为图的这一点弧交错序列为图D的一条的一条链链。若若D的链上每条弧的左右两点分别是该弧的始点和终点，就的链上每条弧的左右两点分别是该弧的始点和终点，就称该链为一条称该链为一条路路。若。若路路的第一个点与最后一个点相同，就称的第一个点与最后一个点相同，就称之为之为回路回路。初等路初等路是中间点皆不相同的路。是中间点皆不相同的路。V1V2V3V4V5V6a1a2a3a4a5a6a7a8a9a10a11V7 如点弧交错序列如点弧交错序列：V1,a2,V3,a8,V5,a10,V6,a11,

15、V7 是链不是路。是链不是路。而而点弧交错序列：点弧交错序列：V1,a1,V2,a5,V4,a7,V6,a11,V7 是链也是路。是链也是路。基本概基本概念念5212.1树及其性质 在各种各样的图中，有一类图是十分简单又非常具有应用价值的图，这就是树。22已知有五个城市，它们之间要架设电话线，要求任意两个城市均可以互相通话（允许通过其它城市），并且电话线的根数最少。不含圈的连通图v2v3v5v4v123 定义1 一个无圈的连通图叫做树。下面介绍树的一些重要性质：定理3 设图G=（V，E）是一个树P(G)2，那么图G中至少有两个悬挂点。定理4 图G=（V，E）是一个树的充要条件是G不含圈，并且有

16、且仅有P-1条边。定理5 图G=（V，E）是一个树的充要条件是G是连通图，并且有且仅有P-1条边。定理8.6 图G是一个树的充分必要条件是任意两个顶点之间有且仅有一条链。24 从以上定理，不难得出以下结论：（1）从一个树中任意去掉一条边，那么剩下的图不是连通图，亦即，在点集合相同的图中，树是含边数最少的连通图。（2）在树中不相邻的两个点之间加上一条边，那么恰好得到一个圈。252.2图的支撑树 定义2 设图T=(V,E)是图G=(V,E)的支撑子图,如果图T=(V,E)是一个树,那么称T是G的一个支撑树。v6v5v2v3v4v1图1014av6v2v4v1bv3v526 若若T=（V，E）是图）是图 G=（V，E）的支撑）的支撑树，则树，则T的边数：的边数：q(T)=p(T)-1=p(G)-1，G 中不属于中不属于 T 的边数是的边数是 q(G)-（p(G)-1）=q(G)-p(G)+1。27定理定理 7 图图G有支撑树的充分必要条有支撑树的充分必要条件是件是 G 连通连通。必要性显然。必要性显然。充分性充分性 设设G连通。若连通。若G是树，则是树，则G是它自是它自己的支撑树。若己的支撑