数模培训_图论模型.ppt

2017-2-27 南京信息工程大学数理学院费文龙 1图论模型主讲:费文龙 Feiwl. ******@nuist. 数学建模培训 2017-2-27 南京信息工程大学数理学院费文龙 2图论模型 2017-2-27 南京信息工程大学数理学院费文龙 3 1 1、图论的基本概念、图论的基本概念 AB CD 哥尼斯堡七桥示意图问题 1(哥尼斯堡七桥问题): 能否从任一陆地出发通过每座桥恰好一次而回到出发点? 2017-2-27 南京信息工程大学数理学院费文龙 4A B D C七桥问题模拟图欧拉指出: 如果每块陆地所连接的桥都是偶数座,则从任一陆地出发, 必能通过每座桥恰好一次而回到出发地. 2017-2-27 南京信息工程大学数理学院费文龙 5 问题 2(哈密顿环球旅行问题): 十二面体的 20个顶点代表世界上 20个城市,能否从某个城市出发在十二面体上依次经过每个城市恰好一次最后回到出发点? 哈密顿圈(环球旅行游戏) 2017-2-27 南京信息工程大学数理学院费文龙 6 问题 3(四色问题):对任何一张地图进行着色,两个共同边界的国家染不同的颜色, 4(关键路径问题):一项工程任务,大到建造一座大坝,一座体育中心,小至组装一台机床,一架电视机, ,只有在某些工序完成之后, 一个工序才能开始. 即它们之间存在完成的先后次序关系,一般认为这些关系是预知的, 而且也能够预计完成每个工序所需要的时间. 这时工程领导人员迫切希望了解最少需要多少时间才能够完成整个工程项目, 影响工程进度的要害工序是哪几个? 2017-2-27 南京信息工程大学数理学院费文龙 7 图的定义图的定义图论中的“图”并不是通常意义下的几何图形或物体的形状图, 而是以一种抽象的形式来表达一些确定的事物之间的联系的一个数学系统. 定义 1 一个有序二元组(V, E ) 称为一个图, 记为 G = (V, E ), 其中① V称为 G的顶点集, V ≠?, 其元素称为顶点或结点, 简称点; ② E称为 G的边集, 其元素称为边, 它联结 V 中的两个点, 如果这两个点是无序的, 则称该边为无向边, 否则, 称为有向边. 如果 V = {v1, v2, …, vn} 是有限非空点集, 则称 G为有限图或 n阶图. 2017-2-27 南京信息工程大学数理学院费文龙 8 如果 E的每一条边都是无向边, 则称 G为无向图(如图 1); 如果 E的每一条边都是有向边, 则称 G为有向图(如图 2); 否则, 称G为混合图. 图1 图2 并且常记 V = {v1, v2, … , vn}, |V | = n ; E = {e1, e2, … , em}(ek=vivj ) , |E | = m. 称点 vi , vj 为边 vivj 的端点. 在有向图中, 称点 vi , vj 分别为边 vivj 的始点和终点. 该图称为(n,m) 图 2017-2-27 南京信息工程大学数理学院费文龙 9 对于一个图 G = (V, E ), 人们常用图形来表示它, 称其为图解. 凡是有向边, 在图解上都用箭头标明其方向. 例如, 设 V = {v1 , v2 , v3 , v4}, E = { v1v2 , v1v3 , v1v4 , v2v3 , v2v4 , v3v4}, 则 G = (V, E ) 是一个有 4个顶点和 6条边的图, G 的图解如下图所示. 2017-2-27 南京信息工程大学数理学院费文龙 10 一个图会有许多外形不同的图解, 下面两个图表示同一个图 G = (V, E ) V = {v1 , v2 , v3 , v4}, E = { v1v2 , v1v3 , v1v4 , v2v3 , v2v4 , v3v4}. 这两个图互为同构图,今后将不计较这种外形上的差别,而用一个容易理解的、确定的图解去表示一个图.