《运筹学--图与网络1(qh)》由会员分享，可在线阅读，更多相关《运筹学--图与网络1(qh)（201页珍藏版）》请在金锄头文库上搜索。
1、第十章 图与网络分析,引言图论是专门研究图的理论的一门数学分支，属于离散数学范畴，与运筹学有交叉，它有200多年历史，大体可划分为三个阶段：第一阶段是从十八世纪中叶到十九世纪中叶，处于萌芽阶段，多数问题为游戏而产生，最有代表性的工作是所谓的Euler七桥问题(1736年)，即一笔画问题。,第二阶段是从十九世纪中叶到二十世纪中叶，这时，图论问题大量出现，如Hamilton问题，地图染色的四色问题以及可平面性问题等，这时，也出现用图解决实际问题，如Cayley把树应用于化学领域，Kirchhoff用树去研究电网络等.,第三阶段是二十世纪中叶以后，由生产管理、军事、交通、运输、计算机网络等方面提出实
2、际问题，以及大型计算机使大规模问题的求解成为可能，特别是以Ford和Fulkerson建立的网络流理论，与线性规划、动态规划等优化理论和方法相互渗透，促进了图论对实际问题的应用。,例10-1：哥尼斯堡七桥问题哥尼斯堡（现名加里宁格勒）是欧洲一个城市，Pregei河把该城分成两部分，河中有两个小岛，十八世纪时，河两边及小岛之间共有七座桥，当时人们提出这样的问题：有没有办法从某处（如A）出发，经过各桥一次且仅一次最后回到原地呢？,A,B,C,D,最后，数学家Euler在1736年巧妙地给出了这个问题的答案，并因此奠定了图论的基础，Euler把A、B、C、D四块陆地分别收缩成四个顶点，把桥表示成连接
3、对应顶点之间的边，问题转化为从任意一点出发，能不能经过各边一次且仅一次，最后返回该点。这就是著名的Euler问题。,A,C,B,D,例10-2：有7个人围桌而坐，如果要求每次相邻的人都与以前完全不同，试问不同的就座方案共有多少种？用顶点表示人，用边表示两者相邻，因为最初任何两个人都允许相邻，所以任何两点都可以有边相连。,1,2,3,7,6,4,5,假定第一次就座方案是 （1，2，3，4，5，6，7，1），那么第二次就座方案就不允许这些顶点之间继续相邻，只能从图中删去这些边。,1,2,3,7,6,4,5,1,2,3,7,6,4,5,1,2,3,7,6,4,5,1,2,3,7,6,4,5,1,2,
4、3,7,6,4,5,1,2,3,7,6,4,5,1,2,3,7,6,4,5,1,2,3,7,6,4,5,假定第二次就座方案是 （1，3，5，7，2，4，6，1），那么第三次就座方案就不允许这些顶点之间继续相邻，只能从图中删去这些边。,1,2,3,7,6,4,5,1,2,3,7,6,4,5,1,2,3,7,6,4,5,1,2,3,7,6,4,5,1,2,3,7,6,4,5,1,2,3,7,6,4,5,1,2,3,7,6,4,5,1,2,3,7,6,4,5,假定第三次就座方案是 （1，4，7，3，6，2，5，1），那么第四次就座方案就不允许这些顶点之间继续相邻，只能从图中删去这些边，只留下7点孤立
5、点，所以该问题只有三个就座方案。,1,2,3,7,6,4,5,1,2,3,7,6,4,5,1,2,3,7,6,4,5,1,2,3,7,6,4,5,1,2,3,7,6,4,5,1,2,3,7,6,4,5,1,2,3,7,6,4,5,1,2,3,7,6,4,5,例10-3：哈密顿（Hamilton）回路是十九世纪英国数学家哈密顿提出，给出一个正12面体图形，共有20个顶点表示20个城市，要求从某个城市出发沿着棱线寻找一条经过每个城市一次而且仅一次，最后回到原处的周游世界线路（并不要求经过每条边）。,一. 有甲、乙、丙、丁、戊、己6名运动员报名参加A，B，C，D，E，F,6项比赛。下表给出6个运动员
6、报名参加的比赛项目。问6个项目比赛顺序如何安排，做到每名运动员不连续参加两项比赛。,甲 乙 丙 丁 戊 己 ,A B C D E F,解:比赛项目作为点,两个比赛项目由同一个人参加连一边.如图:,A,B,D,F,C,E,比赛顺序可安排A-C-B-F-E-D 或A-F-B-C-D-E,甲 乙 丙 丁 戊 己 ,A B C D E F,10.1 图的基本概念图论是专门研究图的理论的一门数学分支，主要研究点和线之间的 几何关系。,定义：（图） 设G=（V，E，） 其中：V= （ v1， v2，. vm）是m个顶点集合；E= （ e1， e2，. en）是n条边集合。是描述边与顶点之间关系的函数,称G
7、=（V，E，）为 一个图，如果它满足： （1）V非空； （2）E是一个不与V 中顶点相交的边集合；（3）是关联函数。 V，E，称为图的三要素。,说明： （1）V非空，即没有顶点的图不讨论； （2）E无非空条件，即允许没有边； （3）条件（2）是指点只在边的端点处相交； （4）任一条边必须与一对顶点关联，反之不然。,v1,v3,v2,v4,v5,v1,v3,v2,v4,v5,有向图,v1,v3,v2,v4,v6,v5,e1,e3,e5,e6,e4,e8,e7,e2,例10-5,V= （ v1， v2，. v6） E= （ e1， e2，. e8） （e1）= （v1， v2） （e2）= （v1
8、， v2） （e7）= （v3， v5） （e8）= （v4， v4）,次（度）：与顶点关联的边数。 简单图：没有环和重边的图。 悬挂点：次为1的点。 悬挂边：次为1的边。 孤立点：次为0的点。 (e8)= (v4， v4),称为自回路(环)； v6是孤立点，v5为悬挂点，e7为悬挂边， 顶点v3的次为4，顶点v2的次为3。,定理1：在一个图中，所有顶点次的和等于边的两倍。,定理8-1：在一个图中，所有顶点次的和等于边的两倍。 定理2：在任意一个图中，奇顶点的个数必为偶数。 证明:设V1和V2分别为G中奇点和偶点的集合,定理8-1：在一个图中，所有顶点次的和等于边的两倍。 定理8-2：在任意一
9、个图中，奇顶点的个数必为偶数。 注意：一个图的形状并不唯一。但它的三要素是不能变的。,注意：一个图的形状并不唯一。但它的三要素是不能变的。 例如：这两个图均为K4,v1,v2,v3,v4,v1,v2,v3,v4,定义：设G=（V，E，）和G1=（V1，E1，1）。如果V1 V， E1 E则称G1为G的子图；如果G1=（V1，E1，1）是G=（V，E，）子图，并且V1= V，则称G1为G的生成子图；,如果V1 V， E1 是E中所有端点属于V1的边组成的集合，则称G1是G的关于V1的导出子图；如果G1=（V1，E1，1）是G=（V，E，）子图，并且V1= V，则称G1为G的生成（支撑）子图。,v
10、1,v5,v4,v2,v3,e1,e8,e7,e6,e5,e4,e3,e2,v1,v5,v4,v2,e1,e5,e3,（a）的子图,v1,v5,v4,v2,v3,e8,e6,e5,e2,（a）的生成子图,v1,v5,v4,v2,v3,e1,e8,e7,e6,e5,e4,e3,e2,v1,v5,v4,v2,e1,e8,e7,e6,e5,e4,e3,（a）的导出子图,定义（简单图）如果图中任意两个顶点之间至多有一条边，则称为简单图，否则称为多重图。即:无环、无重边的图。,定义（简单图）如果图中任意两个顶点之间至多有一条边，则称为简单图，否则称为多重图。 定义（有向图）如果图中每一条边都规定了方向，则称为有向图。有向图去掉箭头得到的图称为基础图。,
