《图论与网络流》PPT课件.ppt

《《图论与网络流》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《图论与网络流》PPT课件.ppt（127页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、B B题题 灾情巡视路线灾情巡视路线 下图为某县的乡（镇）、村公路网示意图，下图为某县的乡（镇）、村公路网示意图，公路边的数字为该路段的公里数。公路边的数字为该路段的公里数。今年夏天该县遭受水灾。为考察灾情、组今年夏天该县遭受水灾。为考察灾情、组织自救，县领导决定，带领有关部门负责人到织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视。灾情巡视路线指从全县各乡（镇）、村巡视。灾情巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线。回到县政府所在地的路线。若分三组（路）巡视，试设计总路程最短若分三组（路）巡视，试设计总路

2、程最短且各组尽可能均衡的灾情巡视路线。且各组尽可能均衡的灾情巡视路线。19981998年全国大学生数学建模竞赛题目年全国大学生数学建模竞赛题目 假定巡视人员在各乡（镇）停留时间假定巡视人员在各乡（镇）停留时间T=2T=2小时，在小时，在各村停留时间各村停留时间t=1t=1小时，汽车行驶速度小时，汽车行驶速度V=35V=35公里公里/小时。小时。要要2424小时内完成巡视，至少应分几组；给出这种分组小时内完成巡视，至少应分几组；给出这种分组下你认为最佳的灾情巡视路线。下你认为最佳的灾情巡视路线。在上述关于在上述关于T,tT,t和和V V的假定下，如果巡视人员足的假定下，如果巡视人员足够多，完成巡

3、视的最短时间是多少；给出在这种最短够多，完成巡视的最短时间是多少；给出在这种最短时间完成巡视的要求下，你认为最佳的灾情巡视路线。时间完成巡视的要求下，你认为最佳的灾情巡视路线。若巡视组数已定若巡视组数已定(如三组），要求尽快完成巡视，如三组），要求尽快完成巡视，讨论讨论T T，t t和和V V改变对最佳灾情巡视路线的影响。改变对最佳灾情巡视路线的影响。20012001建模竞赛题目（大专组）建模竞赛题目（大专组）C题题基金使用计划基金使用计划某校基金会有一笔数额为某校基金会有一笔数额为M元的基金，打算将其存入银行或元的基金，打算将其存入银行或购买国库券。当前银行存款及各期国库券的利率见下表。假设

4、购买国库券。当前银行存款及各期国库券的利率见下表。假设国库券每年至少发行一次，发行时间不定。取款政策参考银行国库券每年至少发行一次，发行时间不定。取款政策参考银行的现行政策。的现行政策。校基金会计划在校基金会计划在n年内每年用部分本息奖励优秀师生，要求年内每年用部分本息奖励优秀师生，要求每年的奖金额大致相同，且在每年的奖金额大致相同，且在n年末仍保留原基金数额。校基年末仍保留原基金数额。校基金会希望获得最佳的基金使用计划，以提高每年的奖金额。金会希望获得最佳的基金使用计划，以提高每年的奖金额。请你帮助校基金会在如下情况下设计基金使用方案，并对请你帮助校基金会在如下情况下设计基金使用方案，并对M

5、=5000万元，万元，n=10年给出具体结果：年给出具体结果：1.只存款不购国库券；只存款不购国库券；2.可存款也可购国库券；可存款也可购国库券；3.学校在基金到位后的第学校在基金到位后的第3年要举行百年校庆，基金会希望年要举行百年校庆，基金会希望这一年的奖金比其它年度多这一年的奖金比其它年度多20%。银行存款税后银行存款税后年利率（年利率（%）国库券年利率国库券年利率（%）活期活期0.792半年期半年期1.664一年期一年期1.800二年期二年期1.9442.55三年期三年期2.1602.89五年期五年期2.3043.142000“网易杯网易杯”全国大学生数学建模竞赛试题全国大学生数学建模竞

6、赛试题B题题钢管订购和运输钢管订购和运输要铺设一条要铺设一条的输送天然气的主管道的输送天然气的主管道,如图一所示如图一所示(见下见下页页)。经筛选后可以生产这种主管道钢管的钢厂有。经筛选后可以生产这种主管道钢管的钢厂有。图中。图中粗线表示铁路，单细线表示公路，双细线表示要铺设的管粗线表示铁路，单细线表示公路，双细线表示要铺设的管道道(假设沿管道或者原来有公路，或者建有施工公路假设沿管道或者原来有公路，或者建有施工公路)，圆，圆圈表示火车站，每段铁路、公路和管道旁的阿拉伯数字表圈表示火车站，每段铁路、公路和管道旁的阿拉伯数字表示里程示里程(单位单位km)。为方便计，。为方便计，1km主管道钢管称

7、为主管道钢管称为1单位单位钢管。钢管。一个钢厂如果承担制造这种钢管，至少需要生产一个钢厂如果承担制造这种钢管，至少需要生产500个个单位。钢厂单位。钢厂在指定期限内能生产该钢管的最大数量为在指定期限内能生产该钢管的最大数量为个单位，钢管出厂销价个单位，钢管出厂销价1单位钢管为单位钢管为万元，如下表：万元，如下表：1单位钢管的铁路运价如下表：单位钢管的铁路运价如下表：1000km以上每增加以上每增加1至至100km运价增加运价增加5万元。万元。公路运输费用为公路运输费用为1单位钢管每公里单位钢管每公里0.1万元（不足整公里部万元（不足整公里部分按整公里计算）。分按整公里计算）。钢管可由铁路、公路

8、运往铺设地点（不只是运到点钢管可由铁路、公路运往铺设地点（不只是运到点，而是，而是管道全线）。管道全线）。（1）请制定一个主管道钢管的订购和运输计划，使总费）请制定一个主管道钢管的订购和运输计划，使总费用最小（给出总费用用最小（给出总费用)。（2）请就（）请就（1）的模型分析：哪个钢厂钢管的销价的变化）的模型分析：哪个钢厂钢管的销价的变化对购运计划和总费用影响最大，哪个钢厂钢管的产量的上对购运计划和总费用影响最大，哪个钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大，并给出相应的限的变化对购运计划和总费用的影响最大，并给出相应的数字结果。数字结果。（3）如果要铺设的管道不是一条线，而是一

9、个树形图，）如果要铺设的管道不是一条线，而是一个树形图，铁路、公路和管道构成网络，请就这种更一般的情形给出铁路、公路和管道构成网络，请就这种更一般的情形给出一种解决办法，并对图二按（一种解决办法，并对图二按（1）的要求给出模型和结果）的要求给出模型和结果。2008 2008年北京奥运会的建设工作已经进入全面设计和年北京奥运会的建设工作已经进入全面设计和实施阶段。奥运会期间，在比赛主场馆的周边地区需要建设由实施阶段。奥运会期间，在比赛主场馆的周边地区需要建设由小型商亭构建的临时商业网点，称为迷你超市（小型商亭构建的临时商业网点，称为迷你超市（Mini Mini Supermarket,Super

10、market,以下记做以下记做MSMS）网，以满足观众、游客、工作人）网，以满足观众、游客、工作人员等在奥运会期间的购物需求，主要经营食品、奥运纪念品、员等在奥运会期间的购物需求，主要经营食品、奥运纪念品、旅游用品、文体用品和小日用品等。在比赛主场馆周边地区设旅游用品、文体用品和小日用品等。在比赛主场馆周边地区设置的这种置的这种MSMS，在地点、大小类型和总量方面有三个基本要求：，在地点、大小类型和总量方面有三个基本要求：满足满足奥运会期间的购物需求、分布基本均衡和商业上赢利奥运会期间的购物需求、分布基本均衡和商业上赢利。2004年年A题题奥运会临时超市网点设计奥运会临时超市网点设计鸟鸟巢巢国

11、家体育馆国家体育馆水立方水立方请你按以下步骤对图请你按以下步骤对图2 2的的2020个商区设计个商区设计MSMS网点：网点：1 1）根据附录中给出的问卷调查数据，找出观众在出行、用餐）根据附录中给出的问卷调查数据，找出观众在出行、用餐和购物等方面所反映的规律。和购物等方面所反映的规律。2 2）假定奥运会期间（指某一天）每位观众平均出行两次，一）假定奥运会期间（指某一天）每位观众平均出行两次，一次为进出场馆，一次为餐饮，并且出行均采取最短路径。依次为进出场馆，一次为餐饮，并且出行均采取最短路径。依据据1 1的结果，测算图的结果，测算图2 2中中2020个商区的人流量分布（用百分比表个商区的人流量

12、分布（用百分比表示）。示）。3 3）如果有两种大小不同规模的）如果有两种大小不同规模的MSMS类型供选择，给出图类型供选择，给出图220220个商区内个商区内MSMS网点的设计方案（即每个商区内不同类型网点的设计方案（即每个商区内不同类型MSMS的个数），以满足上述三个基本要求。的个数），以满足上述三个基本要求。4 4）阐明你的方法的科学性，并说明你的结果是贴近实际的。）阐明你的方法的科学性，并说明你的结果是贴近实际的。例例1 1 最短路问题最短路问题（SPPSPPshortest path problemshortest path problem）一名货柜车司机奉命在最短的时间内将一车货物从

13、甲地一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地。从甲地到乙地的公路网纵横交错，因此有多种行运往乙地。从甲地到乙地的公路网纵横交错，因此有多种行车路线，这名司机应选择哪条线路呢？车路线，这名司机应选择哪条线路呢？例例2 2 公路连接问题公路连接问题 某一地区有若干个主要城市，现准备修建高速公路把这某一地区有若干个主要城市，现准备修建高速公路把这些城市连接起来，使得从其中任何一个城市都可以经高速公些城市连接起来，使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市。假定已经知道了任意两个城路直接或间接到达另一个城市。假定已经知道了任意两个城市之间修建高速公路的成本，那么应如

14、何决定在哪些城市间市之间修建高速公路的成本，那么应如何决定在哪些城市间修建高速公路，使得总成本最小？修建高速公路，使得总成本最小？假设货柜车的运行速度是恒定的，那么这一问题相当于假设货柜车的运行速度是恒定的，那么这一问题相当于需要找到一条从甲地到乙地的最短路。需要找到一条从甲地到乙地的最短路。例例3 3 指派问题指派问题（assignment problemassignment problem）一家公司经理准备安排一家公司经理准备安排n n名员工去完成名员工去完成n n项任务，每人一项任务，每人一项。由于各员工的特点不同，不同的员工去完成同一项任务项。由于各员工的特点不同，不同的员工去完成同一

15、项任务时所获得的回报是不同的。如何分配工作方案可以使总回报时所获得的回报是不同的。如何分配工作方案可以使总回报最大？最大？例例4 4 中国邮递员问题中国邮递员问题（CPPCPPchinese postman problemchinese postman problem）一名邮递员负责投递某个街区的邮件。如何为他设计一一名邮递员负责投递某个街区的邮件。如何为他设计一条最短的投递路线（从邮局出发，经过投递区内每条街道至条最短的投递路线（从邮局出发，经过投递区内每条街道至少一次，最后返回邮局）？少一次，最后返回邮局）？由于这一问题是我国管梅谷教授由于这一问题是我国管梅谷教授19601960年首先提出

16、的，所年首先提出的，所以国际上称之为中国邮递员问题。以国际上称之为中国邮递员问题。（匹配问题）（匹配问题）例例5 5 旅行商问题旅行商问题（TSPTSPtraveling salesman problemtraveling salesman problem）一名推销员准备前往若干城市推销产品。如何为他一名推销员准备前往若干城市推销产品。如何为他（她）设计一条最短的旅行路线（从驻地出发，经过每个城（她）设计一条最短的旅行路线（从驻地出发，经过每个城市恰好一次，最后返回驻地）？这一问题的研究历史十分悠市恰好一次，最后返回驻地）？这一问题的研究历史十分悠久，通常称之为旅行商久，通常称之为旅行商(推销

17、员）问题。推销员）问题。例例6 6 运输问题运输问题（transportation problemtransportation problem）某种原材料有某种原材料有M M个产地，现在需要将原材料从产地运往个产地，现在需要将原材料从产地运往N N个使用这些原材料的工厂。假定个使用这些原材料的工厂。假定M M个产地的产量和个产地的产量和N N家工厂的家工厂的需求量已知，单位产品从任一产地到任一工厂的运费已知，需求量已知，单位产品从任一产地到任一工厂的运费已知，那么如何安排运输方案可以使总运输成本最低？那么如何安排运输方案可以使总运输成本最低？上述问题有两个共同的上述问题有两个共同的特点特点：一

18、，其目的都是从若干可能的安排或方案中寻求一，其目的都是从若干可能的安排或方案中寻求某种意义下的某种意义下的最优安排或方案最优安排或方案，数学上把这种问题称，数学上把这种问题称为为最优化或优化最优化或优化最优化或优化最优化或优化（optimizationoptimization）问题问题问题问题；二，都易于用图形的形式直观地描述和表达，二，都易于用图形的形式直观地描述和表达，数学上把这种与图相关的结构称为数学上把这种与图相关的结构称为网络网络网络网络（networknetwork）。）。与图和网络相关的最优化问题就是与图和网络相关的最优化问题就是网络最优化网络最优化或称网络优化或称网络优化 （n

19、etwork optimizationnetwork optimization）问题。）问题。由于多数网络优化问题是以网络上的流（由于多数网络优化问题是以网络上的流（flowflow）为研究的对象，因此网络优化又常常被称为网络流为研究的对象，因此网络优化又常常被称为网络流（network flowsnetwork flows）或网络流规划等。）或网络流规划等。故事的背景是十八世纪的东普鲁士，美丽的故事的背景是十八世纪的东普鲁士，美丽的Pregel Pregel 河河穿过哥尼斯堡；人们在河的两岸及河中两个小岛间建立了七穿过哥尼斯堡；人们在河的两岸及河中两个小岛间建立了七座桥，将它们连结成一个风景

20、优美的公园。有一天，有人突座桥，将它们连结成一个风景优美的公园。有一天，有人突发奇想：如何才能走遍七座桥，而每座桥都只能经过一次，发奇想：如何才能走遍七座桥，而每座桥都只能经过一次，最后又回到原先的出发点？最后又回到原先的出发点？例例1 七桥问题七桥问题18世纪东普鲁士哥尼斯堡被普列格尔河分为世纪东普鲁士哥尼斯堡被普列格尔河分为四块，它们通过七座桥相互连接起来，问能否从某块陆地出四块，它们通过七座桥相互连接起来，问能否从某块陆地出发，经每座桥一次而且仅一次，回到出发点？发，经每座桥一次而且仅一次，回到出发点？ACBDABCD任何一个点作为出发点任何一个点作为出发点都必须先都必须先“出出”后后“

21、回回”，才能，才能行遍与该点相连的桥。行遍与该点相连的桥。行行遍遍性性问问题题对此问题，欧拉给出了一个通用对此问题，欧拉给出了一个通用判定规则判定规则判定规则判定规则：从图的某一个顶点出发，经过每从图的某一个顶点出发，经过每条线正好一次，最后回到原来的顶点，条线正好一次，最后回到原来的顶点，当且仅当这个图连成一片且每个顶点当且仅当这个图连成一片且每个顶点都有都有偶数条线偶数条线和它连接。和它连接。思考：思考：能否将图的每一条线走遍，但只走一次。能否将图的每一条线走遍，但只走一次。（不必回到原顶点）（不必回到原顶点）从图的某一个顶点出发，经过每条线正好一次，从图的某一个顶点出发，经过每条线正好一

22、次，当且仅当这个图连成一片且当且仅当这个图连成一片且最多只有两个顶点是奇最多只有两个顶点是奇次的，且必须从某奇次点出发，到另一奇次点结束。次的，且必须从某奇次点出发，到另一奇次点结束。AB BC CD D 以下网络中哪一个是可以遍历的以下网络中哪一个是可以遍历的(即一笔而不重即一笔而不重复地画成复地画成)？一笔画问题一笔画问题 欧拉注意到：一个奇顶点在这种遍历式的旅行中，欧拉注意到：一个奇顶点在这种遍历式的旅行中，要么是起点，要么是终点由于一个遍历的网络只要么是起点，要么是终点由于一个遍历的网络只能有一个起点和一个终点，因而这种网络的能有一个起点和一个终点，因而这种网络的奇点数奇点数不能多于两

23、个不能多于两个 例例2 2 人、狼、羊、菜渡河问题人、狼、羊、菜渡河问题 一个摆渡人一个摆渡人F F希望用一条小船希望用一条小船把一只狼把一只狼WW、一头羊、一头羊G G和一篮白菜和一篮白菜C C从一条河的左岸渡到右岸从一条河的左岸渡到右岸去，而船小只能容纳去，而船小只能容纳F F、WW、G G、C C中的两个，决不能在无人中的两个，决不能在无人看守情况下，留下狼和羊在一起，羊和白菜在一起，问应怎看守情况下，留下狼和羊在一起，羊和白菜在一起，问应怎样渡河才能将狼、羊、白菜都运过去？样渡河才能将狼、羊、白菜都运过去？用小圆圈（顶点）表示河岸左边的各个状态，用小圆圈（顶点）表示河岸左边的各个状态，

24、两点连线两点连线两点连线两点连线当且仅当两状态可在规定允许下转移当且仅当两状态可在规定允许下转移当且仅当两状态可在规定允许下转移当且仅当两状态可在规定允许下转移。FWGCFWGFWCFGCFGWCWGC00FWGC WCFWCCWFGCFWGGFG 一个人带三只狼和三只羊过河，一条船可容两只动物，没人在时，如果狼的数量不少于羊的数量就会吃掉羊，如何安全渡河?有一天，一家人（爸爸、妈妈、2个女儿、2个儿子）和警察、小偷，想过河，船上只能装两个人，爸爸、妈妈、警察三人会划船，在过河的时候，爸爸不在的时候，妈妈会打儿子，妈妈不在的时候，爸爸会打女儿。警察不在的时候，小偷会打一家人。怎样才能使他们安全

25、的过河？例例3 3 化学药品存放问题化学药品存放问题 某公司生产几种化学药品某公司生产几种化学药品a,b,c,d,e,f,ga,b,c,d,e,f,g，其中某些化学药品不相容，为安全，公司要把相容的药品放在不其中某些化学药品不相容，为安全，公司要把相容的药品放在不同格中，问至少应将仓库划分为多少格？同格中，问至少应将仓库划分为多少格？我们可以用顶点表示各个化学药品，两顶点连线当且仅当我们可以用顶点表示各个化学药品，两顶点连线当且仅当两药品不相容，便可得一个图两药品不相容，便可得一个图G:G:adcbefg图图G G的点色数便是所求的最少格数的点色数便是所求的最少格数为每个顶点赋一色，使为每个顶

26、点赋一色，使凡有连线的两顶点异色，凡有连线的两顶点异色，点色数即是使图得到正点色数即是使图得到正常点上色的最少色数。常点上色的最少色数。图的正常点上色图的正常点上色地图着色问题（四色问题）地图着色问题（四色问题）：任何一张地图只用任何一张地图只用四四四四种颜色就能使具有共同种颜色就能使具有共同边界的国家着上不同的颜色。边界的国家着上不同的颜色。111223344 用数学语言表示，即用数学语言表示，即“将平面任意地细分为不相重迭的将平面任意地细分为不相重迭的区域，每一个区域总可以用区域，每一个区域总可以用1 1，2 2，3 3，4 4这四个数字之一来这四个数字之一来标记，而不会使相邻的两个区域得

27、到相同的数字。标记，而不会使相邻的两个区域得到相同的数字。”世界近代三大数学难题：世界近代三大数学难题：1.1.费尔马大定理费尔马大定理 （16371637年）年）在阅读丢番图在阅读丢番图算术算术拉丁文译本时，曾在拉丁文译本时，曾在第第1111卷第卷第8 8命题旁写道：将一个立方数分成两个立方命题旁写道：将一个立方数分成两个立方数之和，或一个四次幂分成两个四次幂之和，或者数之和，或一个四次幂分成两个四次幂之和，或者一般地将一个高于二次的幂分成两个同次幂之和，一般地将一个高于二次的幂分成两个同次幂之和，这是不可能的。这是不可能的。关于此，我确信已发现了一种美妙的证法关于此，我确信已发现了一种美妙

28、的证法关于此，我确信已发现了一种美妙的证法关于此，我确信已发现了一种美妙的证法 ，可，可，可，可惜这里空白的地方太小，写不下惜这里空白的地方太小，写不下惜这里空白的地方太小，写不下惜这里空白的地方太小，写不下。经过三个半世纪的努力，这个世纪数论难题才由普林斯顿大学英国经过三个半世纪的努力，这个世纪数论难题才由普林斯顿大学英国数学家安德鲁数学家安德鲁怀尔斯和他的学生理查怀尔斯和他的学生理查泰勒于泰勒于19951995年成功证明。年成功证明。3.3.哥德巴赫猜想（哥德巴赫猜想（17421742年年6 6月月7 7日，德国数学家在写日，德国数学家在写给著名数学家欧拉的一封信中提出）：给著名数学家欧拉

29、的一封信中提出）：2.2.四色问题四色问题1 1）任何不小于）任何不小于6 6的偶数，都是两个奇质数之和；的偶数，都是两个奇质数之和；2 2）任何不小于）任何不小于9 9的奇数，都是三个奇质数之和。的奇数，都是三个奇质数之和。世界近代三大数学难题：世界近代三大数学难题：任何一张地图只用任何一张地图只用四四四四种颜色就能使具有共同种颜色就能使具有共同边界的国家着上不同的颜色。边界的国家着上不同的颜色。路线着色问题路线着色问题 一个人来到他从未造访过的小镇上，驾着车到处寻找一个人来到他从未造访过的小镇上，驾着车到处寻找他朋友的家，即使连路名都没有。朋友说，别担心，他会他朋友的家，即使连路名都没有。

30、朋友说，别担心，他会指示他如何到达，先向左，再向右，指示他如何到达，先向左，再向右，接着向左接着向左”这个难题的假设是，在出发点（圆点）及道路（直线）这个难题的假设是，在出发点（圆点）及道路（直线）的数量都固定的情况下，应该有办法以不同颜色标示道路，的数量都固定的情况下，应该有办法以不同颜色标示道路，让人不管从哪一个点出发，都能到达固定的点。这在真实让人不管从哪一个点出发，都能到达固定的点。这在真实生活中的情况就像是，不管朋友住在哪里，只要知道你家生活中的情况就像是，不管朋友住在哪里，只要知道你家的位置，绕再远都有办法到你家。的位置，绕再远都有办法到你家。以图为范本，如果按照以图为范本，如果按

31、照 蓝蓝红红红红,蓝蓝红红红红,蓝蓝红红红红.的方式行走，不管从哪个点出发都能到黄色的点；的方式行走，不管从哪个点出发都能到黄色的点；如果是如果是 蓝蓝蓝蓝红红,蓝蓝蓝蓝红红,蓝蓝蓝蓝红红.则一定则一定能到绿点能到绿点 （万能地图）（万能地图）图图：是指某类具体事物和这些事物之间的联系：是指某类具体事物和这些事物之间的联系 如果我们用点表示这些具体事物，用连接两如果我们用点表示这些具体事物，用连接两点的线段（直的或曲的）表示两个事物的特定的点的线段（直的或曲的）表示两个事物的特定的联系，就得到了描述这个联系，就得到了描述这个“图图”的几何形象。的几何形象。图与网络是运筹学（图与网络是运筹学（O

32、perations ResearchOperations Research）中的一个经典和重要的分支，所研究的问题涉及中的一个经典和重要的分支，所研究的问题涉及经济管理、工业工程、交通运输、计算机科学与经济管理、工业工程、交通运输、计算机科学与信息技术、通讯与网络技术等诸多领域。信息技术、通讯与网络技术等诸多领域。最短路问题、行遍性问题、最大流问题、最小最短路问题、行遍性问题、最大流问题、最小费用流问题和匹配问题等都是图与网络的基本问题。费用流问题和匹配问题等都是图与网络的基本问题。例例1 1 线性方程组线性方程组的解取决于：的解取决于：系数系数常数项常数项复习：复习：矩阵矩阵对线性方程组的对

33、线性方程组的研究可转化为对研究可转化为对这张表的研究这张表的研究.线性方程组的系数与常数项按原位置可排为线性方程组的系数与常数项按原位置可排为例例2 2 对随机抽取的对随机抽取的10001000人按性别（男或女）及人按性别（男或女）及色觉（正常或色盲）两个属性分类，得到二行二色觉（正常或色盲）两个属性分类，得到二行二列的列联表列的列联表 :行行列列 由由 个数个数排成的排成的 行行 列的数表列的数表定义：定义：称为称为 行行 列矩阵列矩阵.简称简称 矩阵矩阵.简记为简记为这这个数称为个数称为的元素，简称的元素，简称为元为元.几种特殊矩阵几种特殊矩阵1.1.方阵方阵(SquareMatrix):

34、例如：例如：是一个是一个 3 3 阶方阵阶方阵.行数与列数都等于行数与列数都等于 的矩阵，的矩阵，也可记作也可记作注注 意意 2 2、矩阵的行数和列数可以不等、矩阵的行数和列数可以不等1 1、矩阵是一张数表、矩阵是一张数表2.2.行矩阵行矩阵(RowMatrix)(或行向量或行向量):3.3.列矩阵列矩阵(ColumnMatrix)(或列向量或列向量):):只有一行的矩阵只有一行的矩阵只有一列的矩阵只有一列的矩阵形如形如 的方阵的方阵,4.4.对角矩阵对角矩阵(DiagonalMatrix):记作记作元素不全为元素不全为0 0主对角线主对角线5.5.单位矩阵单位矩阵(IdentityMatri

35、x):主对角线上元素全为主对角线上元素全为1,1,其他元素都是其他元素都是0 0的方阵的方阵6.6.零矩阵零矩阵(Zero Matrix):(Zero Matrix):注意注意不同阶数的零矩阵是不相等的不同阶数的零矩阵是不相等的.例如：例如：元素全为零的矩阵称为零矩阵，元素全为零的矩阵称为零矩阵，零零矩阵记作矩阵记作 或或 .?矩阵的基本运算矩阵的基本运算1.1.矩阵相等矩阵相等矩阵相等矩阵相等:例例 同型同型矩阵：两个矩阵的行数相等、列数也相等矩阵：两个矩阵的行数相等、列数也相等设有两个设有两个 矩阵矩阵 那么矩阵那么矩阵 与与 的和记作的和记作 ，规定为，规定为2.2.矩阵的加减法矩阵的加

36、减法加法加法：例例说明说明只有当两个矩阵是同型矩阵时，才能进只有当两个矩阵是同型矩阵时，才能进行加法运算行加法运算.减法减法:负矩阵负矩阵：矩阵加法满足的矩阵加法满足的运算规律运算规律:3.3.数与矩阵相乘数与矩阵相乘数乘数乘:数乘矩阵的数乘矩阵的运算规律：运算规律：（设（设 为为 矩阵，矩阵，为数）为数）矩阵相加与数乘矩阵合起来矩阵相加与数乘矩阵合起来,统称为矩阵的统称为矩阵的线性运算线性运算.并把此乘积记作并把此乘积记作设设 是一个是一个 矩阵，矩阵，是一个是一个 矩阵，那么规定矩阵矩阵，那么规定矩阵 与矩阵与矩阵 的乘积的乘积是一个是一个 矩阵矩阵 ，其中，其中4 4、矩阵与矩阵相乘、矩

37、阵与矩阵相乘设设例例解解求求注意只有当注意只有当第一个矩阵的列数第一个矩阵的列数第一个矩阵的列数第一个矩阵的列数等于等于第二个矩阵第二个矩阵的行数的行数时，两个矩阵才能相乘时，两个矩阵才能相乘.例如例如不存在不存在.矩阵乘法的矩阵乘法的运算规律运算规律（其中（其中 为数）为数）;若若A A是是 阶矩阵，则阶矩阵，则 为为A A的的 次幂，即次幂，即 并且并且 满足满足结合律、分配率结合律、分配率矩阵不满足交换律矩阵不满足交换律例例 设设则则 （并非所有的矩阵都不满足交换律）（并非所有的矩阵都不满足交换律）矩阵是否满足交换律？矩阵是否满足交换律？矩阵乘法不满足消去律矩阵乘法不满足消去律矩阵乘法是

38、否满足消去律？矩阵乘法是否满足消去律？例：例：有有但是但是 输入矩阵的方法输入矩阵的方法(1)(1)用中括号用中括号 把所有矩阵元素括起来；把所有矩阵元素括起来；(2)(2)同一行的不同元素之间用空格或逗号间隔；同一行的不同元素之间用空格或逗号间隔；(3)(3)用分号用分号(;)(;)指定一行结束；指定一行结束；(4)(4)也可以分成几行进行输入，用回车符代替分号；也可以分成几行进行输入，用回车符代替分号；(5)(5)数据元素可以是表达式，系统将自动计算结果；数据元素可以是表达式，系统将自动计算结果；例：输入矩阵例：输入矩阵matlab输入格式：输入格式：ans=-39-1137ans=3特殊

39、矩阵函数特殊矩阵函数函数函数描述描述举例举例空矩阵空矩阵A(:,2)=%删除矩阵删除矩阵A的第的第2列列eye单位矩阵单位矩阵A=eye(3)ones元素全部为元素全部为1的矩阵的矩阵A=ones(2,3)%A为为23元素全为元素全为1的矩阵的矩阵zeros元素全部为元素全部为0的矩阵的矩阵A=zeros(2,3)%A为为23元素全为元素全为0的矩阵的矩阵rand元素值为元素值为0到到1之间之间均匀分布的随机矩阵均匀分布的随机矩阵A=rand(3)函数函数描述描述举例举例randn元素值服从均值为元素值服从均值为0方差为方差为1的正态分布的随机矩阵的正态分布的随机矩阵A=randn(4)tri

40、u求给定矩阵的上三角阵求给定矩阵的上三角阵B=triu(A)tril求给定矩阵的下三角阵求给定矩阵的下三角阵B=tril(A)矩阵的基本运算矩阵的基本运算运算运算功能功能命令形式命令形式矩阵矩阵加法和减法加法和减法将两个同型矩阵相加将两个同型矩阵相加(减减)ABAB数乘数乘将数与矩阵做乘法将数与矩阵做乘法k*Ak*Ak k是一个数是一个数,A,A是一个矩阵是一个矩阵矩阵矩阵乘法乘法将两个矩阵进行矩阵相乘将两个矩阵进行矩阵相乘A*BA*BA A的列数与的列数与B B的行数相等的行数相等矩阵的矩阵的左除左除计算ABABA A必须为方阵必须为方阵矩阵的矩阵的右除右除计算A/BA/BB B必须为方阵必

41、须为方阵求矩阵求矩阵行列式行列式计算方阵的行列式计算方阵的行列式det(A)det(A)A A必须为方阵必须为方阵矩阵的基本运算矩阵的基本运算运算运算功能功能命令形式命令形式求矩阵的求矩阵的逆逆求方阵的逆求方阵的逆Inv(A)Inv(A)或或矩阵矩阵乘幂乘幂计算AnA An nA A必须为方阵必须为方阵,n,n是正整数是正整数矩阵的矩阵的转置转置求矩阵的转置求矩阵的转置Transpose(A)Transpose(A)或或AA矩阵矩阵求秩求秩求矩阵的秩求矩阵的秩rank(A)rank(A)矩阵矩阵行变换化简行变换化简求求A A阶梯形的行最简形式阶梯形的行最简形式rref(A)rref(A)一、图

42、与网络的基本概念一、图与网络的基本概念是由一个非空有限集合是由一个非空有限集合和和中某些元素的中某些元素的无无序对序对集合集合构成的二元组，记为构成的二元组，记为。顶点集或节点集顶点集或节点集边集边集Vertex，edge完备图完备图若若表示表示集合中的元素个数），集合中的元素个数），中无相邻顶点对，中无相邻顶点对，中亦然，中亦然，则称则称为为二分图二分图；特别地，若；特别地，若则则，则称，则称为为完全二分图完全二分图，记成，记成。简而言之，就是顶点集简而言之，就是顶点集V V可分割为两个互不相可分割为两个互不相交的子集，并且图中每条边依附的两个顶点都分交的子集，并且图中每条边依附的两个顶点都

43、分属于这两个互不相交的子集。属于这两个互不相交的子集。图中图中(a),(b)为二分图，为二分图，(c)为完全二分图为完全二分图K3,3树树最小生成树：最小生成树：二、图与网络的数据结构二、图与网络的数据结构（每边有两个顶点与其相关联）（每边有两个顶点与其相关联）1 5 3 4 6 7三、最短距离问题三、最短距离问题 在生产管理、交通运输和通讯领域，经常会碰在生产管理、交通运输和通讯领域，经常会碰到这样的问题：沿着哪条路线可以最短的时间或最到这样的问题：沿着哪条路线可以最短的时间或最少的费用把货物运往目的地？沿着哪条路线传送信少的费用把货物运往目的地？沿着哪条路线传送信息最可靠或最快捷？如何组织

44、生产可使生产成本最息最可靠或最快捷？如何组织生产可使生产成本最低？如何制定投资计划可使利润最大？这些都可看低？如何制定投资计划可使利润最大？这些都可看成是在给定的加权图中，求最短路径问题成是在给定的加权图中，求最短路径问题 。邻邻接接矩矩阵阵 2v1v3v4v5v6570805020310030 2v1v3v4v5v6570805020310030例例某公司在六个城市中有分公司，从到的直接航程票价某公司在六个城市中有分公司，从到的直接航程票价记在下述矩阵的位置上。（表示无直接航路），请帮助该记在下述矩阵的位置上。（表示无直接航路），请帮助该公司设计一张城市到其它城市间的票价最便宜的路线图。公司

45、设计一张城市到其它城市间的票价最便宜的路线图。行行 遍遍 性性 问问 题题一、中一、中 国国 邮邮 递递 员员 问问 题题二、推二、推 销销 员员 问问 题题（一）（一）欧欧 拉拉 图图（二）（二）中中 国国 邮邮 递递 员员 问问 题题（一）（一）哈哈 密密 尔尔 顿顿 图图（二）（二）推推 销销 员员 问问 题题e3v1v2v3v4e1e2e4e5e6欧欧 拉拉 图图e3v1v2v3v4e1e2e4e5巡回：v1e1v2e2v3e5v1e4v4e3v3e5v1欧拉道路：v1e1v2e2v3e5v1e4v4e3v3欧拉巡回：v1e1v2e2v3e5v1e4v4e3v3e6v1e3v1v2v3

46、v4e1e2e4e5e3v1v2v3v4e1e2e4e5e6欧拉图非欧拉图 推论推论1 1 设设G G是非平凡连通图，则是非平凡连通图，则G G有欧拉道路的充要条有欧拉道路的充要条件是件是G G最多有两个奇次顶点最多有两个奇次顶点.该推论为判别图形能否一笔画给出了依据该推论为判别图形能否一笔画给出了依据中国邮递员问题中国邮递员问题-定义定义 邮递员发送邮件时，要从邮局出发，经过他投递邮递员发送邮件时，要从邮局出发，经过他投递范围内的每条街道至少一次，然后返回邮局，但邮递范围内的每条街道至少一次，然后返回邮局，但邮递员希望选择一条行程最短的路线。这就是员希望选择一条行程最短的路线。这就是中国邮递

47、员中国邮递员问题问题。若将若将投递区的街道用边表示，街道的长度用边权表投递区的街道用边表示，街道的长度用边权表示，邮局街道交叉口用点表示，则一个投递区构成一示，邮局街道交叉口用点表示，则一个投递区构成一个赋权连通无向图个赋权连通无向图.中国邮递员问题转化为：中国邮递员问题转化为：在一个非负加权连通图中，在一个非负加权连通图中，寻求一个权最小的巡回这样的巡回称为寻求一个权最小的巡回这样的巡回称为最佳巡回最佳巡回（管梅谷（管梅谷1962年）年）一笔画问题一笔画问题V7e3v1v2v3v4e1e2e4e5V5V6e6e7e8e9割边 割边的定义割边的定义：设G连通，e E(G),若从G中删除边e后，

48、图G-e不连通，则称边e为图G的割边G的边e为割边割边e 不含在G的圈中圈圈：起点与终点重合的：起点与终点重合的路径路径顶点、边均不重复的通路顶点、边均不重复的通路中国邮递员问题中国邮递员问题-算法算法Fleury算法算法-基本思想基本思想：从任一点出发，每当访问从任一点出发，每当访问一条边时，先要进行检查如果可供访问的边不只一条边时，先要进行检查如果可供访问的边不只一条，则应选一条不是未访问的边集的导出子图的一条，则应选一条不是未访问的边集的导出子图的割边割边作为访问边，直到没有边可选择为止作为访问边，直到没有边可选择为止.此时此时G的任何一个欧拉巡回便是最佳巡回问题的任何一个欧拉巡回便是最

49、佳巡回问题归结为在欧拉图中确定一个欧拉巡回归结为在欧拉图中确定一个欧拉巡回1.G1.G是欧拉图是欧拉图V7e3v1v2v3v4e1e2e4e5V5V6e6e7e8e9e10 若若G不是欧拉图，则不是欧拉图，则G的任何一个巡回经过某些边的任何一个巡回经过某些边必定多于一次必定多于一次解决这类问题的一般方法是，在一些点对之间解决这类问题的一般方法是，在一些点对之间引入重复边（重复边与它平行的边具有相同的权），引入重复边（重复边与它平行的边具有相同的权），使原图成为欧拉图，但希望所有添加的重复边的使原图成为欧拉图，但希望所有添加的重复边的权的总和为最小权的总和为最小e3v1v2v3v4e1e2e4e

50、52.G2.G不是欧拉图不是欧拉图V7e3v1v2v3v4e1e2e4e5V5V6e6e7e8e9先将奇次顶点配对，要求最佳配对，即点对之间先将奇次顶点配对，要求最佳配对，即点对之间距离总和最小再沿点对之间的最短路径添加重复边距离总和最小再沿点对之间的最短路径添加重复边得欧拉图得欧拉图G*，G*的欧拉巡回便是原图的最佳巡回的欧拉巡回便是原图的最佳巡回基本思想基本思想：（3）求出）求出G1的的最小权理想匹配最小权理想匹配M，得到奇次顶点的最佳配对，得到奇次顶点的最佳配对（2）以）以G的所有奇次顶点为顶点集（个数为偶数），作一的所有奇次顶点为顶点集（个数为偶数），作一完备图，边上的权为两端点在原图