图的基本概念PPT学习教案

1、会计学1图的基本概念图的基本概念12、07乘公交，看奥运第1页/共51页第2页/共51页 1) 98 1) 98年全国大学生数学建模竞赛年全国大学生数学建模竞赛B B题题“最佳灾最佳灾 今年今年(1998年年)夏天某县遭受水灾夏天某县遭受水灾. 为考察灾情为考察灾情、组织自救，县领导决定，带领有关部门负责人到组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视全县各乡（镇）、村巡视. 巡视路线指从县政府巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线府所在地的路线.情巡视路线情巡视路线”中的前两个问题是这样的：中的

2、前两个问题是这样的：第3页/共51页 1）若分三组（路）巡视，试设计总路程最）若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线短且各组尽可能均衡的巡视路线. 2）假定巡视人员在各乡（镇）停留时间）假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间小时，在各村停留时间t=1小时，汽车行驶速度小时，汽车行驶速度V=35公里公里/小时小时. 要在要在24小时内完成巡视，至少应小时内完成巡视，至少应分分几组；给出这种分组下最佳的巡视路线几组；给出这种分组下最佳的巡视路线.第4页/共51页公路边的数字为该路段的公里数公路边的数字为该路段的公里数.第5页/共51页2) 2) 问题分析

3、：问题分析：本题给出了某县的公路网络图，要求的是在不本题给出了某县的公路网络图，要求的是在不同的条件下，灾情巡视的最佳分组方案和路线同的条件下，灾情巡视的最佳分组方案和路线. 将每个乡（镇）或村看作一个图的顶点，各乡将每个乡（镇）或村看作一个图的顶点，各乡镇、村之间的公路看作此图对应顶点间的边，各镇、村之间的公路看作此图对应顶点间的边，各条条再回到点再回到点O，使得总权（路程或时间）最小，使得总权（路程或时间）最小.公路的长度（或行驶时间）看作对应边上的权，公路的长度（或行驶时间）看作对应边上的权，所所给公路网就转化为加权网络图，问题就转化图论给公路网就转化为加权网络图，问题就转化图论中中一类

4、称之为旅行售货员问题，即在给定的加权网一类称之为旅行售货员问题，即在给定的加权网络络图中寻找从给定点图中寻找从给定点O出发，行遍所有顶点至少一次出发，行遍所有顶点至少一次第6页/共51页第7页/共51页第8页/共51页第9页/共51页D DA AB BC C图 第10页/共51页D DA AB BC CA AB BC CD Dv建模： 点陆地 岛屿 边桥Euler的做法：图 图 第11页/共51页第12页/共51页十二面体的十二面体的20个顶点代表世界上个顶点代表世界上20个城市，能个城市，能否从某个城市出发在十二面体上依次经过每个否从某个城市出发在十二面体上依次经过每个城市恰好一次最后回到出

5、发点？城市恰好一次最后回到出发点？第13页/共51页第14页/共51页德德摩尔根致哈密顿的信（摩尔根致哈密顿的信（1852年年10月月23日）日） 我的一位学生今天请我解释一个我过去不知道，现在仍不甚了了的事实。他说如果任意划分一个图形并给各部分着上颜色，使任何具有公共边界的部分颜色不同，那么需要且仅需要四种颜色就够了。下图是需要四种颜色的例子（图1）。第15页/共51页第16页/共51页第17页/共51页第18页/共51页同的。如何分配工作方案可以使总回报最大？第19页/共51页第20页/共51页北京天津济南青岛郑州徐州连云港南京上海.武汉一、图论的基本概念第21页/共51页例2 8种化学品

6、，某些药品不能存放在同一个库房里，求库房最少。图示：2v4v3v7v5v6v8v1v第22页/共51页。5v4v3v2v1v第23页/共51页第24页/共51页 定义定义 一个一个图图G是指一个二元组是指一个二元组(V(G),E(G)，其中，其中: 其中元素称为图其中元素称为图G的的顶点顶点.组成的集合，即称为组成的集合，即称为边集边集,其中元素称为其中元素称为边边.),(jivv 定义定义 图图G的的阶阶是指图的顶点数是指图的顶点数|V(G)|, 用用来表示；来表示；v图的边的数目图的边的数目|E(G)|用用 来表示来表示. 也用也用来表示边来表示边jivv).,(jivv,)(21vvvG

7、V是非空有限集，称为是非空有限集，称为顶点集顶点集，1)2) E(G)是顶点集是顶点集V(G)中的无序或有序的元素偶对中的无序或有序的元素偶对).,(EVG )(),(GEGVG 表示图，表示图，简记简记 用用第25页/共51页 其为其为有限图有限图. 只有一个顶点的图称为只有一个顶点的图称为平凡图平凡图，其他的，其他的 所有图都称为所有图都称为非平凡图非平凡图.第26页/共51页 一个图会有许多外形不同的图解一个图会有许多外形不同的图解, , 下面两个下面两个图表示同一个图图表示同一个图G = (V, E )的图解的图解. .其中其中V = v1 , v2 , v3 , v4,E = v1v

8、2 , v1v3 , v1v4 , v2v3 , v2v4 , v3v4. 今后将不计较这种外形上的差别今后将不计较这种外形上的差别, ,而用一个容而用一个容易理解的、确定的图解去表示一个图易理解的、确定的图解去表示一个图. .第27页/共51页。5v4v3v2v1v例3 （非对称关系图）有5个球队，他们之间的比赛情况，可以用图表示出来。第28页/共51页,称称G为为有向图有向图),(jivv边边 为为无向边无向边，称，称e连接连接 和和 ，顶点，顶点 和和 称称称边称边为为有向边有向边或或弧弧。),(jivve称称 为为e的的尾尾，称，称 为为e的的头头. ivjv 若图若图G中的边均为无序

9、偶对中的边均为无序偶对 ，称，称G为为无向图无向图.jivv为为e的的端点端点. jivve ivjvivjv 既有无向边又有有向边的图称为既有无向边又有有向边的图称为混合图混合图.第29页/共51页1) 边和它的两端点称为互相边和它的两端点称为互相关联关联.2)与同一条边关联的两个端点与同一条边关联的两个端点称称为为相邻相邻的顶点，与同一个顶点的顶点，与同一个顶点 点关联的两条边称为点关联的两条边称为相邻相邻的边的边. 3) 端点重合为一点的边称为端点重合为一点的边称为环环，4) 若一对顶点之间有两条以上的边联结，则这些边若一对顶点之间有两条以上的边联结，则这些边 称为称为重边重边第30页/

10、共51页图 5) 既没有环也没有重边的图，称为既没有环也没有重边的图，称为简单图简单图 第31页/共51页图 第32页/共51页2nC第33页/共51页是是3正则图。正则图。完全图完全图不是完全图不是完全图第34页/共51页)(),(GEGVG 一个实数一个实数w(e)，称，称w(e)为边为边e的的权权，G 连同边上的权连同边上的权称为称为赋权图赋权图. 定义定义 设设 和和 是两个图是两个图.),(EVG ),(EVG 1) 若若 ,称称 是是 的一个的一个子图子图,记记 EEVV,GG.GG 2) 若若 ， ，则称，则称 是是 的的生成子图生成子图.VV EE GG第35页/共51页,32

11、1vvvG,6543eeeeG 3) 若若 ，且，且 ，以，以 为顶点集，以两端点为顶点集，以两端点 VV VV 均在均在 中的边的全体为边集的图中的边的全体为边集的图 的子图，称的子图，称 VG4) 若若 ，且，且 ，以，以 为边集，以为边集，以 的端点的端点EE EEE 集为顶点集的图集为顶点集的图 的子图，称为的子图，称为 的的由由 导出导出的的GGE 边导出的子图边导出的子图，记为，记为 . EGGVVG 为为 的的由由 导出的子图导出的子图，记为，记为 .第36页/共51页定义定义 1) 在无向图在无向图G中，与顶点中，与顶点v关联的边的数目关联的边的数目(环环算两次算两次),称为顶

12、点称为顶点v的的度度或或次数次数，记为，记为d(v)或或 dG(v).称度为奇数的顶点为称度为奇数的顶点为奇点奇点，度为偶数的顶点为，度为偶数的顶点为偶点偶点.2) 在有向图中，从顶点在有向图中，从顶点v引出的边的数目称为顶点引出的边的数目称为顶点 v的的出度出度，记为，记为d+(v)，从顶点，从顶点v引入的边的数目称为引入的边的数目称为 v的的入度入度，记为，记为d -(v). 称称d(v)= d+(v)+d -(v)为顶点为顶点v的的 度度或或次数次数4)(1vd1)(3ud2)(3ud3)(3ud第37页/共51页mvdnii2)(1第38页/共51页第39页/共51页( ,)GV E1

13、12211(,)kkkiiiiiiiv e vevev1,(1,2,1)tttiiiev vtk1ivkiv121(,)kkiiiiv vvv121,kkiiiiv vvv第40页/共51页121(,)kkiiiiv vvv1kiivv121(,)kkiiiiv vvv链 中，点 均不同，称之为初等链初等链121,kkiiiiv vvv1211(,)kiiiiv vvv链 中， 均不同，称之为初等圈初等圈。若链（圈）中含的边均不相同，称之为简单（链）圈或迹简单（链）圈或迹121,kiiiv vv第41页/共51页8v9v10e1v2v4v7v5v3v6v5e4e3e6e9e8e2e1e7e1,

14、2345367(,)v v v v v v v v是一条简单链，不是初等链1,2367(,)v v v v v是一条初等链1,234589(,)v v v v v v v不存在41,2357634(,)v v v v v v v v v是简单圈，不是初等圈第42页/共51页 （1）若途径）若途径W的顶点和边均互不相同，则称的顶点和边均互不相同，则称W为为路路或或路径路径. 一条起点为一条起点为 ,终点为终点为 的路称为的路称为 路路0vkv),(0kvv记为记为).,(0kvvP（2）若在图）若在图G中存在中存在(u,v)路，则称顶点路，则称顶点u和和v在图在图G中中连通连通. （3）若在图）

15、若在图G中顶点中顶点u和和v是连通的，则顶点是连通的，则顶点u和和v之之之间的之间的距离距离d(u,v)是指图是指图G中最短中最短(u,v)路的长；若没路的长；若没没有路连接没有路连接u和和v，则定义为无穷大，则定义为无穷大.第43页/共51页（4）图）图G中任意两点皆连通的图称为中任意两点皆连通的图称为连通图连通图 （5） 对于有向图对于有向图G，若，若 ，且，且 有有kkveevevW2110ie 类似地，可定义类似地，可定义有向迹有向迹，有向路有向路和和有向圈有向圈.头头 和尾和尾 ，则称，则称W为为有向途径有向途径.iv1iv 例例 在右图中：在右图中： 路或路径：路或路径： 圈或回路

16、：圈或回路：uavdxcwuuavbwcxfyg第44页/共51页 例例 一摆渡人欲将一只狼一摆渡人欲将一只狼, ,一头羊一头羊, ,一篮菜从一篮菜从河西渡过河到河东河西渡过河到河东. .由于船小由于船小, ,一次只能带一物过一次只能带一物过河，并且狼与羊河，并且狼与羊, ,羊与菜不能独处羊与菜不能独处. .给出渡河方法给出渡河方法. . 解解：用四维：用四维0-10-1向量表示向量表示( (人人, ,狼狼, ,羊羊, ,菜菜) )在河在河西岸的状态西岸的状态( (在河西岸则分量取在河西岸则分量取1,1,否则取否则取0),0),共有共有24 =16 种状态种状态. .由由题设题设, ,状态状态

17、(0,1,1,0),(0,0,1,1),(0,1,1,1)(0,1,1,0),(0,0,1,1),(0,1,1,1)是不允许的是不允许的, ,从而对应状态从而对应状态(1,0,0,1), (1,1,0,0),(1,0,0,1), (1,1,0,0), (1,0,0,0) (1,0,0,0)也是不允许的也是不允许的. .第45页/共51页第46页/共51页打，于是问题可用穷举法解答如下：第47页/共51页(1,0,1,0)(0,1,0,1)(1,1,0,0)(0,0,1,1)(1)(1,1,1,1)(1,0,0,1)(0,1,1,0)(1,0,0,0)(0,1,1,1)(1,0,1,0)(1,1

18、,1,1)(1,1,0,0)(1,0,1,1)(2)(0,1,0,1)(1,0,0,1)(1,1,0,0)(1,0,0,0)(1,1,0,1)(1,0,1,0)(0,1,1,1)(1,1,0,0)(0,0,0,1)(3)(1,1,0,1)(1,0,0,1)(0,1,0,0)(1,0,0,0)(0,1,0,1)(人人,狼狼,羊羊,菜菜)第48页/共51页1(1,0,1,0)(1,0,1,1)(1,1,0,0)(1,1,0,1)(4) (0,0,0,1)(1,0,0,1)(1,0,0,0)(1,0,0,0)(1,0,0,1)1(1,0,1,0)(0,0,0,1)(1,1,0,0)(0,1,1,1)(5) (1,0,1,1)(1,0,0,1)(0,0,1,0)(1,0,0,0)(0,0,1,1)2(1,0,1,0)(1,1,1,0)(1,1,0,0)(1,0,0,0)(4) (0,1,0,0)(1,0,0,1)(1,1,0,1)