图与网络模型

《图与网络模型》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、图与网络模型一、图的基本概念定义1：一个有序二元组(V,E)称为一个图,记为G=(V,E),其中V称为G的顶点集,V≠,其元素称为顶点或结点,简称点;E称为G的边集,其元素称为边,它联结V中的两个点,如果这两个点是无序的,则称该边为无向边,否则,称为有向边.如果E的每一条边都是无向边,则称G为无向图;如果E的每一条边都是有向边,则称G为有向图;否则,称G为混合图.如果V={v1,v2,…,vn}是有限非空点集,则称G为有限图或n阶图.一、图的基本概念记V={v1,v2,…,vn},

2、V

3、=n;E={e1,e2,…,em}(ek=vivj

4、),

5、E

6、=m.称点vi,vj为边vivj的端点.在有向图中,称点vi,vj分别为边vivj的始点和终点.有边联结的两个点称为相邻的点,有一个公共端点的边称为相邻边.边和它的端点称为互相关联.常用d(v)表示图G中与顶点v关联的边的数目,d(v)称为顶点v的度数.用N(v)表示图G中所有与顶点v相邻的顶点的集合.一、图的基本概念有限简单图(1)顶点个数是有限的;(2)任意一条边有且只有两个不同的点与它相互关联;(3)若是无向图,则任意两个顶点最多只有一条边与之相联结;(4)若是有向图,则任意两个顶点最多只有两条边与之相联结.当两个顶点有两

7、条边与之相联结时，这两条边的方向相反.如果某个有限图不满足(2)(3)(4),可在某条边上增设顶点使之满足.一、图的基本概念定义2：若将图G的每一条边e都对应一个实数F(e),则称F(e)为该边的权,并称图G为赋权图(网络),记为G=(V,E,F).定义3：设G=(V,E)是一个图,v0,v1,…,vk∈V,且1≤i≤k,vi-1vi∈E,则称v0v1…vk是G的一条通路.如果通路中没有相同的边,则称此通路为道路.始点和终点相同的道路称为圈或回路.如果通路中既没有相同的边,又没有相同的顶点,则称此通路为路径,简称路.定义4：任意两点均有

8、通路的图称为连通图.定义5：连通而无圈的图称为树,常用T表示树.二、图的矩阵表示邻接矩阵：邻接矩阵表示了点与点之间的邻接关系.一个n阶图G的邻接矩阵A=(aij)n×n,其中二、图的矩阵表示权矩阵一个n阶赋权图G=(V,E,F)的权矩阵A=(aij)n×n,其中二、图的矩阵表示关联矩阵一个有m条边的n阶有向图G的关联矩阵A=(aij)n×m,其中若vi是ej的始点;若vi是ej的终点;若vi与ej不关联.二、图的矩阵表示边权矩阵起点1123344终点2431413权6873245起点11123终点23434权63472三、最短路定义1设P

9、(u,v)是赋权图G=(V,E,F)中从点u到v的路径,用E(P)表示路径P(u,v)中全部边的集合,记，则称F(P)为路径P(u,v)的权或长度(距离).定义2若P0(u,v)是G中连接u,v的路径,且对任意在G中连接u,v的路径P(u,v)都有F(P0)≤F(P),则称P0(u,v)是G中连接u,v的最短路.三、最短路若v0v1…vm是图G中从v0到vm的最短路,则1≤k≤m,v0v1…vk必为G中从v0到vk的最短路.即：最短路是一条路，且最短路的任一段也是最短路.求非负赋权图G中某一点到其它各点最短路，一般用Dijkstra标号

10、算法；求非负赋权图上任意两点间的最短路，一般用Floyd算法.这两种算法均适用于有向非负赋权图.最短路的应用（截断切割问题）四、最小生成树由树的定义不难知道,任意一个连通的p,q图(p个顶点q条边)G适当去掉q-p+1条边后,都可以变成树,这棵树称为图G的生成树.设T是图G的一棵生成树,用F(T)表示树T中所有边的权数之和,F(T)称为树T的权.一个连通图G的生成树一般不止一棵,图G的所有生成树中权数最小的生成树称为图G的最小生成树.最小生成树常用算法有Prim算法和Krukal算法五、匹配问题定义1设X,Y都是非空有限集,且X∩Y=,

11、E{xy

12、x∈X,y∈Y},称G=(X,Y,E)为二部图.如果X中的每个点都与Y中的每个点邻接,则称G=(X,Y,E)为完备二部图.若F：E→R+,则称G=(X,Y,E,F)为二部赋权图.二部赋权图的权矩阵一般记作A=(aij)

13、X

14、×

15、Y

16、,其中aij=F(xiyj).五、匹配问题定义2设G=(X,Y,E)为二部图,且ME.若M中任意两条边在G中均不邻接,则称M是二部图G的一个匹配.定义3设M是二部图G的一个匹配,如果G的每一个点都是M中边的顶点,则称M是二部图G的完美匹配；如果G中没有另外的匹配M0,使

17、M0

18、＞

19、M

20、,则称M是二

21、部图G的最大匹配.在二部赋权图G=(X,Y,E,F)中,权数最大的最大匹配M称为二部赋权图G的最佳匹配.显然,每个完美匹配都是最大匹配,反之不一定成立六、最大流定义1设G=(V,E)为有向图,