图论模型(第一讲)

《图论模型(第一讲)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数学建模图论方法专题图论在数学建模中的应用建立OR/MS理论模型的一般步骤模型准备模型假设模型分析模型构成模型求解模型应用模型检验下一页网络优化图论在数学建模中的应用主要涉及网络优化模型网络=赋(加)权图网络优化问题,即在网络中求权最大（或最小）的某类子网络基本而重要的网络优化问题有:最小树问题最短路问题网络流问题中国邮递员问题旅行售货员问题匹配问题网络优化模型简介网络优化网络优化的例子1.1公路连接问题某个地区有若干个主要城市，现在准备修建高速公路把这些主要城市连接起来，使得其中任何一个城市都可以直接或间接的通过高速公路到达另一个城市，假设已经知道了任

2、意两个城市之间修建高速公路的成本，那么应选择在那些城市修建高速公路使得所花费的成本最少？1.2最短路问题一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地，从甲地到乙地的公路网纵横交错，因此有多种行车路线，那么司机应选择哪条行车路线呢？假设司机的货车运行速度是恒定的，那么这个问题就可转化为从甲地到乙地寻找一条最短路。网络优化网络优化2.图论的基本概念1)图的概念2)赋权图与子图3)图的矩阵表示4)图的顶点度5)路和连通1)图的概念定义一个图G是指一个二元组(V(G),E(G))，其中:其中元素称为图G的顶点.组成的集合，即称为边集,其中元素称为边.

3、定义图G的阶是指图的顶点数

4、V(G)

5、,用来表示；图的边的数目

6、E(G)

7、用来表示.也用来表示边是非空有限集，称为顶点集，1)2)E(G)是顶点集V(G)中的无序或有序的元素偶对表示图，简记用定义若一个图的顶点集和边集都是有限集，则称其为有限图.只有一个顶点的图称为平凡图，其他的所有图都称为非平凡图.定义若图G中的边均为有序偶对,称G为有向边为无向边，称e连接和，顶点和称图.称边为有向边或弧,称是从连接，称为e的尾，称为e的头.若图G中的边均为无序偶对，称G为无向图.称为e的端点.既有无向边又有有向边的图称为混合图.常用术语1)边和它的两端点称为互相关联

8、.2)与同一条边关联的两个端点称为相邻的顶点，与同一个顶点点关联的两条边称为相邻的边.3)端点重合为一点的边称为环，端点不相同的边称为连杆.4)若一对顶点之间有两条以上的边联结，则这些边称为重边．5)既没有环也没有重边的图，称为简单图．常用术语6)任意两顶点都相邻的简单图,称为完全图.记为Kv.7)若，，且X中任意两顶点不，相邻，Y中任意两顶点不相邻，则称为二部图或偶图；若X中每一顶点皆与Y中一切顶点相邻,称为完全二部图或完全偶图,记为(m=

9、X

10、,n=

11、Y

12、)．8)图叫做星.二部图2)赋权图与子图定义若图的每一条边e都赋以一个实数w(e)，称w(e)为

13、边e的权，G连同边上的权称为赋权图.定义设和是两个图.1)若,称是的一个子图,记2)若，，则称是的生成子图.3)若，且，以为顶点集，以两端点均在中的边的全体为边集的图的子图，称为的由导出的子图，记为.4)若，且，以为边集，以的端点集为顶点集的图的子图，称为的由导出的边导出的子图，记为.3)若，且，以为顶点集，以两端点均在中的边的全体为边集的图的子图，称4)若，且，以为边集，以的端点集为顶点集的图的子图，称为的由导出的边导出的子图，记为.为的由导出的子图，记为.3)图的矩阵表示邻接矩阵:1)对无向图，其邻接矩阵，其中：(以下均假设图为简单图:无重边和自回路

14、).2)对有向图,其邻接矩阵,其中：其中：3)对有向赋权图,其邻接矩阵,对于无向赋权图的邻接矩阵可类似定义.关联矩阵1)对无向图，其关联矩阵,其中：2)对有向图，其关联矩阵,其中：4)图的顶点度定义1)在无向图G中，与顶点v关联的边的数目(环算两次),称为顶点v的度或次数，记为d(v)或dG(v).称度为奇数的顶点为奇点，度为偶数的顶点为偶点.2)在有向图中，从顶点v引出的边的数目称为顶点v的出度，记为d+(v)，从顶点v引入的边的数目称为v的入度，记为d-(v).称d(v)=d+(v)+d-(v)为顶点v的度或次数．定理的个数为偶数．推论任何图中奇点5

15、)路和连通定义1)无向图G的一条途径（或通道或链）是指一个有限非空序列，它的项交替地为顶点和边，使得对，的端点是和,称W是从到的一条途径，或一条途径.整数k称为W的长.顶点和分别称为的起点和终点,而称为W的内部顶点.2)若途径W的边互不相同但顶点可重复，则称W为迹或简单链.3)若途径W的顶点和边均互不相同，则称W为路或路径.一条起点为,终点为的路称为路记为定义1)途径中由相继项构成子序列称为途径W的节.2)起点与终点重合的途径称为闭途径.3)起点与终点重合的的路称为圈(或回路)，长为k的圈称为k阶圈，记为Ck.4)若在图G中存在(u,v)路，则称顶点u和

16、v在图G中连通.5)若在图G中顶点u和v是连通的，则顶点u和v之之间的距离d(u