文档介绍：例245136G1图G1中:V(G1)={1,2,3,4,5,6}E(G1)={<1,2>,<2,1>,<2,3>,<2,4>,<3,5>,<5,6>,<6,3>}例157324G26图G2中:V(G2)={1,2,3,4,5,6,7}E(G1)={(1,2),(1,3),(2,3),(2,4),(2,5),(5,6),(5,7)}图的基本术语完全图:n个顶点的图中,每个顶点与其它n-1个顶点都有边有向完全图——n个顶点的有向图最大边数是n(n-1)无向完全图——n个顶点的无向图最大边数是n(n-1)/2权——与图的边或弧相关的数叫~网——带权的图叫~子图——如果图G(V,E)和图G‘(V’,E‘),满足:V’VE’E则称G‘为G的子图顶点的度无向图中,顶点的度为与每个顶点相连的边数有向图中,顶点的度分成入度与出度入度:以该顶点为头的弧的数目出度:以该顶点为尾的弧的数目路径——路径是顶点的序列V={Vi0,Vi1,……Vin},满足(Vij-1,Vij)E或<Vij-1,Vij>E,(1<jn)路径长度——沿路径边的数目或沿路径各边权值之和回路——第一个顶点和最后一个顶点相同的路径叫~简单路径——序列中顶点不重复出现的路径叫~简单回路——除了第一个顶点和最后一个顶点外,其余顶点不重复出现的回路叫~连通——从顶点V到顶点W有一条路径,则说V和W是连通的连通图——图中任意两个顶点都是连通的叫~连通分量——非连通图的每一个连通部分叫~()强连通图——有向图中,如果对每一对Vi,VjV,ViVj,从Vi到Vj和从Vj到Vi都存在路径,则称G是~:1出度:3顶点4入度:1出度:0例157324G26顶点5的度:3顶点2的度:4例157324G26例245136G1路径:1,2,3,5,6,3路径长度:5简单路径:1,2,3,5回路:1,2,3,5,6,3,1简单回路:3,5,6,3路径:1,2,5,7,6,5,2,3路径长度:7简单路径:1,2,5,7,6回路:1,2,5,7,6,5,2,1简单回路:1,2,3,1连通图例245136强连通图356例非连通图连通分量例245136有向树:一个有向图若只有一个顶点的入度为0,其余顶点的入度都为1,:由若干棵有向树组成,含图中全部顶点,(P160)例G12413例15324G2V1V2^^V4^V3^^V1V2V4^V5^V3数组表示法——表示顶点间相联关系的邻接矩阵定义:设G=(V,E)是有n1个顶点的图,G的邻接矩阵A是具有以下性质的n阶方阵例G12413例15324G2特点:无向图的邻接矩阵对称,可压缩存储;有n个顶点的无向图需存储空间为n(n+1)/2有向图邻接矩阵不一定对称;有n个顶点的有向图需存储空间为n²无向图中顶点Vi的度TD(Vi)是邻接矩阵A中第i行(或第i列)元素之和有向图中,顶点Vi的出度OD(vi)是A中第i行元素之和顶点Vi的入度ID(vi)是A中第i列元素之和网络的邻接矩阵可定义为: