图论基础与计划编制方法课件.ppt

1、第第11章章 图论基础与计划编制方法图论基础与计划编制方法111 111 图论基础图论基础112 112 工程项目计划的横道图表示法工程项目计划的横道图表示法113 113 网络计划技术的概念及其表示网络计划技术的概念及其表示114 114 网络计划的优化网络计划的优化首页首页上页上页返回返回下页下页111 图论基础首页首页上页上页返回返回下页下页基础知识基础知识1、图的基本概念、图的基本概念 引例引例11公路网公路网 有有6个城镇个城镇A、B、C、D、E、F，它们之，它们之间有公路直通的情况是：（间有公路直通的情况是：（A，B）、（A，C）、（A，E）、（A，F）、（）、（B，C）、（）、（

2、B，D）、（）、（D，F）、（）、（E，F）.试将它们的关系用图表示出来试将它们的关系用图表示出来.分析分析 我们把我们把6个城镇个城镇A、B、C、D、E、F分别用点表示分别用点表示.若若两城镇之间有公路直通，则用线两城镇之间有公路直通，则用线相连结，否则不连结，可得到右相连结，否则不连结，可得到右图，即为所作的关系图图，即为所作的关系图.ABCDEF首页首页上页上页返回返回下页下页把把A、B、C、D、E、F对应的点看成一个集合，对应的点看成一个集合，“线线”是这个集合中是这个集合中“点点”之间的关系，那么，之间的关系，那么，图论正是研图论正是研究像这样的有限集合及其关系的一门数学科学究像这样

3、的有限集合及其关系的一门数学科学.在这里，在这里，“线线”是不论其曲直形状的，通常称为边，是不论其曲直形状的，通常称为边，“点点”是是不论其上下位置的，通常称为不论其上下位置的，通常称为结点结点.由这样的结点和边由这样的结点和边构成的整体，就叫做构成的整体，就叫做图图.A、B两点有线相连，称两点有线相连，称A和和B是是邻接的点邻接的点；而连线称为与；而连线称为与A、B两点两点相关联的边相关联的边，记，记作作(A,B).结点结点邻接点邻接点相关联的边相关联的边ABCDEF首页首页上页上页返回返回下页下页 若图中一边的两个相关联的结点相同，则称为若图中一边的两个相关联的结点相同，则称为环环.若图中

4、两边具有相同的一对结点，则称为若图中两边具有相同的一对结点，则称为平行边平行边.没有环和平行边的图称为没有环和平行边的图称为简单图简单图.ABCDEF环环平行边平行边讨论讨论：以上两图中哪一个为简单图？：以上两图中哪一个为简单图？ABCDEF首页首页上页上页返回返回下页下页 这里的图与平面几何里的图形是不相同的这里的图与平面几何里的图形是不相同的.这里的图这里的图只考虑结点、边以及边与结点的对应关系，因此当两个只考虑结点、边以及边与结点的对应关系，因此当两个图的形状看似不同，但若它们的结点集、边集及边与结图的形状看似不同，但若它们的结点集、边集及边与结点的关联关系都相同时，则可将它们看作同一个

5、图点的关联关系都相同时，则可将它们看作同一个图.这时，这时，称这两个图是称这两个图是同构同构的的.同构同构点与点点与点1-1对应，线与线对应，线与线1-1对应对应(1)ABCDABCD(2)首页首页上页上页返回返回下页下页与与A点关联的所有边的条数称为点关联的所有边的条数称为A点的点的次数次数，记作，记作degA.ABCDEF孤立点孤立点次数为零的结点称为次数为零的结点称为孤立点孤立点.ABCDEFdegA=4，degB=degF=3，degC=degD=degE=2.例：例：求图中各点的次数求图中各点的次数问：问：下图中下图中F点的次数是多少？点的次数是多少？首页首页上页上页返回返回下页下页

6、定理定理1 任一图中点的次数之和等于边数的两倍任一图中点的次数之和等于边数的两倍.定理定理2 任一图中次数为奇数的点的个数必为偶数任一图中次数为奇数的点的个数必为偶数.讨论讨论：图中点的次数与边数有何联系？：图中点的次数与边数有何联系？ABCDEF首页首页上页上页返回返回下页下页 引例引例2 程序调用程序调用 有有4个程序个程序 ，它们的调，它们的调用关系是：用关系是：能调用能调用 ；能调用能调用 ，能调用能调用 .试将它试将它们的关系用图表示出来们的关系用图表示出来.1234,p ppp1p2p2p3p2p4p 分析分析 将将4个程序分别用点来表示个程序分别用点来表示.由于调用是有顺由于调用

7、是有顺序的，因此它们之间的调用关系用一条有方向的线相序的，因此它们之间的调用关系用一条有方向的线相连结，得到下图，即为所作的关系图连结，得到下图，即为所作的关系图.p1p2p3p4 图中的边带有方向，通常称为图中的边带有方向，通常称为有向边有向边.若一个图中所有边均是有若一个图中所有边均是有向边，则称这图为向边，则称这图为有向图有向图.若一个若一个图中所有边均是无向边，则称这图图中所有边均是无向边，则称这图为为无向图无向图.首页首页上页上页返回返回下页下页 引例引例33输油管网络输油管网络 有有5个城市个城市A、B、C、D、E，它，它们之间有输油管相连们之间有输油管相连（A，B），（），（A，

8、C），（），（A，E），（B，C），（），（C，D）.而这些油管的长度分别为：而这些油管的长度分别为：100km，120km，60km，80km，90km.试将它们的关系试将它们的关系用图表示出来用图表示出来.ABCDE 分析分析 我们把我们把5个城市个城市A、B、C、D、E分别用点表示分别用点表示.若两城市之间有输油管相联，若两城市之间有输油管相联，则用线连结，否则不连结则用线连结，否则不连结.为为了表示里程数，将各输油管长了表示里程数，将各输油管长度标在相应的边上，可得到右度标在相应的边上，可得到右图，即为所作的关系图图，即为所作的关系图.100809060120首页首页上页上页返回返回下

9、页下页ABCDE100809060120 若一个图的每条边均附有数量信息，则这图称为若一个图的每条边均附有数量信息，则这图称为赋权图赋权图，而附加的数量信息称为相应边的，而附加的数量信息称为相应边的权数权数.赋权图赋权图首页首页上页上页返回返回下页下页ABCDEF111320.50.5 例例1 某产品的生产流程为：第一车间和第二车间都从原材某产品的生产流程为：第一车间和第二车间都从原材料库领取原材料，用时都为料库领取原材料，用时都为1h；第一车间加工后的半成品送；第一车间加工后的半成品送到第二车间，用时到第二车间，用时3 h；经第二车间加工后部分送到总装车间，；经第二车间加工后部分送到总装车间

10、，用时用时0.5 h，部分送到第三车间再加工，用时，部分送到第三车间再加工，用时2 h，然后再送，然后再送到总车间总装，用时到总车间总装，用时0.5 h；经总装后的成品送入成品库，用；经总装后的成品送入成品库，用时时1 h.试将这一流程用图表示试将这一流程用图表示.首页首页上页上页返回返回下页下页2连通图连通图看右边图：看右边图：v1v2v3v4v5v1v2v3v4 这种由首尾连结的边构这种由首尾连结的边构成的序列叫做成的序列叫做图的通路图的通路.通路通路中的边数叫做中的边数叫做通路的长度通路的长度.将通路中的结点依次排成的序列来表示这条通路，其将通路中的结点依次排成的序列来表示这条通路，其第

11、一个点为第一个点为通路的起点通路的起点，最后一个点为，最后一个点为通路的终点通路的终点.讨论讨论：图中的下面几条通路有何特点，长度为多少？：图中的下面几条通路有何特点，长度为多少？v1v2v3v4v5,v1v2v4v5,v2v3v4v2,v3v4v2v3首页首页上页上页返回返回下页下页起点与终点相同的通路称为起点与终点相同的通路称为图的回路图的回路.任意两点之间均有通路的图称为任意两点之间均有通路的图称为连通图连通图.v1v2v3v4v5连通图连通图首页首页上页上页返回返回下页下页ABCDE100809060120讨论讨论：下图是否为连通图？：下图是否为连通图？ABCDEF赋权连通图称为赋权连

12、通图称为网络网络.首页首页上页上页返回返回下页下页下面研究一类特殊的连通图下面研究一类特殊的连通图欧拉图欧拉图。ABCD问问：一笔可以画出下面的图吗？：一笔可以画出下面的图吗？ABFDCDE 若一个图中存在经过每一条边一次且仅一次的通路，若一个图中存在经过每一条边一次且仅一次的通路，则此路称为则此路称为欧拉通路欧拉通路。若一个图中存在经过每一条边一次且仅一次的回路，若一个图中存在经过每一条边一次且仅一次的回路，则此回路称为则此回路称为欧拉回路欧拉回路.具有欧拉回路的图称为具有欧拉回路的图称为欧拉图欧拉图.首页首页上页上页返回返回下页下页问问：如何判定一个图为欧拉图呢？：如何判定一个图为欧拉图呢

13、？定理定理3 无向连通图中结点无向连通图中结点vi和和vj间存在欧拉通路的间存在欧拉通路的充分必要条件是充分必要条件是vi和和vj的次数均为奇数，而其他结点的的次数均为奇数，而其他结点的次数均为偶数次数均为偶数.定理定理4 无向连通图是欧拉图的充要条件是每个结无向连通图是欧拉图的充要条件是每个结点的次数均为偶数点的次数均为偶数.首页首页上页上页返回返回下页下页ABFDCDE例例：判断下面的图是否为欧拉图？：判断下面的图是否为欧拉图？ABDCE首页首页上页上页返回返回下页下页3树树 定义定义 若一个图是连通的，且不包含回路，则这样的若一个图是连通的，且不包含回路，则这样的图称为图称为树树.例例3

14、 试判断图中哪些是树，哪些不是树，并说明理由试判断图中哪些是树，哪些不是树，并说明理由.AAACBEDCBEDCBED（1）（2）（3）不不连连通通有有回回路路 在图在图3中，若去掉边中，若去掉边CE，则可得到图，则可得到图2.因此，图因此，图2可看作可看作是由图是由图3的一部分（称为的一部分（称为子图子图）构成的树，称为）构成的树，称为生成树生成树.首页首页上页上页返回返回下页下页小结：小结：1、图的基本概念、图的基本概念（1）图；）图；（2）简单图；）简单图；（3）有向图，无向图；）有向图，无向图；（4）赋权图。）赋权图。2、连通图、连通图（1）通路，回路；）通路，回路；（2）连通图；）连

15、通图；（3）网络；）网络；（4）欧拉通路，欧拉回路，）欧拉通路，欧拉回路，欧拉图。欧拉图。3、树、树（1）树；）树；（2）生成树。）生成树。首页首页上页上页返回返回下页下页应用案例应用案例 案例案例11洒水路线洒水路线 某城市街道如图所示某城市街道如图所示.洒水车从洒水车从A点出点出发，执行洒水任务发，执行洒水任务.问：是否存在一条洒水路径，使洒水车从问：是否存在一条洒水路径，使洒水车从A点出发通过所有街道且不重复而最后回到车库点出发通过所有街道且不重复而最后回到车库B？ABFGCDEFACDEFBGCFGA欧拉回路欧拉回路首页首页上页上页返回返回下页下页 案例案例2（七桥问题）（七桥问题）哥

16、尼斯堡城的居民有郊游的习惯哥尼斯堡城的居民有郊游的习惯.在城郊的普雷格尔河畔，河中有两个小岛在城郊的普雷格尔河畔，河中有两个小岛C、D，七座桥，七座桥将两个小岛与河岸将两个小岛与河岸A、B连接（见图）连接（见图）.问是否存在这样的问是否存在这样的游玩路径：从游玩路径：从A、B、C、D中任一地出发，不重复走遍七中任一地出发，不重复走遍七座桥，再回到原出发地？座桥，再回到原出发地？DCAB答：答：这样的路线不存在。这样的路线不存在。ADBC首页首页上页上页返回返回下页下页 案例案例3（保卫油网）（保卫油网）设有设有6个城市个城市A、B、C、E、F、G，它们间有输油管连通，其分布如图所示（图中的数字

17、，它们间有输油管连通，其分布如图所示（图中的数字表示油管的长度）表示油管的长度）.为了保卫油管不受破坏，在每段油管为了保卫油管不受破坏，在每段油管间需派一连士兵看守间需派一连士兵看守.问：至少需派多少连士兵，他们应问：至少需派多少连士兵，他们应驻在哪些油管处？驻在哪些油管处？ABCDEF25411222443首页首页上页上页返回返回下页下页（2）将原图所有边删去，保留所有结点）将原图所有边删去，保留所有结点.（3）按表中的次序将边加入图中）按表中的次序将边加入图中.（4）如出现回路，则删去权为最大的边，即得最短树）如出现回路，则删去权为最大的边，即得最短树.解：解：寻找最短生成树问题。寻找最短

18、生成树问题。（1）将所有边排序：）将所有边排序：边边 ACCDABCEBDEFDFADEDCFBC权权 1 1 2 2 2 2 3 4 4 4 5ABCDEF25411222443首页首页上页上页返回返回下页下页ABCDEFFABCDE2112ABCDEF211ABCDE21122答：答：只需派只需派5个连驻守个连驻守.守卫油管的总长度为守卫油管的总长度为8 首页首页上页上页返回返回下页下页综合实训综合实训课课 外（外（P143）第第1题；第题；第2题；第题；第3题；第题；第5题题.判断：判断：ABCDE（1）上图是简单图。）上图是简单图。（2）上图是连通图。）上图是连通图。（3）上图是欧拉图。）上图是欧拉图。（4）上图是树。）上图是树。（5）上图是网络。）上图是网络。