运筹学图与网络分析(2).ppt

《运筹学图与网络分析(2).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、图与网络分析(GraphTheoryandNetworkAnalysis)图与网络的基本知识最短路问题树及最小树问题最大流问题哥尼斯堡七桥问题哥尼斯堡（现名加里宁格勒）是欧洲一个城市，Pregei河把该城分成两部分，河中有两个小岛，十八世纪时，河两边及小岛之间共有七座桥，当时人们提出这样的问题：有没有办法从某处（如A）出发，经过各桥一次且仅一次最后回到原地呢？BDACABCD哥尼斯堡七空桥一笔画问题哈密尔顿（Hamilton）回路是十九世纪英国数学家哈密顿提出，给出一个正12面体图形，共有20个顶点表示20个城市，要求从某个城市出发沿着棱线寻找一条经过每个城市一次而且仅一次，最后回到原处

2、的周游世界线路（并不要求经过每条边）。有7个人围桌而坐，如果要求每次相邻的人都与以前完全不同，试问不同的就座方案共有多少种？用顶点表示人，用边表示两者相邻，因为最初任何两个人都允许相邻，所以任何两点都可以有边相连。12376451237645123764512376451237645123764512376451237645得到第一次就座方案是（1，2，3，4，5，6，7，1），继续寻求第二次就座方案时就不允许这些顶点之间继续相邻，因此需要从图中删去这些边。12376451237645123764512376451237645123764512376451237645得出第二次就座方案是

3、（1，3，5，7，2，4，6，1），那么第三次就座方案就不允许这些顶点之间继续相邻，只能从图中删去这些边。12376451237645123764512376451237645123764512376451237645得到第三次就座方案是（1，4，7，3，6，2，5，1），那么第四次就座方案就不允许这些顶点之间继续相邻，只能从图中删去这些边，只留下7点孤立点，所以该问题只有三个就座方案。1237645引论图的用处某公司的组织机构设置图总公司分公司工厂或办事处一、图与网络的基本知识（一）、图与网络的基本概念EADCB1、一个图是由点和连线组成。（连线可带箭头，也可不带，前者叫弧，后者叫边）

4、v1v2v3v4v5v6e1e2e3e4e5e6e7e8e9e10例图1一个图是由点集和中元素的无序对的一个集合构成的二元组，记为G=(V，E)，其中V中的元素叫做顶点，V表示图G的点集合；E中的元素叫做边，E表示图G的边集合。{}jvV=2、不带箭头的连线叫做边。如果一个图是由点和边所构成的，则称其为无向图，记作G=(V，E)，连接点的边记作[vi,vj]，或者[vj,vi]。3、若点与点之间的连线有方向，称为弧。如果一个图是由点和弧所构成的，那么称它为有向图，记作D=(V,A)，其中V表示有向图D的点集合，A表示有向图D的弧集合。一条方向从vi指向vj的弧，记作(vi,vj)。v4v

5、6v1v2v3v5V={v1,v2,v3,v4,v5,v6}，A={(v1,v3),(v2,v1),(v2,v3),(v2,v5),(v3,v5),(v4,v5),(v5,v4),(v5,v6)}图24、一条边的两个端点是相同的,那么称这条边是环。5、如果两个端点之间有两条以上的边，那么称它们为多重边。6、不含环和多重边的图称为简单图；有多重边的图称为多重图。7、每一对顶点间都有边相连的无向简单图称为完全图。有向完全图则是指任意两个顶点之间有且仅有一条有向边的简单图。v1v2v3v4v5v6e1e2e3e4e5e6e7e8e9e10次为零的点称为弧立点，次为1的点称为悬挂点。悬挂点的关联

6、边称为悬挂边。次为奇数的点称为奇点，次为偶数的点称为偶点。8、以点v为端点的边的个数称为点v的次，记作。图中d(v1)=4，d(v6)=4（环计两次）定理1所有顶点次数之和等于所有边数的2倍。定理2在任一图中，奇点的个数必为偶数。所有顶点的入次之和等于所有顶点的出次之和。有向图中，以vi为始点的边数称为点vi的出次，用表示；以vi为终点的边数称为点vi的入次，用表示；vi点的出次和入次之和就是该点的次。9、设G=（V，E），G′=（V′,E′）如果V′V,E′E，称G′是G的子图；如果V′=V,E′E，称G′是G的生成子图或支撑子图。v1v2v3v4v5v6v7e1e2e3e4e5

7、e6e7e8e9e10e11(a)e5e7v1v2v5v6v7e1e6e8(b)子图v1v2v3v4v5v6v7e1e6e7e9e10e11(c)支撑子图在实际应用中，给定图中每条边，对应一个数，称之为“权”。通常把这种赋权的图称为网络。10、由两两相邻的点及其相关联的边构成的点边序列称为链。如:v0，e1，v1，e2，v2，e3，v3,…,vn-1,en，vn，e3v1v2v3v4v5v6e7e8e1e2e4e5e6e9e1011