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

1、第11章 图论基础与计划编制方法111 图论基础112 工程项目计划的横道图表示法113 网络计划技术的概念及其表示114 网络计划的优化第11章 图论基础与计划编制方法111 图论基础1111 图论基础111 图论基础基础知识1、图的基本概念 引例1公路网 有6个城镇A、B、C、D、E、F，它们之间有公路直通的情况是：（A，B）、（A，C）、（A，E）、（A，F）、（B，C）、（B，D）、（D，F）、（E，F）. 试将它们的关系用图表示出来. 分析 我们把6个城镇A、B、C、D、E、F分别用点表示. 若两城镇之间有公路直通，则用线相连结，否则不连结，可得到右图，即为所作的关系图. ABCDE

2、F基础知识1、图的基本概念 引例1公路网 把A、B、C、D、E、F对应的点看成一个集合，“线”是这个集合中“点”之间的关系，那么，图论正是研究像这样的有限集合及其关系的一门数学科学. 在这里，“线”是不论其曲直形状的，通常称为边，“点”是不论其上下位置的，通常称为结点. 由这样的结点和边构成的整体，就叫做图. A、B两点有线相连，称A和B是邻接的点；而连线称为与A、B两点相关联的边，记作(A,B). 结点邻接点相关联的边ABCDEF把A、B、C、D、E、F对应的点看成一个集合，“线”是这个集 若图中一边的两个相关联的结点相同，则称为环. 若图中两边具有相同的一对结点，则称为平行边. 没有环和平

3、行边的图称为简单图. ABCDEF环平行边讨论：以上两图中哪一个为简单图？ABCDEF 若图中一边的两个相关联的结点相同，则称为环. 这里的图与平面几何里的图形是不相同的. 这里的图只考虑结点、边以及边与结点的对应关系，因此当两个图的形状看似不同，但若它们的结点集、边集及边与结点的关联关系都相同时，则可将它们看作同一个图. 这时，称这两个图是同构的. 同构点与点1-1对应，线与线1-1对应 这里的图与平面几何里的图形是不相同的. 这里与A点关联的所有边的条数称为A点的次数，记作degA. ABCDEF孤立点次数为零的结点称为孤立点. ABCDEFdegA=4，degB=degF=3，degC=

4、degD=degE=2.例：求图中各点的次数问：下图中F点的次数是多少？与A点关联的所有边的条数称为A点的次数，记作degA. AB定理1 任一图中点的次数之和等于边数的两倍. 定理2 任一图中次数为奇数的点的个数必为偶数. 讨论：图中点的次数与边数有何联系？ABCDEF定理1 任一图中点的次数之和等于边数的两倍. 讨论：图中点 引例2程序调用 有4个程序 ，它们的调用关系是： 能调用 ； 能调用 ， 能调用 . 试将它们的关系用图表示出来. 分析 将4个程序分别用点来表示. 由于调用是有顺序的，因此它们之间的调用关系用一条有方向的线相连结，得到下图，即为所作的关系图. p1p2p3p4 图中

5、的边带有方向，通常称为有向边. 若一个图中所有边均是有向边，则称这图为有向图. 若一个图中所有边均是无向边，则称这图为无向图. 引例2程序调用 有4个程序 引例3输油管网络 有5个城市A、B、C、D、E，它们之间有输油管相连（A，B），（A，C），（A，E），（B，C），（C，D）. 而这些油管的长度分别为：100km，120km，60km，80km，90km. 试将它们的关系用图表示出来.ABCDE 分析 我们把5个城市A、B、C、D、E分别用点表示. 若两城市之间有输油管相联，则用线连结，否则不连结. 为了表示里程数，将各输油管长度标在相应的边上，可得到右图，即为所作的关系图. 10080

6、9060120 引例3输油管网络 有5个城市A、B、C、D、EABCDE100809060120 若一个图的每条边均附有数量信息，则这图称为赋权图，而附加的数量信息称为相应边的权数. 赋权图ABCDE100809060120 若一个图的ABCDEF111320.50.5 例1 某产品的生产流程为：第一车间和第二车间都从原材料库领取原材料，用时都为1h；第一车间加工后的半成品送到第二车间，用时3 h；经第二车间加工后部分送到总装车间，用时0.5 h，部分送到第三车间再加工，用时2 h，然后再送到总车间总装，用时0. 5 h；经总装后的成品送入成品库，用时1 h. 试将这一流程用图表示. ABCD

7、EF111320.50.5 例1 某产品的生2连通图看右边图：v1v2v3v4v5v1v2v3v4 这种由首尾连结的边构成的序列叫做图的通路. 通路中的边数叫做通路的长度. 将通路中的结点依次排成的序列来表示这条通路，其第一个点为通路的起点，最后一个点为通路的终点. 讨论：图中的下面几条通路有何特点，长度为多少？v1v2v3v4v5, v1v2v4v5, v2v3v4v2, v3v4v2v32连通图看右边图：v1v2v3v4v5v1v2v3v4 起点与终点相同的通路称为图的回路. 任意两点之间均有通路的图称为连通图. v1v2v3v4v5连通图起点与终点相同的通路称为图的回路. 任意两点之间均

8、有通路的图ABCDE100809060120讨论：下图是否为连通图？ABCDEF赋权连通图称为网络. ABCDE100809060120讨论：下图是否为连通图？A下面研究一类特殊的连通图欧拉图。ABCD问：一笔可以画出下面的图吗？ABFDCDE 若一个图中存在经过每一条边一次且仅一次的通路，则此路称为欧拉通路。 若一个图中存在经过每一条边一次且仅一次的回路，则此回路称为欧拉回路. 具有欧拉回路的图称为欧拉图. 下面研究一类特殊的连通图欧拉图。ABCD问：一笔可以画出问：如何判定一个图为欧拉图呢？ 定理3 无向连通图中结点vi和vj间存在欧拉通路的充分必要条件是vi和vj的次数均为奇数，而其他结

9、点的次数均为偶数. 定理4 无向连通图是欧拉图的充要条件是每个结点的次数均为偶数.问：如何判定一个图为欧拉图呢？ 定理3 无向ABFDCDE例：判断下面的图是否为欧拉图？ABDCEABFDCDE例：判断下面的图是否为欧拉图？ABDCE3树 定义 若一个图是连通的，且不包含回路，则这样的图称为树. 例3 试判断图中哪些是树，哪些不是树，并说明理由. AAACBEDCBEDCBED（1）（2）（3）不连通有回路 在图3中，若去掉边CE，则可得到图2. 因此，图2可看作是由图3的一部分（称为子图）构成的树，称为生成树. 3树 定义 若一个图是连通的，且不包含回路小结：1、图的基本概念（1）图；（2）

10、简单图；（3）有向图，无向图；（4）赋权图。2、连通图（1）通路，回路；（2）连通图；（3）网络；（4）欧拉通路，欧拉回路，欧拉图。3、树（1）树；（2）生成树。小结：1、图的基本概念2、连通图3、树应用案例 案例1洒水路线 某城市街道如图所示. 洒水车从A点出发，执行洒水任务. 问：是否存在一条洒水路径，使洒水车从A点出发通过所有街道且不重复而最后回到车库B？ ABFGCDEFACDEFBGCFGA欧拉回路应用案例 案例1洒水路线 某城市街道如图所示. 案例2（七桥问题） 哥尼斯堡城的居民有郊游的习惯. 在城郊的普雷格尔河畔，河中有两个小岛C、D，七座桥将两个小岛与河岸A、B连接（见图）.

11、问是否存在这样的游玩路径：从A、B、C、D中任一地出发，不重复走遍七座桥，再回到原出发地？答：这样的路线不存在。ADBC 案例2（七桥问题） 哥尼斯堡城的居民有郊游 案例3（保卫油网） 设有6个城市A、B、C、E、F、G，它们间有输油管连通，其分布如图所示（图中的数字表示油管的长度）. 为了保卫油管不受破坏，在每段油管间需派一连士兵看守. 问：至少需派多少连士兵，他们应驻在哪些油管处？ABCDEF25411222443 案例3（保卫油网） 设有6个城市A、B、C（2）将原图所有边删去，保留所有结点. （3）按表中的次序将边加入图中.（4）如出现回路，则删去权为最大的边，即得最短树. 解：寻找最短生成树问题。（1）将所有边排序：边ACCDABCEBDEFDFADEDCFBC权11222234445ABCDEF25411222443（2）将原图所有边删去，保留所有结点. （3）按表中的次序将ABCDEFFABCDE2112ABCDE