《《图与网络分析》PPT课件》由会员分享，可在线阅读，更多相关《《图与网络分析》PPT课件（190页珍藏版）》请在金锄头文库上搜索。
1、第十一章第十一章 图与网络分析图与网络分析Graph theory and network analysis第十一章第十一章 图与网络分析图与网络分析11.1 11.1 引言引言引言引言图论是专门研究图的理论的一门数学分支，图论是专门研究图的理论的一门数学分支，属于离散数学范畴，与运筹学有交叉，它有属于离散数学范畴，与运筹学有交叉，它有200200多年历史，大体可划分为三个阶段。多年历史，大体可划分为三个阶段。引言引言第一阶段第一阶段 从十八世纪中叶到十九世纪中叶，处于从十八世纪中叶到十九世纪中叶，处于萌芽阶段萌芽阶段，多数问题由游戏而产生，最，多数问题由游戏而产生，最有代表性的工作是所谓的有
2、代表性的工作是所谓的EulerEuler七桥问七桥问题，即一笔画问题。题，即一笔画问题。引言引言第二阶段第二阶段 从十九世纪中叶到二十世纪中叶，这时，从十九世纪中叶到二十世纪中叶，这时，图论问题大量出现，如图论问题大量出现，如HamiltonHamilton问题，问题，地图染色的四色问题以及可平面性问题等，地图染色的四色问题以及可平面性问题等，这时，也出现用图解决实际问题，如这时，也出现用图解决实际问题，如CayleyCayley把树应用于化学领域，把树应用于化学领域，KirchhoffKirchhoff用树去研究电网络等用树去研究电网络等. .引言引言第三阶段第三阶段 二十世纪中叶以后，由生
3、产管理、军事、二十世纪中叶以后，由生产管理、军事、交通、运输、计算机网络等方面提出实际交通、运输、计算机网络等方面提出实际问题，以及问题，以及大型计算机使大规模问题的求大型计算机使大规模问题的求解成为可能解成为可能，特别是以，特别是以FordFord和和FulkersonFulkerson建立的网络流理论，与线性规划、动态规建立的网络流理论，与线性规划、动态规划等优化理论和方法相互渗透，促进了图划等优化理论和方法相互渗透，促进了图论对实际问题的应用。论对实际问题的应用。ABCD哥尼斯堡七桥问题哥尼斯堡七桥问题 哥尼斯堡七桥问题哥尼斯堡七桥问题 最最后后，数数学学家家EulerEuler在在17
4、361736年年巧巧妙妙地地给给出出了了这个问题的答案，并因此奠定了图论的基础这个问题的答案，并因此奠定了图论的基础EulerEuler把把A A、B B、C C、DD四四块块陆陆地地分分别别收收缩缩成成四四个个顶顶点点，把把桥桥表表示示成成连连接接对对应应顶顶点点之之间间的的边边，问问题题转转化化为为从从任任意意一一点点出出发发，能能不不能能经经过过各各边边一一次次且且仅仅一一次次，最最后后返返回回该该点点。这这就就是是著著名名的的EulerEuler问题。问题。ABCD哥尼斯堡七桥问题哥尼斯堡七桥问题 哥尼斯堡七桥问题哥尼斯堡七桥问题ACBD围坐问题围坐问题 有有7 7个个人人围围桌桌而而
5、坐坐，如如果果要要求求每每次次相相邻邻的的人人都都与与以以前前完完全全不不同同，试试问问不不同同的的就就座座方方案共有多少种？案共有多少种？用顶点表示人，用边表示两者相邻用顶点表示人，用边表示两者相邻，因，因为最初任何两个人都允许相邻，所以任为最初任何两个人都允许相邻，所以任何两点都可以有边相连。何两点都可以有边相连。1 12 23 37 76 64 45 5围坐问题围坐问题假定第一次就座方案是假定第一次就座方案是假定第一次就座方案是假定第一次就座方案是（1 1 1 1，2 2 2 2，3 3 3 3，4 4 4 4，5 5 5 5，6 6 6 6，7 7 7 7，1 1 1 1），），），）
6、，那那那那么么么么第第第第二二二二次次次次就就就就座座座座方方方方案案案案就就就就不不不不允允允允许许许许这这这这些些些些顶顶顶顶点点点点之之之之间间间间继继继继续相邻，只能从图中删去这些边。续相邻，只能从图中删去这些边。续相邻，只能从图中删去这些边。续相邻，只能从图中删去这些边。围坐问题围坐问题1 12 23 37 76 64 45 5围坐问题围坐问题1 12 23 37 76 64 45 5围坐问题围坐问题1 12 23 37 76 64 45 5围坐问题围坐问题1 12 23 37 76 64 45 5围坐问题围坐问题1 12 23 37 76 64 45 5围坐问题围坐问题1 12 2
7、3 37 76 64 45 5围坐问题围坐问题1 12 23 37 76 64 45 5围坐问题围坐问题1 12 23 37 76 64 45 5围坐问题围坐问题假定第二次就座方案是假定第二次就座方案是（1 1，3 3，5 5，7 7，2 2，4 4，6 6，1 1），），那那么么第第三三次次就就座座方方案案就就不不允允许许这这些些顶顶点点之之间间继续相邻继续相邻，只能从图中，只能从图中删去这些边删去这些边。围坐问题围坐问题1 12 23 37 76 64 45 5围坐问题围坐问题1 12 23 37 76 64 45 5围坐问题围坐问题1 12 23 37 76 64 45 5围坐问题围坐问
8、题1 12 23 37 76 64 45 5围坐问题围坐问题1 12 23 37 76 64 45 5围坐问题围坐问题1 12 23 37 76 64 45 5围坐问题围坐问题1 12 23 37 76 64 45 5围坐问题围坐问题1 12 23 37 76 64 45 5围坐问题围坐问题假定第三次就座方案是假定第三次就座方案是（1 1，4 4，7 7，3 3，6 6，2 2，5 5，1 1），那那么么第第四四次次就就座座方方案案就就不不允允许许这这些些顶顶点点之之间间继继续续相相邻邻，只只能能从从图图中中删删去去这这些些边边，只只留留下下7 7点点孤孤立立点点，所以该问题只有三个就座方案。
9、所以该问题只有三个就座方案。围坐问题围坐问题1 12 23 37 76 64 45 5围坐问题围坐问题1 12 23 37 76 64 45 5围坐问题围坐问题1 12 23 37 76 64 45 5围坐问题围坐问题1 12 23 37 76 64 45 5围坐问题围坐问题1 12 23 37 76 64 45 5围坐问题围坐问题1 12 23 37 76 64 45 5围坐问题围坐问题1 12 23 37 76 64 45 5围坐问题围坐问题1 12 23 37 76 64 45 5围坐问题围坐问题1 12 23 37 76 64 45 5围坐问题围坐问题假定第三次就座方案是假定第三次就座
10、方案是（1 1，4 4，7 7，3 3，6 6，2 2，5 5，1 1），那那么么第第四四次次就就座座方方案案就就不不允允许许这这些些顶顶点点之之间间继继续续相相邻邻，只只能能从从图图中中删删去去这这些些边边，只只留留下下7 7点点孤孤立立点点，所所以以该问题只有三个就座方案该问题只有三个就座方案。围坐问题围坐问题 哈哈密密顿顿（HamiltonHamilton）回回路路是是十十九九世世纪纪英英国国数数学学家家哈哈密密顿顿提提出出，给给出出一一个个正正1212面面体体图图形形，共共有有2020个个顶顶点点表表示示2020个个城城市市，要要求求从从某某个个城城市市出出发发沿沿着着棱棱线线寻寻找找
11、一一条条经经过过每每个个城城市市一一次次而而且且仅仅一一次次，最最后后回回到到原原处处的的周周游游世世界界线线路（并不要求经过每条边）。路（并不要求经过每条边）。哈密顿回路哈密顿回路哈密顿回路哈密顿回路哈密顿回路哈密顿回路哈密顿回路哈密顿回路哈密顿回路哈密顿回路哈密顿回路哈密顿回路哈密顿回路哈密顿回路哈密顿回路哈密顿回路哈密顿回路哈密顿回路哈密顿回路哈密顿回路哈密顿回路哈密顿回路哈密顿回路哈密顿回路哈密顿回路哈密顿回路哈密顿回路哈密顿回路哈密顿回路哈密顿回路哈密顿回路哈密顿回路哈密顿回路哈密顿回路哈密顿回路哈密顿回路哈密顿回路哈密顿回路引言引言瑞士数学家瑞士数学家 Euler Euler 在在
12、17361736年发表的一篇题为年发表的一篇题为“依据几何位置的解题方法依据几何位置的解题方法”的论文，有效的解决的论文，有效的解决了哥尼斯堡七桥问题，是有记载的第一篇图论论了哥尼斯堡七桥问题，是有记载的第一篇图论论文，文， EulerEuler被认为是图论的创始人被认为是图论的创始人。图论的第一本专著图论的第一本专著是匈牙利的是匈牙利的 O Konig O Konig写的写的“有有限图与无限图的理论限图与无限图的理论”，发表于，发表于19361936。从从17361736到到19361936，前后，前后200200年，总的来讲这一时年，总的来讲这一时期图论发展缓慢。期图论发展缓慢。直到直到2
13、020世纪中叶，电子计算机的发展和零散数学世纪中叶，电子计算机的发展和零散数学问题具有越来越重要的地位，使得图论得以迅速问题具有越来越重要的地位，使得图论得以迅速发展发展第十一章第十一章 图与网络分析图与网络分析11.1 11.1 引言引言11.2 11.2 图与网络的基本概念图与网络的基本概念11.2 图与网络的基本概念图与网络的基本概念 图论是专门研究图的理论的一门图论是专门研究图的理论的一门数学分支，主要研究点和线之间数学分支，主要研究点和线之间的几何关系的几何关系11.2 图与网络的基本概念图与网络的基本概念定义：定义：图是由点集图是由点集 V=V=（ v vi i ）和）和 V V
14、中元素的无序对的一个集中元素的无序对的一个集合合 E= E=（ e ek k ）所构成的二元组，记为）所构成的二元组，记为G=G=（V V，E E），），其中：其中：V= V= （ v v1 1， v v2 2，. v. vmm） 是是mm个顶点集合；个顶点集合； E= E= （ e e1 1， e e2 2，. e. en n） 是是n n条边集合。条边集合。 当当V V，E E为有限集合时，为有限集合时，GG称为有限图，否则称为称为有限图，否则称为无限图，本章只讨论无限图，本章只讨论有限图有限图。11.2 图与网络的基本概念图与网络的基本概念v1v1v3v3v2v2v4v4v6v6v5v5
15、e1e1e3e3e5e5e6e6e4e4e8e8e7e7e2e211.2 图与网络的基本概念图与网络的基本概念V= V= （ v v1 1， v v2 2，. v. v6 6）E= E= （ e e1 1， e e2 2，. e. e8 8）e e e e1 1 1 1 = = = = （v v v v1 1 1 1， v v v v2 2 2 2）e e e e2 2 2 2= = = = （v v v v1 1 1 1， v v v v2 2 2 2）e e e e7 7 7 7= = = = （v v v v3 3 3 3， v v v v5 5 5 5）e e e e8 8 8 8=
16、= = = （v v v v4 4 4 4， v v v v4 4 4 4）称为自回路称为自回路称为自回路称为自回路( (环环环环) )；11.2 图与网络的基本概念图与网络的基本概念说明：说明：（1 1）V V非空，即没有顶点的图不讨论；非空，即没有顶点的图不讨论；（2 2）E E无非空条件，即允许没有边；无非空条件，即允许没有边；（3 3）E E是一个不与是一个不与V V 中顶点相交的边集合；中顶点相交的边集合； （指点只在边的端点处相交）指点只在边的端点处相交）（4 4）任一条边必须与一对顶点关联，反之不然。）任一条边必须与一对顶点关联，反之不然。11.2 图与网络的基本概念图与网络的基本概念V= V= （ v v1 1， v v2 2，. v. v6 6）E= E= （ e e1 1， e e2 2，. e. e8 8）e e e e1 1 1 1 = = = = （v v v v1 1 1 1， v v v v2 2 2 2）e e e e2 2 2 2= = = = （v v v v1 1 1 1， v v v v2 2 2 2）e e e e7 7 7 7= = = =
