chap 5 系统建模与仿真

第五章建模与仿真第一节系统模型概述第二节系统建模方法第三节线性规划模型第四节系统动力学模型第五节图与网络模型第一节系统模型概述（一）系统模型的定义与特征（二）使用系统模型的必要性（三）系统模型的分类（四）使用系统模型的好处（一）系统模型的定义与特征1.定义

系统模型是一个系统某一方面本质属性的描述，它以某种确定的形式(例如文字、符号、图表、实物、数学公式等)提供关于该系统的知识。系统模型一般不是系统对象本身，而是现实系统的描述、模仿或抽象。系统是复杂的，系统的属性也是多方面的。对于大多数研究目的而言，没有必要考虑系统的全部属性系统模型只是系统某一方面本质属性的描述，本质属性的选取完全取决系统工程研究的目的。对同一个系统根据不同的研究目的，可以建立不同的系统模型。例子同一种模型可以代表多个系统y＝kx(k为常量)几何上：代表一条通过原点的直线；代数上；表示比例关系；设k＝π，x代表直径，则y表示圆周长；设k表示弹簧刚度，x表示伸长量，则y表示弹簧力大小；当k＝a表示加速度，x＝m表示质量，则y表示物体所受外力大小等等。2.特征系统模型反映着实际系统的主要特征，但它又高于实际系统而具有同类问题的共性。一个适用的系统模型应该具有如下三个特征；(1)它是现实系统的抽象或模仿；(2)它是由反映系统本质或特征的主要因素构成的；(3)它集中体现了这些主要因素之间的关系。（二）使用系统模型的必要性人类认识和改造客观世界的研究方法，一般来说主要有三种：实验法、抽象法、模型法。实验法是通过对客观事物本身直接进行科学实验来进行研究的，因此局限性比较大。抽象法是把现实系统抽象为一般的理论概念，然后进行推理和判断，因此这种方法缺乏实体感，过于概念化。模型法是在对现实系统进行抽象的基础上，把它们再现为某种实物的、图画的或数学的模型，然后通过模型来对系统进行分析、对比和研究，最终导出结论。模型法既避免了实验法的局限性，又避免了抽象法的过于概念化，所以它成为现代工程中一种最常用的研究方法。(1)系统开发的需要。在开发一个新系统时，由于此时系统尚未建立，无法直接进行实验，只能通过建造系统模型来对系统的性能进行预测，以实现对系统的分析、优化和评价。(2)经济上的考虑。对大型复杂系统直接进行实验，其成本是十分昂贵的，但是使用系统模型就便宜多了。(3)安全上的考虑。对有些系统(如载人航天飞行器、核电站等)通过直接实验进行分析，往往是很危险的，有时甚至是根本不允许的。必要性(4)时间上的考虑。社会、经济、生态等系统，由于惯性大、反应周期很长，对其直接进行实验要等若干年以后才能看到结果，这是系统分析和评价所不允许的。而使用系统模型进行分析，很快就可得到分析结果。(5)系统模型容易操作，分析结果易于理解。有时对现实系统进行直接实验虽然是允许的，而且也不过分费时、费钱，但此时采用系统模型仍然具有优越性。必要性（三）系统模型的分类分类原则模型种类1按建模材料不同抽象、实物2按与实体的关系形象、类似、数学3按模型表征信息的程度观念性、数学、物理4按模型的构造方法理论、经验、混合5按模型的功能结构、性能、评价、最优化、网络6按与时间的依赖程度静态、动态7按是否描述系统内部特性黑箱、白箱8按模型的应用场合通用、专用9数学模型的分类（1）按变量形式分确定性、随机性、连续型、离散型（2）按变量之间的关系分代数方程、微分方程、概率统计、逻辑一般分为三类：物理模型、文字模型和数学模型（四）使用系统模型的好处(1)是定量分析的基础。在自然科学和工程技术领域里，数量不准将导致质量低劣；在社会科学领域里，没有定量分析会使人心中无数，造成决策失误，引起不必要的混乱；采用数学模型进行定量分析已成为当代自然科学和社会科学进一步发展的共同要求。(2)是系统预测和决策的工具可以利用系统已有的数据建立预测模型，用来预测系统的未来状态，为正确决策提供依据。(3)可变性好，适应性强，分析问题速度快，省时省钱，而且便于使用计算机，因此，它是所有模型中使用最广泛的一种。我们通常所说的系统建模，大多数情况下都是指建立系统的数学模型。好处第二节系统建模方法系统建模是系统工程人员的重要工作之一系统建模既是一种技术，又是一种“艺术”（一）对系统模型的要求

现实性、简明性、标准化1．现实性即在一定程度上能够较好地反映系统的客观实际，应把系统本质的特征和关系反映进去，而把非本质的东西去掉，但又不影响反映本质的真实程度。也就是说，系统模型应有足够的精度。精度要求不仅与研究对象有关，而且与所处的时间、状态和条件有关。因此，为满足现实性要求，对同一对象在不同情况下可以提出不同的精度要求。2．简明性在满足现实性要求的基础上，应尽量使系统模型简单明了，以节约建模的费用和时间这也就是说，如果一个简单的模型已能使实际问题得到满意的解答，就没有必要去建一个复杂的模型，因为建造一个复杂的模型并求解是要付出很高代价的。

3．标准化在建立某些系统的模型时，如果已有某种标准化模型可供借鉴，则应尽量采用标准化模型；或对标准化模型加以某些修改，使之适合对象系统。

以上三条要求往往是相互抵触的，容易顾此失彼例如，现实性和简明性就常常存在矛盾，如果模型复杂一些，虽然满足现实性要求．但建模和求解却相当闲难，费时、费钱，同时也可能影响标准化的要求为此，必须根据对象系统的主体情况妥善处理。一般的处理原则是：力求达到现实性，在现实性的基础上达到简明性，然后尽可能满足标准化。（二）系统建模应遵循的原则根据对系统模型提出的三条要求，可以导出系统建模时应该遵循的四项原则是：切题清晰精度要求适当尽量使用标准模型1．切题模型只应包括与研究目的有关的方面，而不是对象系统的所有方面。例如，对一个空运指挥调度系统的研究，建模只需考虑飞机的飞行航向而无需考虑其飞行姿态。2．清晰一个大型复杂系统是由许多联系密切的子系统组成的，因此对应的系统模型也是由许多子模型(或模块)组成的。在子模型与子模型之间，除了保留研究目的所必要的信息联系外，其它的辐合关系要尽可能减少，以保证模型结构尽可能清晰3．精度要求适当建立系统模型，应该视研究目的和使用环境不同，选择适当的精度等级，以保证模型切题、实用，而又不致花费太多。例如，一个受外力F作用下的物体M，其动力学系统的数学模型，在不同使用环境下有不同精度等级，应该适当选择。（1）当物体的运动速度。足够小时，可以忽略空气阻力的影响，其符合精度要求的数学模型为（2）当速度v提高到必须考虑空气阻力的影响时，则其符合精度要求的数学模型为：（3）当物体的运动速度接近于光速3×108m/s时，按相对论原理，此时M将不是常数，因此其符合精度要求的数学模型为:4．尽量使用标准模型在建立一个实际系统的模型时，应该首先大量调阅模型库中的标准模型，如果其中某些可供借鉴，不妨先试用一下如能满足要求，就应该使用标准模型，或者尽可能向标准模型靠拢。（三）系统建模的主要方法主要有5种方法：（1）推理法（用于白箱）；（2）实验法（黑箱或灰箱）；（3）统计分析法（黑箱，但无法直接实验）（4）混合法；（5）类似法（建造原系统的类似模型）模拟法：对那些内部结构和特性不很清楚的系统，建立计算机仿真模型，模拟实际系统行为，通过模拟的输入、输出结果，评价和确认系统模型仿真：是利用模型对实际系统进行实验研究系统仿真系统仿真：是通过建立和运行计算机仿真模型，模仿实际系统的运行状态及随时间变化规律，以实现在计算机上进行实验的全过程通过对仿真运行过程的观察和统计，得到被仿真系统的仿真输出参数和基本特性，以此来估计和推断实际系统的真实参数和性能系统仿真系统仿真特点

有效的实验手段，为复杂系统创造了柔性计算机实验环境，节省认识系统运行规律的时间系统仿真是一种计算机仿真实验，需要较好的仿真软件支持系统建模仿真过程系统仿真的输出结果在仿真过程由软件自动给出需要多次仿真实验，才能统计推断、估计实际系统的真实参数和性能系统仿真系统仿真优点

直接面向实际过程和系统问题，将不确定性作为系统随机变量来处理，建立系统内部关系模型，有利于简化复杂并有多种随机因素的系统模型求解采用面向对象的建模分析方法，使用人机友好的计算机软件，有利于分析人员集中精力研究问题的内部因素及相互关系，避免复杂编程为分析和决策人员提供了有效实验环境，有利于他们直接参与调整模型参数或结构，选择满意方案系统仿真系统仿真的步骤问题描述与定义建立模型：要求面向问题和过程，选择适当的仿真模型与语言数据采集仿真模型确认：专家评价、统计检验、灵敏性分析编程实现与验证：仿真程序与模型的一致性仿真实验设计：定实验方案结果分析系统仿真（四）系统建模者应具备的素质应该具备以下几方面的能力：（1）对客观事物或过程能够透过现象抓住本质，使得对问题有一个深刻的理解、清晰的图景、清楚的层次和明确的轮廓。（2）在数学方面应有基本训练，要有一定的数学修养．并且掌握一套数学的思路和方法。（3）具有把实际问题与数学联系起来的能力，善于把各种现象中的表面差异撇去，而把本质的共性提炼出来。有些数学工作者或者实际工作者，在实际问题面前感到束手无策，主要就是由于缺乏这种能力，而这种能力在书本上是很难学到的。应该从实践中学，边干边学，逐步积累和培养这种能力。系统建模者应该注意避免的四种倾向是：懒、馋、贪、变。懒：没有详细地调查实际情况，仅仅根据一知半解，就随便假设，凭想象提出一些公式、数学方程和逻辑判断。结果：系统模型不能反映系统的实际情况，所得到的解无用。馋：建模时要求的数据太多，以至提供了全部现有数据和经过多方努力能够得到的数据也还是“喂不饱”。显然，这种要求是很难满足的。贪：企图把研究问题的一切细节、一切因素都要包罗进去，以致模型过于复杂而无法求解。这是由于抓不住问题的本质和关键，抓不住主要矛盾所造成的。变：企图把研究的问题“变”成为适合某种模型。这种改变问题的特征去适合某种模型的作法是一种本末例置的作法，由此而建立起来的模型一点用处也没有。必须记住的是，最好的模型是一个实用的切题的模型，而不是一个外表漂亮的失真的模型。第三节数学规划模型线性规划非线性规划动态规划整数规划……LP问题及其数学模型一、问题的提出二、线性规划的数学模型三、线性规划问题的标准形式四、图解法第三节数学规划模型一、问题的提出例2—1生产计划问题某工厂在计划期内要安排生产甲乙两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗、以及每件产品的获利如表所示。问该工程如何安排计划能使获利最大?甲乙总资源数设备（台时）128原材料A（kg）104原材料B（kg）013获利（元/件）23一、问题的提出目标函数

满足约束条件

一、问题的提出共同特征问题的所求均用一组未知变量表出，这些变量称为决策变量或称为设计变量，且问题的每—个具体的方案，都用一组取值为非负的决策变量表示每个问题都有一个决策变量或设计变量的线性目标函数，并有最大化或最小化两种类型。每个问题都存在若干约束条件，用一组线性等式或不等式来表达。，，，……，二、线性规划的数学模型，，，……，目标函数约束条件维数、价格系数、阶数、结构系数、常数1、和式二、线性规划的数学模型2、向量式二、线性规划的数学模型3、矩阵式二、线性规划的数学模型二、线性规划的数学模型，，，……，目标函数约束条件三、线性规划的标准形式，，，……，目标函数约束条件三、线性规划的标准形式，，，……，目标函数约束条件三、线性规划的标准形式，，，……，三、线性规划的标准形式，，，……，约束条件的标准化——松弛变量法自由变量的处理方法常数项为负值目标函数优化方向的变换需转换类型

变换的方法：目标函数为min型，价值系数一律反号。令f

(x)=-f(x)=-CX,有minf(x)=-max[-

f(x)]=-maxf(x)第i个约束的bi

为负值，则该行左右两端系数同时反号，同时不等号也要反向第i个约束为型，在不等式左边增加一个非负的变量xn+i

，称为松弛变量；同时令cn+i

=0第i个约束为型，在不等式左边减去一个非负的变量xn+i

，称为剩余变量；同时令cn+i

=0若xj0，令

xj=-xj

，代入非标准型，则有xj

0若xj

不限，令

xj=xj

-

xj

，xj

0，xj

0，代入非标准型三、线性规划的标准形式三、线性规划的标准形式，，，……，一个例子三、线性规划的标准形式，，，……，（1）转换自由变量三、线性规划的标准形式，，，……，（2）转换不等式三、线性规划的标准形式，，，……，（3）转换右端项及目标函数四、线性规划的图解法f(x)=36第四节系统动力学模型（一）系统动力学简述（二）动力学模型（一）系统动力学简述系统动力学主要是研究生产管理及库存管理问题的反馈动态行为的方法。起初叫工业动力学，后来当应用于城市问题时，又出现了城市动力学。当应用系统动力学建立了全国性、全球性模型之后，不但可以评估企业或政府及整个人类的经济方针和政策，摸出采用某项政策后在多长时间内其影响有多大，时间有多长。而且还可以用电子计算机按不同假设选择出各种变量，通过反馈自动打出系统的行为数据，并给出曲线图，以协助决策者作出更好更适当的选择。1.含义与内容系统动力学是研究反馈动态行为的方法论。具体说，系统动力学的内容是：①它把有生命和无生命系统称作为信息反馈系统来处理，并且认为在每个系统中部存在着信息反馈机构；②它把被研究系统划分为若干子系统，并建立各子系统的因果关系③在确定了因果关系的基础上，建立被研究系统的仿真模型——流图和结构方程式；④实行计算机仿真(在模型上做实验)；⑤验证模型的有效性；⑥为战略和策略的制订提供依据。1.含义与内容由系统动力学的内容可看出，它能对社会经济管理系统的规划和决策进行实验研究。领导者在作出重大决策之前，可先在“实验室”里做一些“实验”以便对将要实行的策略进行比较，决定取舍，或对系统的行为做出科学的预测。意义系统动力学，研究一个系统在活动中的信息反馈特性，可显示出系统组织的结构，放大和延滞的相互作用，以及对管理系统本身或企业本身所受到的影响。系统动力学建立了四个基础性的支柱：①信息反馈系统的理论；②决策制订过程的知识；③对复杂系统的实验模型方法；④用数字计算机作为实际模型的手段。2.系统动力学的建模特点系统动力学的建模别具一格，具有不同于其它预测方法的特点。现代的管理系统是庞大、复杂而由许多子系统构成。这些子构造相互作用形成了系统内部错综复杂的因果关系。这些因果关系形成作用环或反馈环。在一个管理系统中，我们可以找到多个这样的环，人们的决策活动就在这些环间进行。对于这样多重环的复杂系统来说，单凭人们的经验不能有效地跟踪。只有使用统计的方法。通过对系统输入、输出数据的处理，来获得系统的行为，称为“数据产生的行为”。但是管理系统从本质上讲，是缺乏数据的，关于描述系统行为的数据，虽然经过收集，很难做到完整。仅仅依据这种不完整的数据构筑起来的统计模型，其有效性是很有限的。实际上，人们认识事物的主要依据不是数据，而是事物的内部构造。系统可以划分为若干子构造，这些子构造的相互作用产生系统的行为。人们对于系统构造的认识，不是通过数据，而是通过逻辑思维、想象力和创造性来获得的。例：一个企业可以划分为生产量、库存量、订货量、受订欠付量等等。确定这些子构造和它们的因果关系并不需要数据，而数据只是用在构造概念基础上，建立各子构造的定量关系。数据和构造的有机结合，形成完整的系统构造模型。系统动力学在工程、经济甚至医学、心理学、社会学方面都获得相当成功。近年来，在科技管理系统，特别作为复杂系统的长期预测，确实是一种强有力的建模工具。（二）动力学模型1.几个概念（1）水平——贮放于水槽的水量或流水所积蓄的量。比如，经济上是库存量、银行存款额、工厂设备、资金、材料等；在世界性模型中，则以人口、资本、自然资源、可耕地等为水平变量。2．流速——平均单位时间流入水槽和流出水槽的水流量。比如，物料流中商品进货量和实际存货量，资金中的金钱支付交换量。每一个月的存款额，一年中设备投资等均属此类。世界模型中则有出生率和死亡率，自然资源的消耗，污染的产生和处理等均为流速的变量。水平流速的关系如下图系统动力学的水平与流速的关系一个可变水平和可变流速的基本结构可用来表示一个工业管理系统。水平决定了流速，而决策控制流速，流速反过来改变水平。这些水平和流速由信息、材料、订货、货币、人员和主要设备这六个相互交连的网络组成，用以反映工业系统的活动。如果把网络中(如物料网络)中较重要的阶段包括原料仓库、半成品库、成品库、运转仓库、批发商仓库和零售商仓库；放在网络中某一阶段的数量称为水平；我们又知道网络中发生各种水平的改变时，便能由网络的水平来说明某一时刻的网络状态。网络中的流送信息，便能预期网络中的下个水平决策被看作是决定未来系统状态的管理活动，以及决定系统水平改变的管理活动。在某一时间间隔的水平波动，因流入和流出量之差导致出积蓄。流速的符号象征着流量调节阀在经济学上，水平相当于固定资本，而流速相当于浮动。2.系统动力学的方程结构

系统动力学模型：按照数学的语言，就是所谓离散的差分方程。其表达式为：现在瞬时水平＝前一瞬时水平

+经历时间×流速差。3.应用举例例1市场销售模型设一批货物的成本为C(包括生产、运输、仓储管理等)，出售后的总收入为R则利润P＝R—C。货物的价格是销售量x的函数，即P＝P(X)，这个函数称为需求函数对整个市场来说，价格高需求量就减少；价格低时需求量就高，所以需求函数P(X)是X的递减函数。如果它是线性函数时，则其斜率为负。即

P(x)＝一ax十b(a＞o)而总收入：

R＝xP(X)＝一ax2十bX货物的成本C由不变成本FC和可变成本VC两部分组成。即

C＝FC十VC

如对农作物的成本、土地、工具的花费是不变成本，它是一个常数。而播种、肥料、收获的花费是可变成本，它是x的函数．问题：对某一货物销售量多大才能使利润P达到最大？则由P(x)＝R—C对x求导由P’(X)＝O得R＝C

这个公式是古典经济学中使用利润达到最大的一个基本关系式。第五节图与网络分析图的基本概念树最短路中国邮递员问题网络最大流问题最小费用最大流图最直观的模型图论与网络分析起源哥尼斯堡城中有一条河叫普雷格尔河，该河中有两个岛，河上有七座桥。BACD哥尼斯堡七桥问题欧拉在1736年发表图论方面的第一篇论文，解决了著名的哥尼斯堡七桥问题。从任何一点出发，能否通过每条边一次且仅一次回到出发点。BACD图论是一个古老的数学分支，它起源于游戏难题的研究。图论的内容十分丰富，应用得相当广泛，许多学科，诸如运筹学、信息论、控制论、网络理论、博弈论、化学、生物学、物理学、社会科学、语言学、计算机科学等，都以图作为工具来解决实际问题和理论问题。随着计算机科学的发展，图论在以上各学科中的作用越来越大，同时图论本身也得到了充分的发展。实际背景在组织生产中，为完成某项生产任务，各工序之间怎样衔接，才能使生产任务完成得既快又好。一个邮递员送信，要走完他负责投递的全部街道，完成任务后回到邮局，应该按照怎样的路线走，所走的路线最短。各种通信网络的合理架设交通网络的合理分布等问题G=（V，E）子图矩阵表示含元素的个数点的次边点边关系连通图树特殊的图简单图多重图空图部分树基本概念内容：有向图，无向图的基本概念。1、有向图，无向图的定义，2、图中顶点，边，关联与相邻，顶点度数等基本概念，3、各顶点度数与边数的关系及推论，基本概念（一）5、图的同构的定义。4、简单图，完全图，子图，补图的概念，基本概念一、图的概念。1、定义。无序积无向图中元素为无向边，简称边。，有向图中元素为有向边，简称边。，基本概念一、图的概念。1、定义。无序积基本概念基本概念图论(GraphTheory)：研究图的理论图：一个有序的三元组（V(G)，E(G)，ψG），这里V(G)和E(G)是互无公共元素的集合且V(G)非空，ψG称为关联函数，它使E(G)中的每一个元素对应于V(G)中元素的无序偶（偶中的元素可能相同）V(G)称为图G的顶点集，其中的元素称为图G的顶点E(G）称为图图G的边集，其中的元素称为图G的边基本概念弧(arc)：带箭头的连线有向图：一个有序的三元组（V(D)，A(D)，ψD），这里V(D)和A(D)是互无公共元素的集合且V(D)非空，ψD称为关联函数，它使A(D)中的每一个元素对应于V(D)中元素的序偶（偶中的元素可能相同）。有向图与无向图的区别：无对称性。基础图、始点、终点、路、回路2、图的表示法。有向图，无向图的顶点都用小圆圈表示。无向边——连接顶点的线段。有向边——以为始点，以为终点的有向线段。基本概念例1、(1)无向图，图形表示如右：基本概念图形表示如右：例1、(2)有向图，基本概念3、相关概念。(1)有限图——都是有限集的图。阶图——的图。零图——的图。特别，若又有，称平凡图。(2)关联(边与点关系)——设边(或)，则称与(或)关联。基本概念3、相关概念。(2)基本概念3、相关概念。(2)孤立点——无边关联的点。环——一条边关联的两个顶点重合，称此边为环(即两顶点重合的边)。基本概念3、相关概念。(2)悬挂点——只有一条边与其关联的点，所对应的边叫悬挂边。(3)平行边——关联于同一对顶点的若干条边称为平行边。平行边的条数称为重数。多重图——含有平行边的图。简单图——不含平行边和环的图。基本概念如例1的(1)中，与关联的次数均为1，与关联的次数为2，边都是相邻的，为孤立点，为悬挂点，为悬挂边，为环，为平行边，重数2，为多重图。基本概念4、完全图设为阶无向简单图，若中每个顶点都与其余个顶点相邻，则称为阶无向完全图，记作。若有向图的任一对顶点，既有有向边又有有向边，则称为有向完全图。基本概念例如：基本概念二、顶点的度数，握手定理。1、顶点的度数(简称度)。无向图的度数记，指与，相关联的边的条数。有向图的度数，基本概念二、顶点的度数，握手定理。1、顶点的度数(简称度)。最大度最小度对有向图相应地还有，，，。基本概念如例1的(2)中，，。基本概念设为图的顶点集，称为的度数序列。2、握手定理。定理1：设图为无向图或有向图，为边数)，，(则基本概念定理2：设为有向图，，则，。2、握手定理推论：任何图中，度为奇数的顶点个数为偶数。基本概念三、子图，补图。1、子图定义：设是两个图，若，，且，则称是的子图，是的母图，记作。真子图——

且(即或)。生成子图——且。基本概念三、子图，补图。导出子图——非空，以为顶点集，以两端均在中的边的全体为边集的的子图，称的导出子图。——非空，以为边集，以中边关联的顶点的全体为顶点集的的子图，称的导出子图。基本概念例3、上图中，(1)－(6)都是(1)的子图，其中(2)－(6)为真子图，(1)－(5)为生成子图。基本概念2、补图定义。设为无向完全图，，为无向简单图，其中，，则称，相对于互为补图，记，。基本概念基本概念四、图的同构。定义：设两个无向图，，若存在双射函数，使得对于任意的，当且仅当并且与重数相同，则称与同构，记作。基本概念例4、基本概念内容：图的通路，回路，连通性。重点：1、通路，回路，简单通路，回路，初级通路，回路的定义，2、图的连通性的概念，3、短程线，距离的概念。基本概念（二）一、通路，回路。1、通路(回路)中顶点和边的交替序列——，其中(无向图)，或(有向图)，——始点，——终点，称为到的通路。当时，为回路。基本概念一、通路，回路。2、简单通路，简单回路。简单通路(迹)简单回路(闭迹)复杂通路(回路)基本概念一、通路，回路。3、初级通路，初级回路。初级通路(路径)初级回路(圈)初级通路(回路)简单通路(回路)，但反之不真。4、通路，回路的长度——中边的数目。基本概念例1、(1)图(1)中，从的通路有：到…………长度3长度6长度6基本概念例1、(1)图(1)中，从的通路有：到…………初级通路简单通路复杂通路基本概念例1、(2)…………长度3长度4长度7图(2)中过)有：的回路(从到基本概念例1、(2)…………初级回路(圈)初级回路(圈)复杂回路图(2)中过)有：的回路(从到基本概念5、图中最短的回路。如图：基本概念6、性质。定理：阶图中，若从顶点到存在通路，则从到存在长度小于等于在一个的通路。推论：阶图中，若从顶点到存在通路，则从到存在长度小于等于在一个的初级通路。基本概念6、性质。定理：阶图中，若到自身存在回路，则从到自身存在长度小于等于的回路。在一个推论：阶图中，若到自身存在一个简单回路，则从到自身存在长度小于等于的初级回路。在一个基本概念6、性质。由以上定理可知，在阶图中，任何一条初级通路的长度任何一条初级回路的长度基本概念二、图的连通性。1、连通，可达。无向图中，从到存在通路，称到是连通的(双向)。有向图中，从到存在通路，称可达(注意方向)。基本概念2、短程线，距离。短程线——连通或可达的两点间长度最短的通路。距离——短程线的长度，记无向图有向图基本概念2、短程线，距离。若之间无通路(或不可达)，规定距离满足：(1)，时，等号成立。(2)若是无向图，还具有对称性，。基本概念3、无向图的连通。为连通图——是平凡图，或都是连通的。中任两点为非连通图——中至少有两点不连通。基本概念3、无向图的连通。设是一个无向图，是中顶点之间的连通关系，则是等价关系。设将划分成个等价类：，由它们导出的子图称为的连通分支，其个数记为基本概念4、有向图的连通。——中任一对顶点都互相可达(双向)——中任一对顶点至少一向可达——略去中有向边的方向后得到的无向图连通连通强连通单向连通弱连通强连通单向连通弱连通基本概念例2、强连通单向连通基本概念例2、单向连通弱连通非连通图基本概念内容：关联矩阵，邻接矩阵，可达矩阵。重点：1、有向图，无向图的关联矩阵，2、有向图的邻接矩阵。了解：有向图的可达矩阵。图的矩阵表示一、无向图的关联矩阵。1、设无向图，，，的关联矩阵，图的矩阵表示

无向图(下图所示)，求。解：图的矩阵表示2、性质。(1)(2)(3)握手定理图的矩阵表示(4)，当且仅当为孤立点。2、性质。(5)若第列与第列相同，则说明与为平行边。图的矩阵表示二、有向图的关联矩阵。1、设无环有向图，，，的关联矩阵，其中图的矩阵表示例2、有向图(下图所示)，求。解：图的矩阵表示2、性质。(1)(2)(3)图的矩阵表示三、有向图的邻接矩阵。1、设有向图，，的邻接矩阵，，其中指邻接到的边的条数(非负整数)。图的矩阵表示例3、有向图(下图所示)，求。解：图的矩阵表示2、性质。(1)(2)(3)(4)为中环的个数。图的矩阵表示3、求中长度为的通路数和回路数。(1)令矩阵乘法其中表示从到长度为2的通路数或回路数。图的矩阵表示3、求中长度为的通路数和回路数。考虑，简记为。其中表示从到长度为或回路数。的通路数中长度为为的通路总数，其中为中长度为的回路总数。图的矩阵表示3、求中长度为的通路数和回路数。(2)设则中元素为中到长度小于等于的通路总数，为中长度小于等于的通路总数，其中为中长度小于等于的回路总数。图的矩阵表示例4、在例3的有向图中求，，。解：，，图的矩阵表示四、有向图的可达性矩阵。(了解)设为有向图，，令，图的矩阵表示四、有向图的可达性矩阵。(了解)可达性矩阵其中元素可由求得：图的矩阵表示树(tree)树：一个无圈的连通图称为树例：已知有5个城市，要在他们之间架设电话线，要求任何两个城市都可以互相通话（允许通过其他城市），并且电话线的根数最少。v1v2v5v4v3e1e2e3e4e5树的性质定理1：设图G=(V,E)是一个树，p(G)>=2，则G至少有两个悬挂点。定理2：图G=(V,E)是一个树的充分必要条件是G不含圈，且恰有p-1条边。定理3：图G=(V,E)是一个树的充分必要条件是G是连通图，并且

q(G)=p(G)-1定理4：图G是一个树的充分必要条件是任意两个顶点之间恰有一条路。v1v2v5v4v3e1e2e3e4e5v6图的支撑树设图T=(V,E’)是图G=(V,E)的支撑子图，如果图T=(V,E’)是一个树，则称T是G的一个支撑树。v1v2v4v3图1v1v2v4v3一个支撑字图支撑树的获得定理5：图G有支撑树的充分必要条件是图G是连通的。寻求支撑树的方法：（1）破圈法（2）避圈法v1v2v5v4v3v6v1v2v5v4v3v6最小支撑树问题给定G=(V,E)，对G中的每一条边[vi,vj]，相应地有一个数wij，则称这样的图为赋权图，称为边[vi,vj]上的权(weight)。如果T=(V,E’)是G一个支撑树，称E’中所有边的权之和为支撑树T的权，记为w(T)，即最小支撑树问题最小支撑树T*：权最小的支撑树，即求最小支撑树的方法：（1）避圈法（2）破圈法破圈法v1v2v5v4v361752v65443避圈法v1v2v5v4v361752v65443最短路问题例：某人预从v1出发，通过这个交通网络到v8去，求使总费用最小的旅行路线。v2v5v1v4v36361101362v6v7v8v922243410几个定义给定一个赋权有向图D=(V,A)，对每一个弧a=(vi,vj)，相应有权w(a)=wij

，又给定中的两个顶点vs，vt

。设P是D中从vs到vt的一条路，定义路P的权是路P中所有弧的权之和，记为w(P)。最短路问题最短路问题就是在所有从vs到vt的路中，求一条权最小的路，即求一条从vs到vt的路P0，使式中对D中所有从vs到vt的路P取最小，称P0是从vs到vt的最短路。路P0的权称为从vs到vt的距离，记为d(vs,vt)最短路算法Dijkstra方法（所有wij≥0）基本思想：从vs出发，逐步地向外探寻最短路。执行过程中，与每个点对应，记录下一个数（称为这个点的标号），它或者表示从vs到该点的最短路的权（称为P标号）、或者是从vs到该点的最短路的权的上界（称为T标号），方法每一步是去修改T标号，并且把某一个具T标号的点改变为P标号的点，从而使D中具P标号的顶点数多一个至多经过p-1步，就可以求出从到各点的最短路。具体过程v2v5v1v4v36361101362v6v7v8v922243410P具体过程v2v5v1v4v36361101362v6v7v8v922243410PPPPPPPP网络最大流问题城市供水管网v2v5v1v4v31055108v64113317基本概念与定理网络：给一个有向图D=（V，A)，在V中指定了一点，称为发