第三章 结构模型与技术

1、,如果不借助模型下列问题很难解决： （1）不可重复的过程（地震，山崩，导弹发射，回采冒顶） （2）可以重复但是造价太高或时间太长（发射装置，桥梁流变）,1.1 模型定义： 模型是对实体的特征及其变化规律的一种表征或者抽象，而且往往是对实体中那些所要研究的特定的特征的抽象。具体见P58。 注意两点：一是特定特征；二是为什么只对特定特征进行抽象？ 分类：（表达方式）,模型,实体模型,抽象模型,实物模型,模拟模型,数学模型,物理、化学、美术,结构模型,城市规划、作战沙盘、采矿模型等,地图、电路图、建筑图等,1.2 现实世界与模型（实物与模型）,P59图4-1表达了数学建模的过程，其实也是通用的建模过

2、程。,1.3 建模原则和步骤 原则：既要准确反映实物，有易于研究和解决问题。即： （1）现实性；（2）简洁性；（3）适应性；（4）强壮性。 步骤：,2.1引言,七桥问题,2、图及网络方法,图的基本概念,图的矩阵表示法,应用特例,图1是我国北京，上海等10个城市之间铁路交通图，反映了这十个城市间的铁路分布情况。这里用点代表城市，连线代表铁路。诸如此类的还有电话线分布图，煤气（油）管道图等。 例2，A，B，C，D，E五球队比赛情况：A与其他队都比过一次，E和D比赛过，C和B，D比赛过。可用V1，V2，V3，V4，V5级之间连线表示这些情况（图2）,2. 2 基础知识,（1）图：节点+边（弧）V3

3、（2）无向图：V4V2V1 （3）有向图：V5 （4）节点数和边数：图G=（V，E），节点个数P（G），边Q（G）， （5）端点和关联边：若ei=Vi，VjE，则称Vi，Vj是边ei的端点，边ei是顶点Vi和Vj的关联边 （6）相邻点和相郊边：同一条边的两端点成为相邻点；有公共端点的两条边称为相邻边。 （7）多重边和环：具有相同端点的边；两个端点落在一个顶点的边。 （8）多重图和简单图：含有多重边的图；无环，无多重边的图。 （9）次：以Vi为端点的边的条数为定点Vi的次。d（Vi） （10）悬挂点和悬挂边：次为1的顶点；与悬挂点相连的边。 （11）孤立点：次为零的节点。 （12）奇点与偶点：次

4、为奇数的点；次数为偶数的点。,（13）圈：若链M中Vi1=Vir，即始点与终点重合，则称此链为圈。 （14）连通图和不连通图：一个图G的任意两个顶点，若至少有一条通路将其连接起来，则这个图G为连通图，否则为不连通图。 （15）支撑子图：给定一个图G=（V，E），若图G=（V,E），使V=V及E属于E，则称G是G的一个支撑子图。 （16）赋权图：设G=（V，E），对任意一条边eE，若相应都有一个数值W（e），则称G为赋权图，W（e）称为边e的权。 （17）赋权有向图：D=（V，A），aA，都由W（e）（权距离，费用，时间等）。 在实际工作中，很多问题的可行方案都可通过一个赋权有向图表示，（若物资

5、运输线路的安排，装卸设备的更新，排水管道的铺设等。所以赋权图被广泛应用于解决工程技术及科学管理领域的最优化问题。 （18）网络：通常，我们称赋权图为网络，赋权有向图为有向网络，赋权无向图为无向网络。,2.3 树、最小支撑树,在各式各样的图中，有一类图极其简单而却是很有用的。 例： 一支由五个城市，要在其之间架电话线，要求任两个城市都可以互相通话（允许通过其他城市），并且电话线根数最少。 解：用V1，V5五个点代表五个城市，若在某两城市之间架设电话线，则在相应的两个点之间连一条边，这样一个电话网就可以用一个图来表示。 为使任两个城市之间都可以通话，这样的图必须是连通的，其次，若图中有圈的话，从圈

6、上任意去掉一条边，余下的图仍是连通的，这样可省去一根电话线。因而要求得到满足的电话网所对应的图必定是不含圈的连通图。（树可满足这一要求）,例： 某厂组织机构，用树表示。,树：一个无圈的连通图称为树，通常以T表示。从定义推出性质： （1）具有n个顶点的树，其边数恰好为n-1条。 （2）树的任意两顶点之间有且仅有一条链。 （3）在树T中去掉任一条边，则T成为不连通图。 （4）在树T中不相邻的两个顶点间添上一条边，则恰好得到一个圈。进一步地说，若再从这个圈上任意去掉一条边，则可得到一个树。（5）图的支撑树：设图T=（V，E）是图G=（V，E）的支撑子图，若图T=（V，E）是一个树，则称T是G的一个支

7、撑树。如图5-b是图5-a的一个支撑树。,由此可得出两种寻求连通图的支撑树的方法。（1）破图法：在图G中任取一个圈，从圈中去掉一边，对余下的图中重复这个步骤，直到不含圈时为止，即得到一个支撑树。例：图5-a图5-b.（2）避圈法：在图中任取一条边e1，找一条与e1不构成圈的e2，再找一条与e1，e2不构成圈的边e3，一般，设已有e1，e2，ek，找一条与e1，e2，ek中任何一些边不构成圈的边ek+1，重复这个过程，直到不能进行为止。这时，由所取出的边构成的图是一个支撑树。,最小支撑树问题 设有一个连通图G=（V，E），每一边e=（Vi，Vj）有一个非负权 W（e）=（Wij0）。若T=（V，

8、E）是G的一个支撑树，称E中所有边的权之和为支撑树T的权，记为W（T），即W（T）=Wij。 若存在一个支撑树T* 使得W（T*）在所有的支撑树中权最小，则称T* 是G的最小支撑树。 不同地点间电话网架设，管线，道路铺设，旅游路线安排均可用“求最小支撑树”解决。,最小支撑树求法： （1）破圈法：在连通图G中，从圈中去掉一条权最大的边。在余下的图重复这一步骤，直到不含圈为止，即为最小支撑树。 （2）避圈法：在连通图G中，开始选一条最小权的边，以后每步中，总从未被选取的边中选一权最小的边，并使之与已选取的边不构成圈。重复，直到不存在与已选边不构成圈的边为止。,Example 1,权重有向图,1、邻

9、接矩阵 图的基本的矩阵表示，它用来描述图中各节点两两之间的关系。如图所示的有向图可以用邻接矩阵表示。,行为零的元素对应的点为汇入点； 列为零的元素对应的点为源点。,比如多个点之间的距离问题即为一个邻接矩阵，只是该图是一个无向图，其邻接矩阵和有向图的邻接矩阵相比不同。,S=,2、能源需求模型 每一有向线段标出的数字代表起始节点变化单位值对于相邻节点的影响，1和3节点之间的权重2.6表示能源供给量增加1单位则用户数增加2.6单位。1和2节点之间的 权重为-1.8表示能源供给量增加1单位价格将下降1.8单位。,3、人口转移模型 （1）用权重有向图还可以描述一类概率模型，如人口由一个地方向另一个地方流动的概率。而这类以权重为概率的有向图，其邻接矩阵称为传递概率。,（2）马尔可夫链 具有传递概率的即其记忆跨度只有一步的随机过程，是一种由多步距组成的链，相应发生的状态称之为马尔可夫链。,4、莱氏人口模型 用以预测各年龄