数学建模离散模型培训学习教案.pptx

《数学建模离散模型培训学习教案.pptx》由会员分享，可在线阅读，更多相关《数学建模离散模型培训学习教案.pptx（94页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数学数学(shxu)建模离散模型培训建模离散模型培训第一页，共94页。参考书数学(shxu)模型姜启源谢金星等著高等教育出版社任何数学(shxu)建模方面的书计算机语言方面的书(matlab,mathematica,lindogo）第1页/共94页第二页，共94页。数学(shxu)建模的历史1988.61988.6叶其孝教授在美国讲学期间向美国大学生数学叶其孝教授在美国讲学期间向美国大学生数学建模竞赛发起者和负责人建模竞赛发起者和负责人FusaroFusaro教授了解这项竞赛的情教授了解这项竞赛的情况，商讨况，商讨(shngto)(shngto)中国学生参赛的办法和规则。中国学生参赛的办法和规

2、则。1989.2.241989.2.242626我国大学生（北京大学、清华大学、我国大学生（北京大学、清华大学、北京理工大学共北京理工大学共4 4个队）首次参加美国大学生数学建模竞个队）首次参加美国大学生数学建模竞赛，自此每年我国都有同学参加这项竞赛。赛，自此每年我国都有同学参加这项竞赛。1989.31989.3高校应用数学学报第高校应用数学学报第4 4卷第卷第1 1期发表叶其孝期发表叶其孝教授的文章教授的文章“美国大学生数学建模竞赛及一些想法美国大学生数学建模竞赛及一些想法”，第一，第一次向国内介绍这项竞赛。次向国内介绍这项竞赛。1990.6.221990.6.227.17.1美国美国Fus

3、aroFusaro教授访问北京和上教授访问北京和上海，作了有关美国大学生数学建模竞赛的报告，并与叶海，作了有关美国大学生数学建模竞赛的报告，并与叶其孝、姜启源等讨论数学建模竞赛的组织工作。其孝、姜启源等讨论数学建模竞赛的组织工作。第2页/共94页第三页，共94页。1990.12.71990.12.799上海市举办大学生（数学类）数学模型竞赛，这是我国省、上海市举办大学生（数学类）数学模型竞赛，这是我国省、市级首次举办数学建模竞赛。市级首次举办数学建模竞赛。1991.8.201991.8.202222第三届全国数学建模教学及应用会议在湖南张家界举行，第三届全国数学建模教学及应用会议在湖南张家界举

4、行，对举办全国性竞赛起了组织作用。（第一、二届会议分别于对举办全国性竞赛起了组织作用。（第一、二届会议分别于19861986、19881988年举行。）年举行。）1991.11.231991.11.232424中国工业与应用数学学会第一届第三次常务理事会决定成中国工业与应用数学学会第一届第三次常务理事会决定成立数学模型专业委员会，俞文？为主任，姜启源、叶其孝、谭永基为副主任，并责立数学模型专业委员会，俞文？为主任，姜启源、叶其孝、谭永基为副主任，并责成他们组织成他们组织19921992年部分城市大学生数学模型联赛年部分城市大学生数学模型联赛(linsi)(linsi)。这个委员会实际上成为。这

5、个委员会实际上成为我国大学生数学建模竞赛的主要组织者。我国大学生数学建模竞赛的主要组织者。1992.11.271992.11.27291992291992年部分城市大学生数学模型联赛年部分城市大学生数学模型联赛(linsi)(linsi)举行，这是举行，这是全国性的首届竞赛，全国性的首届竞赛，1010省（市）省（市）7979所院校的所院校的314314队参加。队参加。第3页/共94页第四页，共94页。模型模型(mxng):为了一定目的，对客观事物的一部分为了一定目的，对客观事物的一部分进行简缩、抽象、提炼出来的原型的替代物进行简缩、抽象、提炼出来的原型的替代物.集中反映了原型中人们需要的那一部

6、分特征集中反映了原型中人们需要的那一部分特征什么什么(shnme)是数学模型是数学模型数学模型定义数学模型定义:对于一个现实对象，为了一个特定对于一个现实对象，为了一个特定目的，根据其内在规律，作出必要的简化假设，目的，根据其内在规律，作出必要的简化假设，运用适当的数学工具运用适当的数学工具(gngj)(gngj)，得到的一个数学结构。，得到的一个数学结构。数学建模数学建模:建立数学模型的全过程（包括表建立数学模型的全过程（包括表述、求解、解释、检验等）述、求解、解释、检验等）第4页/共94页第五页，共94页。数学建模的基本数学建模的基本(jbn)(jbn)方法方法机理机理(j l)(j l)

7、分析分析测试测试(csh)(csh)分析分析根据对客观事物特性的认识，找出反映根据对客观事物特性的认识，找出反映内部机理的数量规律内部机理的数量规律将对象看作将对象看作“黑箱黑箱”,通过对量测数据的通过对量测数据的统计分析，找出与数据拟合最好的模型统计分析，找出与数据拟合最好的模型机理分析没有统一的方法，主要通过实例研究机理分析没有统一的方法，主要通过实例研究 (CaseStudies)来学习。以下建模主要指机理分析。来学习。以下建模主要指机理分析。二者结合二者结合用机理分析建立模型结构用机理分析建立模型结构,用测试分析确用测试分析确定模型参数定模型参数 数学建模的方法和步骤数学建模的方法和步

8、骤 数学建模的重要意义数学建模的重要意义数学建模的具体应用数学建模的具体应用第5页/共94页第六页，共94页。数学数学(shxu)(shxu)建模的一般步骤建模的一般步骤模型准备模型准备模型假设模型假设模型构成模型构成模型求解模型求解模型分析模型分析模型检验模型检验模型应用模型应用模模型型准准备备了解实际了解实际(shj)(shj)背景背景明确明确(mngqu)(mngqu)建模目的建模目的搜集有关信息搜集有关信息掌握对象特征掌握对象特征形成一个形成一个比较清晰比较清晰的的问题问题第6页/共94页第七页，共94页。模模型型假假设设针对针对(zhndu)问题特点和建模目的问题特点和建模目的作出合

9、理作出合理(hl)的、简化的假设的、简化的假设在合理在合理(hl)与简化之间作出折中与简化之间作出折中模模型型构构成成用数学的语言、符号描述问题用数学的语言、符号描述问题发挥想像力发挥想像力使用类比法使用类比法尽量采用简单的数学工具尽量采用简单的数学工具 数学建模的一般步骤数学建模的一般步骤第7页/共94页第八页，共94页。模型模型(mxng)求解求解各种数学方法各种数学方法(shxufnf)、软件和计算机技术、软件和计算机技术如结果如结果(jigu)的误差分析、统计分析、的误差分析、统计分析、模型对数据的稳定性分析模型对数据的稳定性分析模型模型分析分析模型模型检验检验与实际现象、数据比较，与

10、实际现象、数据比较，检验模型的合理性、适用性检验模型的合理性、适用性模型应用模型应用 数学建模的一般步骤数学建模的一般步骤第8页/共94页第九页，共94页。数学数学(shxu)建模的全建模的全过程过程现实对象的信息现实对象的信息数学模型数学模型现实对象的解答现实对象的解答数学模型的解答数学模型的解答表述表述求解求解解释解释验证验证(归纳)(演绎)现现实实世世界界数数学学世世界界表述表述求解求解解释解释验证验证根据建模目的和信息将实际问题根据建模目的和信息将实际问题“翻译翻译”成数学问题成数学问题选择适当的数学方法求得数学模型的解答选择适当的数学方法求得数学模型的解答将数学语言表述的解答将数学语

11、言表述的解答“翻译翻译”回实际对象回实际对象用现实对象的信息检验得到的解答用现实对象的信息检验得到的解答实践理论实践第9页/共94页第十页，共94页。模型模型(mxng)的逼真性和可行性的逼真性和可行性模型模型(mxng)的渐进性的渐进性模型模型(mxng)的强健性的强健性模型的可转移性模型的可转移性模型的非预制性模型的非预制性模型的条理性模型的条理性模型的技艺性模型的技艺性模型的局限性模型的局限性数学模型的特点数学模型的特点第10页/共94页第十一页，共94页。数学数学(shxu)(shxu)建模能力的培养建模能力的培养数学建模与其说是一门数学建模与其说是一门(ymn)技术，不如说是一门技术

12、，不如说是一门(ymn)艺术艺术技术技术(jsh)大致有章可循大致有章可循艺术无法归纳成普遍适用的准则艺术无法归纳成普遍适用的准则想像力想像力洞察力洞察力判断力判断力 学习、分析、评价、改进别人作过的模型学习、分析、评价、改进别人作过的模型 亲自动手，认真作几个实际题目亲自动手，认真作几个实际题目 *也是一种创新能力的培养也是一种创新能力的培养 第11页/共94页第十二页，共94页。*没有没有(mi yu)(mi yu)创新，就没有创新，就没有(mi yu)(mi yu)发展，创新促进人类发展，创新促进人类社会的进步社会的进步.*正处于传统的继承性教育正处于传统的继承性教育(jioy)向创新性

13、向创新性教育教育(jioy)转变的时期转变的时期.重要的科学重要的科学(kxu)思维方式之一是创新思维，思维方式之一是创新思维，创新思维是创新能力的核心与灵魂创新思维是创新能力的核心与灵魂.创新能力的培养创新能力的培养 第12页/共94页第十三页，共94页。图与网络图与网络图与网络图与网络(wnglu)(wnglu)模型模型模型模型数学建模中的图论方法数学建模中的图论方法1.图论的起源图论的起源 图论起源于图论起源于18世纪。第一篇图论论文是瑞士数学家欧拉于世纪。第一篇图论论文是瑞士数学家欧拉于1736 年年发表的发表的“哥尼斯堡的七座桥哥尼斯堡的七座桥”。1847年，克希霍夫为了给出电网络方

14、程年，克希霍夫为了给出电网络方程而引进了而引进了“树树”的概念。的概念。1857年，凯莱在计数烷的同分异构物时，也发年，凯莱在计数烷的同分异构物时，也发现现(fxin)了了“树树”。哈密尔顿于。哈密尔顿于1859年提出年提出“周游世界周游世界”游戏，用图游戏，用图论的术语，就是如何找出一个连通图中的生成圈，近几十年来，由于计论的术语，就是如何找出一个连通图中的生成圈，近几十年来，由于计算机技术和科学的飞速发展，大大地促进了图论研究和应用，图论的理算机技术和科学的飞速发展，大大地促进了图论研究和应用，图论的理论和方法已经渗透到物理、化学、通讯科学、建筑学、生物遗传学、心论和方法已经渗透到物理、化

15、学、通讯科学、建筑学、生物遗传学、心理学、经济学、社会学等学科中。理学、经济学、社会学等学科中。第13页/共94页第十四页，共94页。图论中所谓的图论中所谓的“图图”是指某类具体事物和这些事物之间的联是指某类具体事物和这些事物之间的联系。如果我们用点表示这些具体事物，用连接两点的线段（直系。如果我们用点表示这些具体事物，用连接两点的线段（直的或曲的）表示两个事物的特定的联系，就得到了描述这个的或曲的）表示两个事物的特定的联系，就得到了描述这个“图图”的几何形象。图论为任何一个包含了一种二元关系的离散系统的几何形象。图论为任何一个包含了一种二元关系的离散系统提供了一个数学模型，借助于图论的概念、

16、理论和方法，可以提供了一个数学模型，借助于图论的概念、理论和方法，可以对该模型求解。哥尼斯堡七桥问题就是对该模型求解。哥尼斯堡七桥问题就是(jish)一个典型的例子。一个典型的例子。在哥尼斯堡有七座桥将普莱格尔河中的两个岛及岛与河岸联结在哥尼斯堡有七座桥将普莱格尔河中的两个岛及岛与河岸联结起来问题是要从这四块陆地中的任何一块开始通过每一座桥正起来问题是要从这四块陆地中的任何一块开始通过每一座桥正好一次，再回到起点。好一次，再回到起点。第14页/共94页第十五页，共94页。当然可以通过试验去尝试解决这个问题，但该城居民的当然可以通过试验去尝试解决这个问题，但该城居民的任何尝试均未成功。欧拉为了解

17、决这个问题，采用了建立任何尝试均未成功。欧拉为了解决这个问题，采用了建立(jinl)数学模型的方法。他将每一块陆地用一个点来代替，数学模型的方法。他将每一块陆地用一个点来代替，将每一座桥用连接相应两点的一条线来代替，从而得到一个将每一座桥用连接相应两点的一条线来代替，从而得到一个有四个有四个“点点”，七条，七条“线线”的的“图图”。问题成为从任一点出发一笔。问题成为从任一点出发一笔画出七条线再回到起点。欧拉考察了一般一笔画的结构特点，画出七条线再回到起点。欧拉考察了一般一笔画的结构特点，给出了一笔画的一个判定法则：这个图是连通的，且每个点给出了一笔画的一个判定法则：这个图是连通的，且每个点都与

18、偶数线相关联，将这个判定法则应用于七桥问题，得到都与偶数线相关联，将这个判定法则应用于七桥问题，得到了了“不可能走通不可能走通”的结果，不但彻底解决了这个问题，而且开的结果，不但彻底解决了这个问题，而且开创了图论研究的先河。最短路问题、最大流问题、最小费用创了图论研究的先河。最短路问题、最大流问题、最小费用流问题和匹配问题等都是图与网络的基本问题流问题和匹配问题等都是图与网络的基本问题第15页/共94页第十六页，共94页。2.2.问题（通过一些例子来了解图解决问题（通过一些例子来了解图解决问题（通过一些例子来了解图解决问题（通过一些例子来了解图解决(jiju)(jiju)的问题）的问题）的问题

19、）的问题）问题一：问题一：问题一：问题一：最短路问题（最短路问题（最短路问题（最短路问题（SPPSPPshortest path problemshortest path problem）一名货柜车司机奉命在最短的时间内将一车货物从甲地运往一名货柜车司机奉命在最短的时间内将一车货物从甲地运往一名货柜车司机奉命在最短的时间内将一车货物从甲地运往一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地。从甲地到乙地的公路网纵横交错，因此有多种行车路乙地。从甲地到乙地的公路网纵横交错，因此有多种行车路乙地。从甲地到乙地的公路网纵横交错，因此有多种行车路乙地。从甲地到乙地的公路网纵横交错，因此有多种行

20、车路线，这名司机应选择哪条线路呢？假设货柜车的运行速度是线，这名司机应选择哪条线路呢？假设货柜车的运行速度是线，这名司机应选择哪条线路呢？假设货柜车的运行速度是线，这名司机应选择哪条线路呢？假设货柜车的运行速度是恒定的，那么这一问题相当于需要找到一条从甲地到乙地的恒定的，那么这一问题相当于需要找到一条从甲地到乙地的恒定的，那么这一问题相当于需要找到一条从甲地到乙地的恒定的，那么这一问题相当于需要找到一条从甲地到乙地的最短路。最短路。最短路。最短路。问题二：问题二：问题二：问题二：公路连接问题公路连接问题公路连接问题公路连接问题某一地区有若干个主要城市，现准备修建高速公路把这些城某一地区有若干个

21、主要城市，现准备修建高速公路把这些城某一地区有若干个主要城市，现准备修建高速公路把这些城某一地区有若干个主要城市，现准备修建高速公路把这些城市连接起来，使得从其中任何一个城市都可以经高速公路直市连接起来，使得从其中任何一个城市都可以经高速公路直市连接起来，使得从其中任何一个城市都可以经高速公路直市连接起来，使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市。假定已经知道了任意两个城市之接或间接到达另一个城市。假定已经知道了任意两个城市之接或间接到达另一个城市。假定已经知道了任意两个城市之接或间接到达另一个城市。假定已经知道了任意两个城市之间修建高速公路的成本，那么应如何决定在哪些城

22、市间修建间修建高速公路的成本，那么应如何决定在哪些城市间修建间修建高速公路的成本，那么应如何决定在哪些城市间修建间修建高速公路的成本，那么应如何决定在哪些城市间修建高速公路，使得总成本最小？高速公路，使得总成本最小？高速公路，使得总成本最小？高速公路，使得总成本最小？第16页/共94页第十七页，共94页。问题三：问题三：问题三：问题三：指派问题（指派问题（指派问题（指派问题（assignment problemassignment problem）一家公司经理准备安排名员工去完成项任务，每人一项。由于各员工的特一家公司经理准备安排名员工去完成项任务，每人一项。由于各员工的特一家公司经理准备安排

23、名员工去完成项任务，每人一项。由于各员工的特一家公司经理准备安排名员工去完成项任务，每人一项。由于各员工的特点不同，不同的员工去完成同一项任务时所获得的回报是不同的。如何分点不同，不同的员工去完成同一项任务时所获得的回报是不同的。如何分点不同，不同的员工去完成同一项任务时所获得的回报是不同的。如何分点不同，不同的员工去完成同一项任务时所获得的回报是不同的。如何分配工作方案可以使总回报最大？配工作方案可以使总回报最大？配工作方案可以使总回报最大？配工作方案可以使总回报最大？问题四：问题四：问题四：问题四：中国邮递员问题（中国邮递员问题（中国邮递员问题（中国邮递员问题（CPPCPPchinese

24、postman problemchinese postman problem）一名邮递员负责投递某个街区的邮件。如何为他（她）设计一名邮递员负责投递某个街区的邮件。如何为他（她）设计一名邮递员负责投递某个街区的邮件。如何为他（她）设计一名邮递员负责投递某个街区的邮件。如何为他（她）设计(shj)(shj)一条最一条最一条最一条最短的投递路线（从邮局出发，经过投递区内每条街道至少一次，最后返回短的投递路线（从邮局出发，经过投递区内每条街道至少一次，最后返回短的投递路线（从邮局出发，经过投递区内每条街道至少一次，最后返回短的投递路线（从邮局出发，经过投递区内每条街道至少一次，最后返回邮局）？由于这

25、一问题是我国管梅谷教授邮局）？由于这一问题是我国管梅谷教授邮局）？由于这一问题是我国管梅谷教授邮局）？由于这一问题是我国管梅谷教授19601960年首先提出的，所以国际上年首先提出的，所以国际上年首先提出的，所以国际上年首先提出的，所以国际上称之为中国邮递员问题。称之为中国邮递员问题。称之为中国邮递员问题。称之为中国邮递员问题。第17页/共94页第十八页，共94页。问题五：问题五：问题五：问题五：旅行商问题（旅行商问题（旅行商问题（旅行商问题（TSPTSPtraveling salesman problemtraveling salesman problem）一名推销员准备前往若干城市推销产品

26、。如何为他（她）设计一一名推销员准备前往若干城市推销产品。如何为他（她）设计一一名推销员准备前往若干城市推销产品。如何为他（她）设计一一名推销员准备前往若干城市推销产品。如何为他（她）设计一条最短的旅行路线（从驻地出发，经过每个城市恰好一次，最后条最短的旅行路线（从驻地出发，经过每个城市恰好一次，最后条最短的旅行路线（从驻地出发，经过每个城市恰好一次，最后条最短的旅行路线（从驻地出发，经过每个城市恰好一次，最后返回驻地）？这一问题的研究历史十分悠久，通常称之为旅行商返回驻地）？这一问题的研究历史十分悠久，通常称之为旅行商返回驻地）？这一问题的研究历史十分悠久，通常称之为旅行商返回驻地）？这一问

27、题的研究历史十分悠久，通常称之为旅行商问题。问题。问题。问题。问题六：问题六：问题六：问题六：运输问题（运输问题（运输问题（运输问题（transportation problemtransportation problem）某种原材料有个产地，现在需要将原材料从产地运往个使用这些某种原材料有个产地，现在需要将原材料从产地运往个使用这些某种原材料有个产地，现在需要将原材料从产地运往个使用这些某种原材料有个产地，现在需要将原材料从产地运往个使用这些原材料的工厂。假定个产地的产量和家工厂的需要量已知，单位原材料的工厂。假定个产地的产量和家工厂的需要量已知，单位原材料的工厂。假定个产地的产量和家工厂的

28、需要量已知，单位原材料的工厂。假定个产地的产量和家工厂的需要量已知，单位(dnwi)(dnwi)产品从任一产地到任一工厂的运费已知，那么如何安排产品从任一产地到任一工厂的运费已知，那么如何安排产品从任一产地到任一工厂的运费已知，那么如何安排产品从任一产地到任一工厂的运费已知，那么如何安排运输方案可以使总运输成本最低？运输方案可以使总运输成本最低？运输方案可以使总运输成本最低？运输方案可以使总运输成本最低？第18页/共94页第十九页，共94页。上述问题有两个共同的特点：一是它们的目的都是从若干可能上述问题有两个共同的特点：一是它们的目的都是从若干可能上述问题有两个共同的特点：一是它们的目的都是从

29、若干可能上述问题有两个共同的特点：一是它们的目的都是从若干可能(knng)(knng)的安排或方案中寻求某种意义下的最优安排或方案，的安排或方案中寻求某种意义下的最优安排或方案，的安排或方案中寻求某种意义下的最优安排或方案，的安排或方案中寻求某种意义下的最优安排或方案，数学上把这种问题称为最优化或优化（数学上把这种问题称为最优化或优化（数学上把这种问题称为最优化或优化（数学上把这种问题称为最优化或优化（optimizationoptimization）问题；）问题；）问题；）问题；二是它们都易于用图形的形式直观地描述和表达，数学上把这二是它们都易于用图形的形式直观地描述和表达，数学上把这二是它

30、们都易于用图形的形式直观地描述和表达，数学上把这二是它们都易于用图形的形式直观地描述和表达，数学上把这种与图相关的结构称为网络（种与图相关的结构称为网络（种与图相关的结构称为网络（种与图相关的结构称为网络（networknetwork）。与图和网络相关的）。与图和网络相关的）。与图和网络相关的）。与图和网络相关的最优化问题就是网络最优化或称网络优化最优化问题就是网络最优化或称网络优化最优化问题就是网络最优化或称网络优化最优化问题就是网络最优化或称网络优化 （netwok netwok optimizationoptimization）问题。所以上面例子中介绍的问题都是网络优）问题。所以上面例子

31、中介绍的问题都是网络优）问题。所以上面例子中介绍的问题都是网络优）问题。所以上面例子中介绍的问题都是网络优化问题。由于多数网络优化问题是以网络上的流（化问题。由于多数网络优化问题是以网络上的流（化问题。由于多数网络优化问题是以网络上的流（化问题。由于多数网络优化问题是以网络上的流（flowflow）为研）为研）为研）为研究的对象，因此网络优化又常常被称为网络流（究的对象，因此网络优化又常常被称为网络流（究的对象，因此网络优化又常常被称为网络流（究的对象，因此网络优化又常常被称为网络流（network network flowsflows）或网络流规划等。）或网络流规划等。）或网络流规划等。）或

32、网络流规划等。第19页/共94页第二十页，共94页。3.3.图论的基本概念图论的基本概念 图定义：图定义：图是由顶点集合图是由顶点集合(vertex)(vertex)及顶点间的关系集合组成的一种数据结构：及顶点间的关系集合组成的一种数据结构：Graph Graph(V,E)(V,E)其中其中 V=x|x V=x|x 某个数据对象某个数据对象 是顶点的有穷非空集合；是顶点的有穷非空集合；E=(x,y)|x,y E=(x,y)|x,y V V 或或 E=|x,y E=|x,y V&Path(x,y)V&Path(x,y)是顶点之间关系的有穷集合，也叫做边是顶点之间关系的有穷集合，也叫做边(edge

33、)(edge)集合。集合。Path(x,y)Path(x,y)表示从表示从 x x 到到 y y 的一条的一条(y tio)(y tio)单向通路单向通路,它是有方它是有方向的。向的。有向图与无向图：有向图与无向图：在有向图中，顶点对在有向图中，顶点对是有序的。在无向图中，顶点对是有序的。在无向图中，顶点对(x,y)(x,y)是无序的。是无序的。完全图：完全图：若有若有 n n 个顶点的无向图有个顶点的无向图有 n(n-1)/2 n(n-1)/2 条边条边,则此则此第20页/共94页第二十一页，共94页。图为完全无向图。有图为完全无向图。有 n 个顶点的有向图有个顶点的有向图有n(n-1)条边

34、条边,则此图为完全则此图为完全有向图。有向图。邻接顶点：邻接顶点：如果如果(u,v)是是 E(G)中的一条边，则称中的一条边，则称 u 与与 v 互为邻互为邻接顶点。接顶点。若若ek,el至少有一个公共端点至少有一个公共端点,则称则称ek,el 是彼此是彼此(bc)相邻的相邻的,简简称相邻的称相邻的 权：权：某些某些(mu xi)(mu xi)图的边具有与它相关的数图的边具有与它相关的数,称之为权。这种带权图叫做网络。称之为权。这种带权图叫做网络。顶顶点点的的度度：一一个个顶顶点点v v的的度度是是与与它它相相关关联联的的边边的的条条数数。记记作作TD(v)TD(v)。在在有有向向图图中中,顶

35、顶点点的的度等于该顶点的入度与出度之和。度等于该顶点的入度与出度之和。第21页/共94页第二十二页，共94页。顶点顶点 v v 的入度：的入度：以以 v v 为终点的有向边的条数为终点的有向边的条数,记作记作 ID(v);ID(v);顶点顶点 v v 的出度：的出度：以以 v v 为始点的有向边的条数为始点的有向边的条数,记作记作 OD(v)OD(v)。度为奇数的顶点个数为偶数度为奇数的顶点个数为偶数(u sh).(u sh).路径：路径：在图在图 G G(V,E)(V,E)中中,若从顶点若从顶点 vi vi 出发出发,沿一些边经过一些顶点沿一些边经过一些顶点 vp1,vp2,vpm vp1,

36、vp2,vpm，到达顶点到达顶点vjvj。则称顶点序列。则称顶点序列(vi vp1 vp2.vpm vj)(vi vp1 vp2.vpm vj)为从顶点为从顶点vi vi 到顶点到顶点 vj vj 的路径。它经过的路径。它经过的边的边(vi,vp1)(vi,vp1)、(vp1,vp2)(vp1,vp2)、.、(vpm,vj)(vpm,vj)应是属于应是属于E E 的边。的边。第22页/共94页第二十三页，共94页。路径长度：路径长度：非带权图的路径长度是指此路径上边的条数。非带权图的路径长度是指此路径上边的条数。带权图的路径长度是指路径上各边的权之和。带权图的路径长度是指路径上各边的权之和。简

37、单路径：简单路径：若路径上各顶点若路径上各顶点 v1,v2,.,vm v1,v2,.,vm 均不互相重复均不互相重复,则称这样的则称这样的路径为简单路径。路径为简单路径。回路：回路：若路径上第一个顶点若路径上第一个顶点 v1 v1 与最后一个顶点与最后一个顶点vm vm 重合重合,则称这样的路则称这样的路径为回路或环。径为回路或环。连通图与连通分量连通图与连通分量(fn ling)(fn ling)：在无向图中在无向图中,若从顶点若从顶点v1v1到顶点到顶点v2v2有有路径路径,则称顶点则称顶点v1v1与与v2v2是连通的。如果图中任意一对顶点都是连通的是连通的。如果图中任意一对顶点都是连通的

38、,则则称此图是连通图。非连通图的极大连通子图叫做连通分量称此图是连通图。非连通图的极大连通子图叫做连通分量(fn ling)(fn ling)。第23页/共94页第二十四页，共94页。强连通图与强连通分量：强连通图与强连通分量：强连通图与强连通分量：强连通图与强连通分量：在有向图中在有向图中在有向图中在有向图中,若对于每一对顶点若对于每一对顶点若对于每一对顶点若对于每一对顶点(dngdin)vi(dngdin)vi和和和和vj,vj,都存在一条从都存在一条从都存在一条从都存在一条从vivi到到到到vjvj和从和从和从和从vjvj到到到到vivi的路径的路径的路径的路径,则称此则称此则称此则称此

39、图是强连通图。非强连通图的极大强连通子图叫做强连通分量。图是强连通图。非强连通图的极大强连通子图叫做强连通分量。图是强连通图。非强连通图的极大强连通子图叫做强连通分量。图是强连通图。非强连通图的极大强连通子图叫做强连通分量。第24页/共94页第二十五页，共94页。关联：关联：关联：关联：设设设设ekek(vi,vj)(vi,vj)为无向图为无向图为无向图为无向图GG中中中中的一条边的一条边的一条边的一条边,称称称称vi,vjvi,vj为为为为ekek的端点的端点的端点的端点,ek,ek与与与与vivi(或或或或vj)vj)是彼此关联的是彼此关联的是彼此关联的是彼此关联的.无边关联的顶点称为孤立

40、无边关联的顶点称为孤立无边关联的顶点称为孤立无边关联的顶点称为孤立(gl)(gl)点点点点.若若若若一条边所关联的两个顶点重合一条边所关联的两个顶点重合一条边所关联的两个顶点重合一条边所关联的两个顶点重合,则称此则称此则称此则称此边为环边为环边为环边为环.第25页/共94页第二十六页，共94页。ekek与与与与vi(vi(或或或或vj)vj)的关联的关联的关联的关联(gunlin)(gunlin)次次次次数数数数1vivj,2vi vj,0vi(vj)不是(b shi)ek的端点bavV第26页/共94页第二十七页，共94页。关联矩阵关联矩阵对无向图对无向图G，其关联矩阵，其关联矩阵M=(mi

41、j)ve，其中，其中(qzhng)：对有向图对有向图G，其关联矩阵，其关联矩阵M=(mij)ve，其中，其中(qzhng)：第27页/共94页第二十八页，共94页。邻接矩阵邻接矩阵(Adjacency Matrix)(Adjacency Matrix)图的邻接矩阵就是表示各个顶点之间关系的一个矩阵。图的邻接矩阵就是表示各个顶点之间关系的一个矩阵。设图设图 A=(V,E)A=(V,E)是一个有是一个有 n n 个顶点的图，则图的邻接矩阵定义为：个顶点的图，则图的邻接矩阵定义为：无向图的邻接矩阵是对称无向图的邻接矩阵是对称(duchn)(duchn)的，有向图的邻接矩阵可能是不对称的，有向图的邻接

42、矩阵可能是不对称(duchn)(duchn)的。的。在有向图中在有向图中,统计第统计第 i i 行行 1 1 的个数可得顶点的个数可得顶点 i i 的出度，统计第的出度，统计第 j j 行行 1 1 的个数可得顶点的个数可得顶点 j j 的入度。的入度。在无向图中在无向图中,统计第统计第 i i 行行(列列)1)1 的个数可得顶点的个数可得顶点i i 的度。的度。对于网络图（带权图）：对于网络图（带权图）：第28页/共94页第二十九页，共94页。第29页/共94页第三十页，共94页。树的定义：树的定义：树的定义：树的定义：连通而不含回路的无向连通而不含回路的无向连通而不含回路的无向连通而不含回

43、路的无向(w xin)(w xin)图称为无向图称为无向图称为无向图称为无向(w(w xin)xin)树树树树,简称树简称树简称树简称树,常用常用常用常用T T表示树表示树表示树表示树.连通分支数大于等于连通分支数大于等于连通分支数大于等于连通分支数大于等于2,2,且每个连通分支均是树的非连且每个连通分支均是树的非连且每个连通分支均是树的非连且每个连通分支均是树的非连通无向通无向通无向通无向(w xin)(w xin)图称为森林图称为森林图称为森林图称为森林.平凡图称为平凡树平凡图称为平凡树平凡图称为平凡树平凡图称为平凡树.设设设设T T是无向是无向是无向是无向(w xin)(w xin)图图

44、图图GG的子图并且为树，则称的子图并且为树，则称的子图并且为树，则称的子图并且为树，则称T T为为为为GG的树的树的树的树.若若若若T T是是是是GG的树且为生成子图，则称的树且为生成子图，则称的树且为生成子图，则称的树且为生成子图，则称T T是是是是GG的生成的生成的生成的生成树树树树.第30页/共94页第三十一页，共94页。最小生成最小生成(shn chn)树树使用不同的遍历图的方法，可以得到不同的生成树；使用不同的遍历图的方法，可以得到不同的生成树；使用不同的遍历图的方法，可以得到不同的生成树；使用不同的遍历图的方法，可以得到不同的生成树；从不同的顶点出发，也可能得到不同的生成树。从不同

45、的顶点出发，也可能得到不同的生成树。从不同的顶点出发，也可能得到不同的生成树。从不同的顶点出发，也可能得到不同的生成树。按照生成树的定义，按照生成树的定义，按照生成树的定义，按照生成树的定义，n n n n 个顶点的连通网络的生成树有个顶点的连通网络的生成树有个顶点的连通网络的生成树有个顶点的连通网络的生成树有n n n n 个顶点、个顶点、个顶点、个顶点、n-1 n-1 n-1 n-1 条边。条边。条边。条边。构造最小生成树的准则构造最小生成树的准则构造最小生成树的准则构造最小生成树的准则必须必须必须必须(bx)(bx)(bx)(bx)只使用该网络中的边来构造最小生成树；只使用该网络中的边来

46、构造最小生成树；只使用该网络中的边来构造最小生成树；只使用该网络中的边来构造最小生成树；必须必须必须必须(bx)(bx)(bx)(bx)使用且仅使用使用且仅使用使用且仅使用使用且仅使用 n-1 n-1 n-1 n-1 条边来联结网络中的条边来联结网络中的条边来联结网络中的条边来联结网络中的 n n n n 个顶点；个顶点；个顶点；个顶点；不能使用产生回路的边。不能使用产生回路的边。不能使用产生回路的边。不能使用产生回路的边。生成最小树的方法有克鲁斯卡尔算法和普里姆算法生成最小树的方法有克鲁斯卡尔算法和普里姆算法生成最小树的方法有克鲁斯卡尔算法和普里姆算法生成最小树的方法有克鲁斯卡尔算法和普里姆

47、算法 第31页/共94页第三十二页，共94页。普里姆普里姆(Prim)算法算法(sun f)普里姆算法的基本思想：普里姆算法的基本思想：普里姆算法的基本思想：普里姆算法的基本思想：从连通网络从连通网络从连通网络从连通网络 N=V,E N=V,E 中的某一顶点中的某一顶点中的某一顶点中的某一顶点 u0 u0 出发，选出发，选出发，选出发，选择与它关联的具有最小权值的边择与它关联的具有最小权值的边择与它关联的具有最小权值的边择与它关联的具有最小权值的边(u0,v)(u0,v)，将其顶点加入到，将其顶点加入到，将其顶点加入到，将其顶点加入到生成树的顶点集合生成树的顶点集合生成树的顶点集合生成树的顶点

48、集合U U中。中。中。中。以后每一步从一个顶点在以后每一步从一个顶点在以后每一步从一个顶点在以后每一步从一个顶点在U U中，而另一个顶点不在中，而另一个顶点不在中，而另一个顶点不在中，而另一个顶点不在U U中的各条边中选择权值最小的边中的各条边中选择权值最小的边中的各条边中选择权值最小的边中的各条边中选择权值最小的边(u,v),(u,v),把它的顶点加入把它的顶点加入把它的顶点加入把它的顶点加入到集合到集合到集合到集合U U中。如此继续下去，直到网络中的所有中。如此继续下去，直到网络中的所有中。如此继续下去，直到网络中的所有中。如此继续下去，直到网络中的所有(suyu)(suyu)顶点都加入到

49、生成树顶点集合顶点都加入到生成树顶点集合顶点都加入到生成树顶点集合顶点都加入到生成树顶点集合U U中为止。中为止。中为止。中为止。采用邻接矩阵作为图的存储表示。采用邻接矩阵作为图的存储表示。采用邻接矩阵作为图的存储表示。采用邻接矩阵作为图的存储表示。第32页/共94页第三十三页，共94页。用普里姆算法(sunf)构造最小生成树的过程第33页/共94页第三十四页，共94页。prim算法(sun f)如下：，while end第34页/共94页第三十五页，共94页。用用primprim算法求右图的最小生成算法求右图的最小生成(shnchn)(shnchn)树。树。我们用的第一、二、三行分别表示生成

50、我们用的第一、二、三行分别表示生成(shnchn)(shnchn)树边的起点、终点、权集合。树边的起点、终点、权集合。MatlabMatlab程序如下：程序如下：clc;clear;clc;clear;M=1000;M=1000;a(1,2)=50;a(1,3)=60;a(1,2)=50;a(1,3)=60;a(2,4)=65;a(2,5)=40;a(2,4)=65;a(2,5)=40;a(3,4)=52;a(3,7)=45;a(3,4)=52;a(3,7)=45;a(4,5)=50;a(4,6)=30;a(4,7)=42;a(4,5)=50;a(4,6)=30;a(4,7)=42;第35页/