运筹学基础及应用--61选编课件.ppt

1、新疆农业大学数理学院主讲 黄华第六章第六章图与网络分析图与网络分析 近代图论的历史可追溯到近代图论的历史可追溯到1818世纪的七桥问题世纪的七桥问题穿穿过过哥尼斯堡哥尼斯堡城的七座桥，要求每座桥通过一次且仅通城的七座桥，要求每座桥通过一次且仅通过一次。过一次。这就是这就是著名的著名的“哥尼斯堡哥尼斯堡七七桥桥”难题。难题。Euler1736Euler1736年证明了不可能存在这样的路线。年证明了不可能存在这样的路线。BACDABCD 图论与网络分析理论所研究的问题十分广泛，内图论与网络分析理论所研究的问题十分广泛，内容极其丰富。正如一位数学家所说：容极其丰富。正如一位数学家所说：“可以说，图可

2、以说，图论为任何一个论为任何一个包含了某种二元关系包含了某种二元关系的系统提供了一的系统提供了一种分析和描述的模型。种分析和描述的模型。”一个案例一个案例:国庆大假期间旅游非常火爆，机票早已订购一空。成都一国庆大假期间旅游非常火爆，机票早已订购一空。成都一家旅行社由于信誉好、服务好，所策划的国庆首都游的行情家旅行社由于信誉好、服务好，所策划的国庆首都游的行情看好，要求参加的游客众多，游客甚至不惜多花机票钱暂转看好，要求参加的游客众多，游客甚至不惜多花机票钱暂转取道它地也愿参加此游。旅行社只好紧急电传他在全国各地取道它地也愿参加此游。旅行社只好紧急电传他在全国各地的办事处要求协助解决此问题。很快

3、，的办事处要求协助解决此问题。很快，各办事处将其已订购各办事处将其已订购机票的情况传到了总社。机票的情况传到了总社。根据此资料，根据此资料，总社要作出计划，最总社要作出计划，最多能将多少游客从成都送往北京以及如何取道转机。多能将多少游客从成都送往北京以及如何取道转机。各办事处已订购机票情况表各办事处已订购机票情况表成都成都重庆重庆武汉武汉上海上海西安西安郑州郑州沈阳沈阳昆明昆明广州广州北京北京成都成都 重庆重庆 武汉武汉 上海上海 西安西安 郑州郑州 沈阳沈阳 昆明昆明 广州广州 北京北京10 5 15 8 12 10 3010 6 15 25 10 15 8 8 6 14 8 18 8 10

4、 8 2 6 10 将此问题通过图的模型描述：将此问题通过图的模型描述：点点各城市，带箭头各城市，带箭头连连线线从箭尾城市到箭头城市已订购有机票，带箭头连线旁从箭尾城市到箭头城市已订购有机票，带箭头连线旁的数字的数字机票数量机票数量。成成重重武武昆昆上上广广西西郑郑沈沈京京8郑州办事处已订郑州办事处已订有的到北京的有的到北京的机票数量。机票数量。6.1 图图的基本概念与模型的基本概念与模型 图论中图是由点和边构成，图是由点和边构成，可以反映一些对象之间的关系。一般情况下图中点的相对位置如何、点与点之间联线的长短曲直，对于反映对象之间的关系并不是重要的。图的定义：图的定义：若用点点表示研究的对象

5、，用边边表示这些对象之间的联系，则图图G可以定义为点和边的集合，可以定义为点和边的集合，记作：,EVG 其中其中:V点集点集 E边集边集 图图G区别于几何学中的图。这里只关心图中有多区别于几何学中的图。这里只关心图中有多少个点以及哪些点之间有连线。少个点以及哪些点之间有连线。(v1)赵赵(v2)钱钱 孙孙(v3)李李(v4)周周(v5)吴吴(v6)陈陈(v7)e2e1e3e4e5(v1)赵赵(v2)钱钱(v3)孙孙(v4)李李(v5)周周(v6)吴吴(v7)陈陈e2e1e3e4e5可见图论中的图与几何图、工程图是不一样的。可见图论中的图与几何图、工程图是不一样的。例如：例如：在一个人群中，对相

6、互认识相互认识这个关系我们可以用图来表示。定义定义:图中的点用点用v表示，边用表示，边用e表示。表示。对每条边 可用它所连接的点表示，记作：e1=v1,v1;e2=v1,v2;v3e7e4e8e5e6e1e2e3v1v2v4v5 端点端点,关联边关联边,相邻相邻 环环,多重边多重边,简单图简单图如果边e的两个端点相重，称该边为环环。如右图中边e1为环。如果两个点之间多于一条，称为多重边多重边，如右图中的e4和e5，对无环、无多重边的图无环、无多重边的图称作简单图简单图。v3e7e4e8e5e6e1e2e3v1v2v4v5 次，奇点，偶点，孤立点次，奇点，偶点，孤立点与某一个点vi相关联的边的数

7、目称为点vi的次次（也叫做度度），记作 d(vi)。右 图 中 d(v1),d(v3)=5,d(v5)=1。次为奇数的点称作奇点奇点，次为偶数的点称作偶偶点点，次为1的点称为悬挂点悬挂点，次为0的点称作孤立点孤立点。v3e7e4e8e5e6e1e2e3v1v2v4v5图的次图的次:一个图的次等于各点的次之和。一个图的次等于各点的次之和。链，圈，路、回路、连通图链，圈，路、回路、连通图v3e7e4e8e5e6e1e2e3v1v2v4v5链：链：图中保持关联关系的点和边的交替序列，其中点可重复，但边不能重复。路：路：点不能重复的链。圈：圈：起点和终点重合的链。回路：回路：起点和终点重合的路。连通图

8、：连通图：任意两点之间至少存在一条链的图。完全图：完全图：任意两点之间都有边相连的简单图。如图，如图，(v1,e1,v1,e2,v2,e6,v4,e7,v3)是一条链是一条链,但不是路；但不是路；(v1,e2,v2,e6,v4,e7,v3)是一条路是一条路(v1,e2,v2,e6,v4,e7,v3,e3,v1)是一个回路是一个回路(v1,e1,v1,e2,v2,e6,v4,e7,v3,e3,v1)是一个圈是一个圈本图是一个本图是一个连通图连通图。v3e7e4e8e5e6e1e2e3v1v2v4v5偶图（二分图）：偶图（二分图）：若图G的点集V可以分为两个互不相交的非空子集两个互不相交的非空子集

9、V1和V2，而且在同一个子集中的点均互不相邻，同一个子集中的点均互不相邻，则图G称为偶图。v1v3v5v2v4v6v1v2v3v4v1v4v2v3(a)(b)(c)(a)明显为二分图，(b)也是二分图，但不明显，改画为(c)时可以清楚看出。子图，部分图子图，部分图(支撑子图支撑子图)v3e7e4e8e5e6e1e2e3v1v2v4v5v3e4e8e5e6v2v4v5v3e7e4e8e6e2e3v1v2v4v5（G图）图）(a)(b)已知图G1=V1,E1,G2=V2,E2,若有V1 V2，E1 E2，则称G1是G2的一个子图子图；若V1=V2，E1 E2且且 E1E2，则称G1是G2的一个部分

10、图。部分图。网络（赋权图）网络（赋权图）设图G（V，E），对G的每一条边(vi,vj)相应赋予数量指标wij，wij称为边(vi,vj)的权权,赋予权的图G称为网网络络(或赋权图）或赋权图）。权可以代表距离、费用、通过能力(容量)等等。端点无序的赋权图称为无向网络无向网络，端点有序的赋权图称为有向网络。有向网络。910201571419256 出次与入次出次与入次 有向图中，以vi为始点的边数称为点vi的出次出次，用d+(vi)表示；以vi为终点的边数称为点vi 的入次入次，用表示d-(vi)；vi 点的出次和入次之和就是该点的次。有向图中，所有顶点的入次之和等于所有顶有向图中，所有顶点的入次

11、之和等于所有顶点的出次之和。点的出次之和。图模型的简单应用图模型的简单应用例例6.1 有甲有甲,乙乙,丙丙,丁丁,戊戊,己己6名运动员报名参加名运动员报名参加A,B,C,D,E,F 6个项目的比赛。下表中打个项目的比赛。下表中打的是各运的是各运动员报告参加的比赛项目。问动员报告参加的比赛项目。问6个项目的比赛顺序个项目的比赛顺序应如何安排，做到每名运动员都不连续地参加两项应如何安排，做到每名运动员都不连续地参加两项比赛。比赛。ABCDEF甲甲乙乙丙丙丁丁戊戊己己解：解：用图来建模。把比赛项目作为研究对象，用点表示。如果2个项目有同一名运动员参加，在代表这两个项目的点之间连一条线，可得下图。AB

12、CDEF在图中找到一个点序列，使得依次排列的两点不相邻，即能满足要求。如：如：1)A,C,B,F,E,D2)D,E,F,B,C,A一个班级的学生共计选修A、B、C、D、E、F六门课程，其中一部分人同时选修D、C、A，一部分人同时选修B、C、F，一部分人同时选修B、E，还有一部分人同时选修A、B，期终考试要求每天考一门课，六天内考完，为了减轻学生负担，要求每人都不会连续参加考试，试设计一个考试日程表。思考练习题思考练习题人有了知识，就会具备各种分析能力，人有了知识，就会具备各种分析能力，明辨是非的能力。明辨是非的能力。所以我们要勤恳读书，广泛阅读，所以我们要勤恳读书，广泛阅读，古人说古人说“书中自有黄金屋。书中自有黄金屋。”通过阅读科技书籍，我们能丰富知识，通过阅读科技书籍，我们能丰富知识，培养逻辑思维能力；培养逻辑思维能力；通过阅读文学作品，我们能提高文学鉴赏水平，通过阅读文学作品，我们能提高文学鉴赏水平，培养文学情趣；培养文学情趣；通过阅读报刊，我们能增长见识，扩大自己的知识面。通过阅读报刊，我们能增长见识，扩大自己的知识面。有许多书籍还能培养我们的道德情操，有许多书籍还能培养我们的道德情操，给我们巨大的精神力量，给我们巨大的精神力量，鼓舞我们前进鼓舞我们前进。