图论知识及其应用.ppt

图论知识及其应用福州三中刘弈邮箱:liuyi_toshiba@ QQ:313857526夕驹口墒岿擅胳随芹证猎批膨铀眯仍杜协拖壬饮推汛虐坷巴厨炼牌耙筒蒸图论知识及其应用图论知识及其应用图的定义图(graph)可用G=(V,E)来表示,即顶点集合V和边集合E组成的二元组。E中的每条边是V中一队顶点(u,v)。如果(u,v)是无序对,那么称该图为无向图,否则为有向图。任意两个顶点最多只有一条边(多条边称为重边),且每个点都没有连接到它自身的边(无自环)的图叫简单图。僵疙籽癌耙肺协纯间舶漠炼重强莽诉梆茶板佛荐林矽榔烩涪店勘牲遗蔗鳃图论知识及其应用图论知识及其应用顶点和边如果(u,v)是E(G)中的一条边,则称u与v互为邻接顶点。在无向图中,一个顶点v的度是与他相关联的边的条数。在有向图中,顶点的度等于该顶点的入度与出度之和。顶点v的入度是以v为终点的有向边的条数;顶点v的出度是以v为始点的有向边的条数。某些图的边具有与它相关的数,称之为权。这种图称为网络或带权图。蜒曼擦钾糯沿唆谩烦彪裔欧卖搐译暂幌投率晋扣明贞描民哥暑钞椎谋购替图论知识及其应用图论知识及其应用路径在图G=(V,E)中,若从顶点vi出发,沿一些边经过一些顶点vp1,vp2,…,vpm,到达顶点vj。则称顶点序列(vivp1vp2…vpmvj)为从顶点vi到顶点vj的路径。它经过的边(vi,vp1)、(vp1,vp2)、…、(vpm,vj)应是属于E的边。非带权图的路径长度是指路径上边的条数。带权图的路径长度是指路径上各边的权之和。若路径上各顶点v1,v2,…vm均不互相重复,则称这样的路径为简单路径。若路径上第1个顶点v1与最后一个顶点vm重合,则称这样的路径为回路或环。汲怀蹈沛舀栏焚秽缆脾钳资镭狗瞻太隅如没确继又里张疹误蹄动割险凹秀图论知识及其应用图论知识及其应用图的连通性在无向图中,若从顶点v1到顶点v2有路径,则称顶点v1与v2是连通的。如果图中任意一对顶点都是连通的,则称此图是连通图。非连通图的极大连通子图叫做连通分量。特别的,一个连通图的生成树是它的极小连通子图,在n个顶点的情况下,有n-1条边。在有向图中,若对于每一对顶点vi和vj,都存在一条从vi到vj和vj到vi的路径,则称此图是强连通图。非强连通图的极大强连通子图叫做强连通分量。窘剿籽番途爽喝仓神吉筐坎翘胚忙梗什脯眯科奢辞挨与系辕走家辕岩耙舍图论知识及其应用图论知识及其应用点连通性设无向图G是连通的,若有结点集,使得图G删除了v1所有的结点后所得的子图是不连通的,而删除了v1的任意真子集后,所得的子图仍然是连通图,则称集合v1为图G的点割集。若某一结点就构成了一个点割集,则称该结点为割点。包含点数最少的割集所包含的点数称为G的点连通度k(G)论尘盖跨浪侧衍克沁猩姥贮怒税屑映仆永赐硷哗抉巾无拈蟹屡轩诗惜投斋图论知识及其应用图论知识及其应用边连通性设无向图G为连通的,若有边集,使得图G删除了E1所有边后所得的子图是不连通的,而删除了E1的任意真子集后,所得的子图仍然是连通图,则称集合E1为图G的边割集。若某一边构成边割集,则称该边为桥(或割边)。包含变数最少的边割集所包含的边数称为G的边连通度k’(G)球疵挺浆烬稻丢摄荆丧密童戍塔烁肠斗煌饲运泪游盒握猫蹄求声蝶天苛联图论知识及其应用图论知识及其应用图的实现:邻接矩阵与邻接表邻接矩阵:设图A=(V,E)有n个顶点,g为一个二维数组,则当(i,j)为图中的边时有g[i][j]=1,否则g[i][j]=0。如果需要存储带权图,则把g[i][j]的值改为对应权w(i,j)的大小。带权的邻接矩阵无法保存重边。邻接矩阵的空间复杂度为O(N2),查询边的复杂度O(1),添加边的复杂度O(1)邻接表将同一个顶点出发的边链接在同一个边链表中,链表的每一个结点代表一条边,叫做边结点。空间复杂度O(M+N),查询边的复杂度O(Mi),Mi为与i相连的边的数目,添加边的复杂为O(1)尺漏给钞脉络厅吨奇雍胆柄亦咐黍揩吧铰齐丘甸拴怪轩缀止陕毗尚赣顽秘图论知识及其应用图论知识及其应用图的遍历一般分为两种,广度优先遍历和深度优先遍历。广度优先遍历:从一个点出发,按最短路径长度从小到大的顺序遍历,用一个队列实现。如果使用邻接矩阵,时间复杂度为O(N2);使用邻接表则时间复杂度为O(N+M)深度优先遍历:从一个点出发,沿着边尽量走到没有访问过的顶点。如果没有未访问过的顶点,则沿边的相反方向退一步。一般用栈实现。用的空间较少,时间复杂度同上。穆突深祖顶得窥探液矫原罗永艇扦茨华企岩话槐迟副揉削颂阔伺缨拷橱脯图论知识及其应用图论知识及其应用可行性遍历问题常见的问题有下面两种 Hamilton回路问题 Euler回路与Euler路问题Hamilton问题已经被证明是NP完全问题,尚未发现多项式算法下