2.顶点的度、入度和出度 在无向图中,顶点所具有的边的数 目称为该顶点的度。 在有向图中,以顶点终点的入边 的数目,称为该顶点的入度。以项点为 始点的出边的数目,称为该顶点的出度 一个顶点的入度与出度的和为该顶点的 若一个图中有n个顶点和e条边,每 个顶点的度为d,(I≤还n),则有:
2. 顶点的度、入度和出度 在无向图中，顶点所具有的边的数 目称为该顶点的度。 在有向图中，以顶点i为终点的入边 的数目，称为该顶点的入度。以顶点i为 始点的出边的数目，称为该顶点的出度。 一个顶点的入度与出度的和为该顶点的 度。 若一个图中有n个顶点和e条边，每 个顶点的度为di（1≤i≤n），则有： = n i i e d 1 2 1 ＝ 1 2 3 0 4 (a) 1 2 3 0 4 (b)
例71一个无向连通图中有16条边,所有顶点的度均小于5, 度为4的顶点有3个,度为3的顶点有4个,度为2的顶点有2个, 则该图有个顶点。 A.10 B 11 C.12 D.13 解:设该图有n个顶点,图中度为的顶点数为吗 (0≤i≤4),显然n=0,n=3+42+n1+n=9+m1,而度之和 =4x3+3×4+2×2+n1=28+n1,而度之和=2e=32,所以有 28+n1=32,得m1=4,n=9+n1=13。本题答案为D
例7.1 一个无向连通图中有16条边，所有顶点的度均小于5， 度为4的顶点有3个，度为3的顶点有4个，度为2的顶点有2个， 则该图有 个顶点。 A.10 B.11 C.12 D.13 解：设该图有n个顶点，图中度为i的顶点数为ni （0≤i≤4），显然n0=0，n=3+4+2+n1+n0=9+n1，而度之和 =4×3+3×4+2×2+n1=28+n1，而度之和=2e=32，所以有 28+n1=32，得n1=4，n=9+n1=13。本题答案为D
3完全图 若无向图中的每两个顶点之间都存 2 0 在着一条边,有向图中的每两个顶点之 间都存在着方向相反的两条边,则称此 图为完全图。 3 显然,完全无向图包含有条边,完 全有向图包含有n(n-1)条边。例如,图 (a所示的图是一个具有4个顶点的完全 无向图,共有6条边。图(b所示的图是 一个具有4个顶点的完全有向图,共有 0 12条边。 3 (b)
3. 完全图 若无向图中的每两个顶点之间都存 在着一条边，有向图中的每两个顶点之 间都存在着方向相反的两条边，则称此 图为完全图。 显然，完全无向图包含有条边，完 全有向图包含有n(n-1)条边。例如，图 (a)所示的图是一个具有4个顶点的完全 无向图，共有6条边。图(b)所示的图是 一个具有4个顶点的完全有向图，共有 12条边。 (b) 1 2 0 3 1 2 0 3 (a)
4.稠密图、稀疏图 当一个图接近完全图时,则称 3 0 为稠密图。相反,当一个图含有 较少的边数(即当e<m(m-1))时, 4 则称为稀疏图。 5.子图 设有两个图G=(V,E)和(2 3 0)(b) G=(V,E),着V是Ⅴ的子集, 即VcV,且E是E的子集,即 E’E,则称G是G的子图。例如 图(b是图(a)的子图,而图(c)不是 图(a)的子图 2 3 0 注意:G中V的子集和E的子集并 不一定构成G的子图
4 . 稠密图 、稀疏图 当一个图接近完全图时 ，则称 为稠密图 。相反 ，当一个图含有 较少的边数 （即当e<< n ( n - 1 ) ） 时 ， 则称为稀疏图 。 5 . 子图 设有两个图 G=(V ， E) 和 G’=(V’ ，E’) ， 若V’ 是 V的子集 ， 即V’ V ， 且E’ 是 E的子集 ， 即 E’ E ，则称G’ 是 G 的子图 。例如 图(b)是图(a)的子图 ，而图(c)不是 图(a)的子图 。 (a) 1 2 3 0 41 2 3 0 4 (b) 1 2 3 0 4 (c) 注意： G 中 V的子集和 E的子集并 不一定构成 G的子图
6.路径和路径长度 在一个图G=(V,E中,从顶点倒顶忘 的一条路径是一个顶点序列(i;12…,im 着此图G是无向图,则边(i,i),(1),… (m1in),(n)属于E(G);若此图是有向图, 则,1>,…,可m1>3,m→>属于(2 E(G)。 路径长度是指一条路径上经过的边的数 目。若一条路径上除开始点和结束点可以相 同外,其余顶点均不相同,则称此路径为简 单路径。例如,有图中,(0,2,1)就是一条 简单路径,其长度为2
6 . 路径和路径长度 在一个图G=(V ，E) 中 ，从顶点 i到顶点j 的一条路径是一个顶点序列 ( i , i 1 , i 2 , … , im ,j) ， 若此图 G是无向图 ，则边 ( i , i 1 ) ， ( i 1 , i 2 ) ， … ， ( im - 1 , im ) ， ( im ,j)属于E(G)；若此图是有向图 ， 则 < i , i 1 > ， < i 1 , i 2 > ， … ， < i m - 1 , im > ， < i m ,j >属于 E(G) 。 路径长度是指一条路径上经过的边的数 目 。若一条路径上除开始点和结束点可以相 同外 ，其余顶点均不相同 ，则称此路径为 简 单路径 。例如 ，有图中 ， ( 0 ， 2 ， 1 )就是一条 简单路径 ，其长度为 2 。 1 2 0 3