图的基本概念与模型.doc

第6章 图与网络分析 §1 图的基本概念与模型 在生产和日常生活中，我们经常碰到各种各样的图：公路或铁路交通图、管网图、通讯联络图等。运筹学中研究的图是上述各类图的抽象概括，它表明一些研究对象和这些对象之间的联系。 网络：网络社会，计算机信息网络，电话通信网络，运输服务网络，商业网点（商圈），人际关系网络等等。 图与网络分析或网络优化就是研究如何有效地计划、管理和控制网络系统，使其发挥最大的社会和经济效益。这也是属于最优化（optimization）问题。 例1：公路连接问题 某一地区有若干个主要城市，现准备修建高速公路把这些城市连结起来，使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市，假定已经知道了任意两个城市修建高速公路的成本，那么应如何决定在哪些城市间修建高速公路，使得总成本最小？ （最小生成树问题 Mst-minimum Spanning tree） 例2：最短路问题（SPP-Shortest Path Problem） 一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地，从甲地到乙地的公路网纵横交错，因此有多种行车路线，这名司机应选择哪条路线呢？假设货柜车的行驶速度是恒定的，那么这一问题相当于需要找到一条从甲地到乙地的最短路。 例3：经典运输问题（Transportation Problem） 如何安排运输方案使总运费最省？总利润最大？ 例4：指派问题（Assignment Problem） 如何指派使效率最高或者使总回报最大？ 例5：中国邮递员问题（CPP－Chinese Postman Problem） 一名邮递员负责投递某个街区的邮件，如何为他（她）设计一条最短的投递路线（从邮局出发，经过投递区的每一条街道至少一次，最后返回邮局）？由于此问题是由我国复旦大学管梅谷教授1960年首先提出并解决的，所以国际上称之为中国邮递员问题。 例6：旅行商 /货郎担问题（TSP－Traveling Salesman Problem） 一名推销员准备前往若干城市推销产品。如何为他设计一条最短的旅行路线（从驻地出发，经过每个城市恰好一次，最后返回驻地）？又称为一笔画问题。300多年前由Euler提出的哥尼斯堡七桥问题。 特点：（1）与图形有关，或易于用图形方式表达； （2）优化问题，从若干种可能的安排或方案中寻求某种意义下的最优安排方案。 图：定义为点和边的集合，表示图中顶点（节点）的集合，表示图中连接顶点的边的集合。 1．端点、关联边、相邻：若边可以表示为，称为边的端点，反之称为点的关联边。若两个端点与同一条边关联，则称端点相邻；若边具有公共的端点，则称边相邻。 例：与相邻的边有 与相邻的点有 2．环、多重边、简单图、多重图：若边的两个端点相重，则称该边为环（自回路，如），若两个端点之间的边多于一条，则称为具有多重边（如）。对于无环、无多重边的图称作简单图，否则称为多重图。（本例图不是简单图） 3．次、奇点、、偶点、孤立点：与某一个点相关联的边的数目称为点的次（也叫做度或线度），记作。如；次为奇数的点称为奇点，次为偶数的点称为偶点，次为0的点称为孤立点。 （所有点的次数之和等于边数的2倍，又称为握手定理） 4．链、路、圈、回路、连通图：对于图中交替序列， 若其中各边互不相同，且任意均相邻，则称为链；若链中所有顶点均不相同，则称此链为路；对起点与终点相重合的链称作图；起点与终点重合的路称作回路。在中，若每一对顶点之间至少存在一条链，则称这样的图为连通图，否则就称为不连通的。 例：是一条链，但它不是路； 是一条链，同时也是路； 由于任意两个顶点之间必存在一条链，所以该图是连通图。 5．完全图、偶图：一个简单图中若任意两点之间均有边相连，称这样的图为完全图。含有个顶点的完全图，其边数有条。如果图的顶点能分为两个互不相交的非空集合，使得在同一个集合中任意两个点均不相邻，称这样的图为偶图（二分图）。若偶图的顶点集合之间的每一对不同顶点都有一条边相连，称这样的图为完全偶图。若完全偶图含有个顶点，含有个顶点，则其边数共有条。 6．子图、部分图：对于图和，若有和，则称是的一个子图；若有和，则称是的一个部分图。 此外，还有有向图和无向图等概念，到后面我们用到时再介绍。 对要研究的问题确定具体的对象及这些对象间的性质联系，且用图的形式表示出来，这就是对所研究的问题建立图的模型。 例1：有甲、乙、丙、丁、戊、己六名运动员报名参加六个项目的比赛，下表中打“√”的是各运动员报名参加比赛的项目，问六个项目的比赛顺序应如何安排，能做到每名运动员都不连续地参加两项比赛。 √ √ √ √ √