例：一个无向连通图中有16条边，所有顶点的度均小于5度为4的顶点有3个，度为3的顶点有4个，度为2的顶点有2个则该图有个顶点。A.10B.11C.12D.13解：设该图有n个顶点，图中度为的顶点数为n：（0≤i<4），显然no=0，n=3+4+2+n,+no=9+n1，而度之和=4×3+3×4+2×2+n,=28+n1，而度之和=2e=32，所以有28+n,=32得n,=4，n=9+n,=13。本题答案为D。6
6 例．一个无向连通图中有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.完全图若无向图中的每两个顶点之间都存在着一条边，有向图中的每两个顶点之间都存在着方向相反的两条边，则称此3图为完全图。(a)显然，完全无向图包含有条n（n-1)/2边，完全有向图包含有n(n-1)条边。例如，图（a）所示的图是一个具有4个顶点的完全无向图，共有6条边。图（b）所示房的图是一个具有4个顶点的完全有向图共有12条边。3(b)
7 3. 完全图 若无向图中的每两个顶点之间都存 在着一条边，有向图中的每两个顶点之 间都存在着方向相反的两条边，则称此 图为完全图。 显然，完全无向图包含有条n(n-1)/2 边，完全有向图包含有n(n-1)条边。例 如，图(a)所示的图是一个具有4个顶点 的完全无向图，共有6条边。图(b)所示 的图是一个具有4个顶点的完全有向图， 共有12条边。 (b) 1 2 0 3 1 2 0 3 (a)
稀疏图14.稠密图当一个图接近完全图时，则称(a)0-为稠密图。相反，当一个图含有较少的边数（即当e<<n(n-1））时则称为稀疏图。5.子图(b)0设有两个图G-(V，E)和G'=(V’，E"），若V'是V的子集，即V'cV，且E'是E的子集，即E'E，则称G'是G的子图。例如图(b）是图(a）的子图，而图(c）不是图(a）的子图。(c)0注意：G中V的子集和E的子集并不一定构成G的子图8
8 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,i,i,.….,im），若此图G是无向图，则边(ii），（ij,i），….(im1im），（imi)属于E(G)若此图是有向图则<i,i>,<i,iz>，.….,<im1im>,<imj>属于E(G)。路径长度是指一条路径上经过的边的数自。若一条路径上除开始点和结束点可以相同外，其余顶点均不相同，则称此路径为简单路径。例如，有图中，（0，2，1)就是一条简单路径，其长度为2。O
9 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>，.，<im-1 ,im >，<im ,j>属于 E(G)。 路径长度是指一条路径上经过的边的数 目。若一条路径上除开始点和结束点可以相 同外，其余顶点均不相同，则称此路径为简 单路径。例如，有图中，(0，2，1)就是一条 简单路径，其长度为2。 1 2 0 3
7.回路或环若一条路径上的开始点与结束点为同一个顶点，则此路径被称为20回路或环。开始点与结束点相同的简单路径被称为简单回路或简单环例如，右图中，（0，2，1，0)就是一条简单回路，其长度为3。10
10 7. 回路或环 若一条路径上的开始点与结束 点为同一个顶点，则此路径被称为 回路或环。开始点与结束点相同的 简单路径被称为简单回路或简单环。 例如，右图中，(0，2，1，0)就 是一条简单回路，其长度为3。 1 2 0 3