资源描述：
《运筹学第八章》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第八章图与网络模型第一节图与网络的基本知识•什么是图？•图有什么用处？图可以用来表示事物与事物之间的联系如：物质结构、电路网络、城市规划、交通运输等图论：运筹学中应用很广泛的一个分支。许多管理科学、计算机科学、信息论、控制论、物理、化学、生物学、心理学等领域的许多问题都可以描述为图论模型来解决。欧拉：哥尼斯堡七桥问题§图论的创始人§发表了第一篇关于图的论文哥尼斯堡七桥问题：东普鲁士的哥尼斯堡城是一个风景宜人的旅游胜地，也是一个在战争中双方必争的战略要地。哥尼斯堡城中有一条河叫做普雷格尔河，该河横贯城区，河中间有两个岛形
2、地带，这种分布情况把全城分为北区、南区及中央的岛区四个区域，这四个区域分别由七座桥相连。那里的居民热衷于这样的问题：一个散步者能否走过七座桥，且每座桥只走过一次，最后回到出发点。一、图的模型1、哥尼斯堡七桥问题（欧拉1736）A雷尔河普C格DAl·BCl·l·D一笔画问题Bl·2、周游世界问题（哈密顿1857）3786254915161417101318哈密顿圈问题191112120二、图的基本概念1、图（G）：点和边的集合。若点的集合记为V,边的集合记为E,则一个图可以记作G={V,E}。若图中的点和边赋以具体的含义
3、和权数，则该图称为网络图，记为N.v5e·eV={,,,,}v1v2v3v4v55e47E={,,,,,,}eeeeeeevv12345671·e6·4eeG={V,E}13e1=[,]v1v2v·2e2·v32、端点、关联边、相邻：v·1ee13e1=[,]v1v2v·2e2·v33、环、多重边、简单图：vv·5·5e5e7e4e5e4vvvv1·e6·41·e6·4e1e3e1e3vvv·2e2·3v2·e2·3e84、次、奇点、偶点、孤立点：v·5以点vi为端点的边的个数称vv为点vi的次，记作d()vi1·e·
4、44e1e6e3d()v1=3奇点v·2e2·v3d()v2=4偶点d()v=0孤立点5e55、初等链、圈、连通图：v在图中，任意两点间由点和5e7·e8边相互交替构成的一个点不vv重复的序列称为初等链。1·e·44e1e6e3起点和终点重合的链称为圈。v2·e2·v3一个图中，若任意两点间都至少存在一条链，则称该图e5为连通图，否则称为非连通图。6、子图、支撑子图（部分图）：GG图G={V，E}，图G={V，E}21v1112225e7·e8若有VÍV和EÍE，称1212vv1·e4·4图G1是图G2的一个子图。e1
5、e6e3v·2e2·v3e56、子图、支撑子图（部分图）：G图G={V，E}，图G={V，E}21v1112225e7·e8若有VÍV和EÍE，称1212vv1·e·4图G是图G的一个子图。412e1e6e3Ì若有V1=V2和E1E1，称v·2e2·v3图G1是图G2的一个支撑子图。e5支撑子图是子图，但子图不一定是支撑子图例：有甲、乙、丙、丁、戊、己六名运动员报名参加A、B、C、D、E、F六个项目的比赛，下表中打√的是各运动员报名参加的比赛项目。问六个项目的比赛顺序应如何安排，使每名运动员不用连续的参加比赛。ABCD
6、EF甲√√√BD乙√√√丙√√AF丁√√戊√√√己√√√CEACBFED第二节树青海大学医学院财经学院基础部昆仑学院经济学系工商管理系管理科学与工程系统计运筹教研室信息管理教研室一、定义：不含圈的连通图。记作T(V,E)··········v1vv11vv22vv83v2v3vvv354vvv564v4vv97vv5v86vvv6v97v8(b)7(a)(c)上图中，(a)就是一个树，而(b)因为图中有圈所以就不是树，(c)因为不连通所以也不是树。二、树的性质§1、图G是树任意两个顶点之间恰有一条链。§2、从一个树中去
7、掉任意一条边，则余下的图是不连通的。(在点集合相同的所有图中，树是含边数最少的连通图)§3、在树中不相邻的两个点间添上一条边，则恰好得到一个圈。(进一步，若再从这个圈上任意去掉一条边，可以得到一个树。)三、图的最小支撑树（最小部分树）1、定义定义1：若图G1既是图G2的支撑子图（部分图），又是一颗树，则称图G1是图G2的支撑树（部分树）。v·2vv1··v·5·4v3定义2：图G2的所有支撑树中各边权重总和最小的那颗树，称为图G的最小支撑树（最小部分树）。22、寻找最小支撑树§避圈法§破圈法§避圈法（1）选择一条权数最
8、小的边（如果有两条或两条以上的边都是权数最小的边，则任意选择一条）。（2）在剩下的边里选择下一条权数最小的边（如有多个，任选），只要不和前面所选的边构成圈即可。（3）重复第（2）个步骤，直到不能再选下去为止。§避圈法v·2272vvv45v1·5·5·5·714137·v34·v6权重之和为14§破圈法（1）在给定的赋权的连通图上
