本章主要内容.ppt

、=<V,E>,E中每条边是V中一对顶点(u,v)间的联系,如果是无序对,那么称该图为无向图,否则为有向图。完全图、稠密图和稀疏图邻接点及关联边邻接点:边的两个顶点互为邻接点关联边:若有边e=(v,u),则称顶点v、u关联边e关联边:若有边e=(v,u),则称顶点v、(续)顶点的度、入度和出度顶点V的度=与V相关联的边的数目在有向图中:顶点V的出度=以V为起点有向边数顶点V的入度=以V为终点有向边数顶点V的度=V的出度+V的入度设图G的顶点数为n,边数为e图的所有顶点的度数之和=2*e(每条边对图的所有顶点的度数和“贡献”2度)(续)路径、回路在图G=<V,E>中,若有顶点序列v1,v2,…,vk,且<vi,vi+1>E(有向图)或(vi,vi+1)E(无向图),其中i=1,2,…k-1,v=v1,u=vk,则称该序列是从顶点v到顶点u的路径;若v=u,则称该序列为回路。简单路径、简单回路在一条路径中,除起点和终点外,若其余顶点各不相同,则称该路径为简单路径。由简单路径组成的回路称为简单回路。例如在上面的无向图中,V0,V1,V2,V3是简单路径V0,V1,V2,V4,V1不是简单路径;在上面的有向图中,V0,V2,V3,V0是简单回路。(续)连通图、强连通图在无(有)向图G=<V,E>中,若对任何两个顶点u、v都存在从u到v的路径,则称G是连通图(强连通图)。(b)非连通图V0V1V2V3(c)强连通图(a)连通图V0V3V2V1V4V5(d)(续)连通分量、强连通图分量在无(有)向图G=<V,E>中,若对任何两个顶点u、v都存在从u到v的路径,则称G是连通图(强连通图)。非连通图,(续)生成树一个连通图的生成树是一个极小连通子图,它含有图中全部顶点,但只有足以构成一棵树的n-1条边。(a)连通图G1V0V4V3V1V2(b)(续):(续):赋权图546132415102**********(续):有向图的强连通子图54613241510215203041010132415220546洒占绚鸭晃诌巷秽光货蓉凶硅胜的坤鲜宽屹诀滔拎源撇***梢砰省绰钵眷钓本章主要内容本章主要内容