《图与网络分析》PPT课件(I)

《《图与网络分析》PPT课件(I)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、图与网络分析引言第一节图与网络的基本概念第二节树第三节最短路径问题第四节网络最大流问题第五节最小费用最大流问题引言第一阶段从十八世纪中叶到十九世纪中叶游戏产生,代表工作Konigsber七桥问题第二阶段从十九世纪中叶到二十世纪中叶问题大量出现,Hamilton问题;地图四色问题;36年,Konig第一本图论问世第三阶段二十世纪中叶以后Ford和Fulkerson建立的网络流理论图论发展的三个阶段图论(GraphTheory)是研究图的理论,是运筹学中一重要的分支.有200多年历史,大体可划分为三个阶段.目前图论与网络流理论被广泛应用于管理

2、科学、计算机科学、信息论、控制论、物理、化学、生物学、心理学等各个领域.例1:Konigsber七桥问题Konigsber是欧洲一个城市,Pregei河把该城分成两部分,河中有两个小岛,十八世纪时,河两边及小岛之间共有七座桥,当时人们提出这样的问题:ABCDKonigsberPregeiRiver图－1有没有办法从某处(如A)出发,经过各桥一次且仅一次最后回到原地呢？？1235467Euler在1736年发表了一篇题为“依据几何位置的解题方法”论文,有效解决了Konigsber七桥难题,这是有记载的第一篇图论论文,Euler也被公认为图论

3、的创始人.CDAB给出一个正12面体图形,共有20个顶点,分别表示全球20个主要城市,要求从某个城市出发沿着棱线寻找一条经过每个城市一次而且仅一次,最后回到原处的周游世界线路(并不要求经过每条边).－环球旅行问题.例2:Hamilton回路是19世纪英国数学家Hamilton提出图－4伦敦例3:一个班级的学生共计选修A、B、C、D、E、F六门课程,其中一部分人同时选修A、C、D,一部分人同时选修B、C、F,一部分人同时选修B、E,还有一部分人同时选修A、B,期终考试要求每天考一门课,六天内考完,为了减轻学生负担,要求每人都不会连续参加考试

4、,试设计一个考试日程表.A、C、DB、C、FB、EA、BAFEDCB图－5解:以每门课程为一个顶点,共同被选修的课程之间用边相连,得图－5.按题意,相邻顶点对应课程不能连续考试,不相邻顶点对应课程允许连续考试,因此作图－5的补图(图-6).AFEDCB图－6图－7问题是在图－7中寻找一条经过每个顶点一次且仅一次的路线(Hamilton回路).AFEDCB如C—E—A—F—D—BC是一Hamilton回路AFEDCBC—E—A—F—D—BC,就是一个符合要求的考试课程安排.图－8第一节图与网络的基本概念一、图与网络的基本概念1、图及其分类定

5、义1:由点集V={vi}和V中的元素的无序对的一个集合E={ek}所构成的二元组称为图(Graph),记为G=(V,E).V中的元素vi叫做顶点,E中的元素叫做边.当V,E为有限集合时,G称为有限图,否则,称为无限图.图是由一些点及一些点之间的联线(不带箭头或带箭头)的组成的.例4在图9中,V={v1,v2,v3,v4,v5,v6},E={e1,e2,e3,e4,e5,e6,e7,e8}.其中:e1=[v1,v2]e2=[v1,v2]e3=[v2,v3]e4=[v3,v4]e5=[v4,v1]e6=[v1,v3]e7=[v3,v5]e8=

6、[v4,v4]图－9v1v3v2v4v6v5e1e3e5e6e4e8e7e2定义4:若图G=(V,E)的点集V可分为两个非空子集X,Y,满足:XY=V,XY=,使得E中的每条边的两上顶点必有一个端点属于X,而另一个端点Y,则称G为二部图(偶图)v1v3v2v4e1e2e4e3v1v2v3v4v5U1U2U3U4图－113、子图定义7设G=(V,E)和G1=(V1,E1).若V1V,E1E则称G1为G的子图;若G1=(V1,E1)是G=(V,E)的子图,且V1=V,则称G1为G的生成子图(支撑子图)若G1=(V1,E1)是G=(V

7、,E)的子图,且V1V,E1是E中所有端点属于V1的边组成的集合,则称G1是G的关于V1的导出子图v2e6v1v5v4v3e1e8e7e5e4e3e2图G=(V,E)v1v5v4v2e1e5e3(a)G的子图v1v5v4v2v3e8e6e5e2G的生成子图v1v5v2e1e6e5G的导出子图4、网络定义由点或边带有某种数量的指标的图称为网络与无向图相对应的网络称为无向网络与有向图相对应的网络称为有向网络二、连通图定义8无向图G=(V,E),若图G中某些点与边的交替序列可以排成的形成,且,则称这个点边序列为连接的一条链(chain),链长

8、为k.若点边列中没有重复的点与重复边者称为初等链定义9无向图G=(V,E),连接的一条链是同一个点时,称为圈(circle).若圈中没有重复的点与重复边者称为初等圈定义(链)如果图中的某些点、