第五章图论及网络模型

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

1、第五章　图论与网络模型图论起源于１７３６年Euler对著名的K迸igsberg七桥问题的讨论．由于社会历史条件的限制，在此后的１００多年里发展缓慢．到１９世纪中叶，由于对电网络、晶体模型和分子结构等的研究，图论又重新引起人们的重视．尤其是２０世纪中叶以来，随着数学对各个领域的广泛渗透和计算机的广泛应用，离散数学问题处于越来越重要的地位，图论作为一门提供离散数学模型和求解方法的应用数学学科，新的成果大量涌现．由于图论具有能解决许多用传统数学方法无法解决的问题的特殊功能，以及形象和直观的特点，人们应用图论来解决交通运输、生产规划、经济管理、运筹学、系统论、控制论、信息论、数值分类、计算机科学、

2、通信网络、开关电路、博奕论、地理学、生物学、心理学等领域中的许多实际问题，图论成为一个引人注目的十分活跃的学科．随着实践的发展，其巨大的潜力将会被人们进一步认识、发掘和利用．本章介绍图论的一些基本概念与理论，典型问题和建立图论与网络模型的思路，以及常用的算法．第一节　基本概念现实世界的许多现象可用一类图形来描述，这种图形由一个点集和连接该点集中某些点对的边所构成．例如，用点表示车站，边表示车站间道路的交通示意图；用点表示人，边表示一对朋友的人际关系图．对这种图形，人们主要感兴趣的是有哪些点其两点之间能被一条边连接，而点的相对位置及边的长短曲直则无关紧要．大量的这类事实的数学抽象，导致了图的

3、概念．序偶（V，E）称为图，记作G＝（V，E），其中顶点构成的集合V称为顶点集或点集，V中的点对之间的边构成的集合E称为边集．｜V｜称为图G的阶．G的边可以无方向（称为无向边），也可以有方向（称为有向边或弧），记为e＝uv，其中u，v∈V，e∈E，称e的两个端点u与v相邻，u，v与e相互关联．在有向边e＝uv中，u，v分别称为e的始点和终点．有公共端点的两条边称为相邻边．端点重合的边称为环．同一对顶点间边的条数称为边的重数．无环且无重数大于１的边的图称为简单图．只有无向边的图称为无向图，只有有向边的图称为有向图，既含无向边又含有向边的图称为混合图．图中与顶点v关联的边数称为v的次数或度数，

4、记为d（v）；有向图中以v为始点（终点）的边数称为v的出度（入度），记为d＋（v）（d－（v））．显然d（v）＝d＋（v）＋d－（v）．图的顶点的次数有如下性质：①Σv∈Vd（v）＝２｜E｜；②图中次数为奇数的顶点必为偶数个；③Σv∈Vd＋（v）＝Σv∈Vd－（v）．每个顶点的度为n－１的n阶无向图称为n阶无向完全图，记为Kn．每个顶点的出度和入度均为n－１的n阶有向图称为n阶有向完全图，也记为Kn．若G的顶点集V可分成两个不相交的非空子集V１，V２，使G的每条边的端点，一个属于V１，另一个属于V２，则称G为二分图或偶图，记为G＝（V１，V２，E）．若简单二分图G＝（V１，V２，E）中V１

5、的每个顶点与V２的所有顶点相邻，则称G为完全二分图，记为Kn，m，其中n＝｜V１｜，m＝｜V２｜．图论中的图与位置、大小、形状、面积、体积等几何要素无关，是一种更抽象的图．图的最本质的内容实际上就是一个二元关系，即点与边的关联关系．因此具有二元关系的系统或结构便可用图作为数学模型，且图具有直观性和艺术性，应用相当广泛．设G＝（V，E），G′＝（V′，E′），若V′彻V，E彻E′，则称G′为G的子图．特别地，若V′＝V，则称G′为G的生成子图；若V′彻V，E′含G在V′之间的所有边，则称G′为由V′导出的子图，记为G［V′］，·１７０·数学建模（本科册）G［V－V′］记为G－V′；若E′彻E

6、，V′含E′中边的全体端点，则称G′为由E′导出的子图，记为G［E′］；从G中删去E′的所有边得到的生成子图记为G－E′，在G上增加E′的所有边得到的图记为G＋E′．G＝（V，E）中的一个点边交替序列μ＝v０e１v１e２v２⋯ekvk称为G的一条通路（有向通路），简记为μ＝v０v１⋯vk，其中ei的端点为vi－１和vi（ei的始点为vi－１，终点为vi），i＝１，２，⋯，k，k称为μ的长．点均不同的通路（有向通路）称为链或路径（有向链或有向路径）．若v０＝vk，则通路（有向通路）称为回路（有向回路），链（有向链）称为圈（有向圈）．若无向图G的任意两点间都存在通路，则称G为连通图．若V分成非

7、空子集V１，V２，⋯，Vr，当且仅当u，v∈Vi时，u与v之间才有通路，则称子图G［V１］，G［V２］，⋯，G［Vr］为G的连通分支．连通分支的个数记为w（G）．对有向图G的任意两点u与v：若存在从u到v及从v到u的通路，则称G是强连通的；若存在从u到v或从v到u的通路，则称G是单向连通的；若不考虑G的边的方向，即G作为无向图是连通的，则称G是弱连通的．设G为无向图，V＝｛v１，v２，⋯，vn｝，　E＝｛e１，e２，⋯，