为终点的边的数目和?出度——以该顶点为起点的边的数目和 度数为奇数的顶点叫做奇点,度数为偶数的点叫做偶点。3、顶点的度4、 路径和连通集在图G=(V,E)中,如果对于结点a,b,存在满足下述条件的结点序列x1……xk(k>1)⑴x1=a,xk=b⑵(xi,xi+1)∈Ei=1‥k-1则称结点序列x1=a,x2,…,xk=b为结点a到结点b的一条路径,而路径上边的数目k-1称为该路径的长度,并称结点集合{x1,…,xk}为连通集。{V1,v2,v5,v4}5、简单路径和回路如果一条路径上的结点除起点x1和终点xk可以相同外,其它结点均不相同,则称此路径为一条简单路径。图(a)中v1→v2→v3是一条简单路径,v1→v3→v4→v1→v3不是简单路径。x1=xk的简单路径称为回路(也称为环)。例如图(b)中,v1→v2→v1为一条回路。二、图的存储结构图的相邻矩阵表示法相邻矩阵是表示结点间相邻关系的矩阵。若G=(V,E)是一个具有n个结点的图,则G的相邻矩阵是如下定义的二维数组a,其规模为n*n1(或权值) 表示顶点i和顶点j有边(i和j的路程)A(i,j)={ 0表示顶点i和顶点j无边上图中的图G1和图G2对应的相邻矩阵分别为:邻接矩阵的特点:1)无向图的相邻矩阵是对称的,而有向图则不是。2)相邻矩阵方便度数的计算。用相邻矩阵表示图:?(1)容易判定任意两个结点之间是否有边相联;?(2)并容易求得各个结点的度数。?(对于无权无向图的相邻矩阵,第i行元素值的和就是Vi的度数;对于无权有向图的相邻矩阵,第i行元素值的和就是Vi的出度,第i列元素值的和就是Vi的入度;)对于有权无向图的相邻矩阵,第i行(或第i列)中元素值<>0的元素个数就是Vi的度数;对于有权有向图的相邻矩阵,第i行中元素值<>0的元素个数就是Vi的出度;第i列元素值<>0的元素个数就是Vi的入度。
全文预览
