第一节图的基本概念 U2 V1 3 5 U6Q ○U3 0 V2 V4 V6 U5 U4 (1) (2) 图8-6两个同样的图 与顶点v关联的边数称为点v的次数，记为 dw)。图8-5中dy)=1,d2)=5,d(3)=4, d(v4=3,dvs)=3,d(y6)=0。 18
18 第一节 图的基本概念 与顶点v关联的边数称为点v的次数，记为 d(v)。图8-5中d(v1 )＝l，d(v2 )＝5，d(v3 )＝4， d(v4 )=3，d(v5 )＝3，d(v6 ) = 0。 图8-6 两个同样的图
第一节图的基本概念 次数为零的点称为孤立点，如图85中的v。 次数为奇数的点称为奇点，如图85中的y1, 次数为偶数的点称为偶点，如图85中的y3, 6 有关图中顶点数n,顶点的次数和边数m之间 的关系有如下两个基本定理 定理1任一图的顶点次数之和等于边数的二倍。 如果边数为m,则有 ∑d(y:)=2m i=1 19
19 第一节 图的基本概念 次数为零的点称为孤立点，如图8-5中的v6。 次数为奇数的点称为奇点，如图8-5中的v1，v2。 次数为偶数的点称为偶点，如图8-5中的v3，v6。 有关图中顶点数n，顶点的次数和边数m之间 的关系有如下两个基本定理。 定理1 任一图的顶点次数之和等于边数的二倍。 如果边数为m，则有： d v m n i ( i ) 2 1 = =
第一节图的基本慨念 定理的结论是明显的，因为计算顶点次数时 每一边都用了二次，所以次数和为边数的二倍。 定理2任一图中奇点的个数必为偶数。 证：设V,和V,分别为图中奇点和偶点的集 合，由前一定理有： 2m= ∑d(y)=∑d(y)+∑d(v) i=l vieV i∈'V2 因为上式最后一项是偶数，总和又是偶数。 所以奇点次数之和（倒数第二项）也只能是偶数。 20
20 第一节 图的基本概念 定理的结论是明显的，因为计算顶点次数时 每一边都用了二次，所以次数和为边数的二倍。 定理2 任一图中奇点的个数必为偶数。 证： 设V1和V2分别为图中奇点和偶点的集 合，由前一定理有： = = = + 1 2 2 ( ) ( ) ( ) 1 v V i v V i n i i i i m d v d v d v 因为上式最后一项是偶数，总和又是偶数。 所以奇点次数之和(倒数第二项)也只能是偶数
第一节图的基本慨念 只有偶数个奇数之和才能为偶数。故，奇点 的个数必为偶数 在图G中，从一个顶点出发，经过边、点、 边、点，到达某一点，称为G中的一条链。 我们可用经过这条链的顶点（或边）表示这条链。 如图8-7中(V1, V2, V3,V4 V5,V6)是一条链，也 可表示为(e1,e3,e4,e7)。 本章中我们只讨论没 有重复边的链，即简单链。 简单链也可称为通路 简称路 21
21 第一节 图的基本概念 只有偶数个奇数之和才能为偶数。故，奇点 的个数必为偶数。 在图G中，从一个顶点出发，经过边、点、 边、.、点，到达某一点，称为G中的一条链。 我们可用经过这条链的顶点(或边)表示这条链。 如图8-7中(v1，v2，v3，v4，v5，v6 )是一条链，也 可表示为(e1，e3，e4，e7 )。本章中我们只讨论没 有重复边的链，即简单链。简单链也可称为通路， 简称路
第一节图的基本概念 在一个图中，若任意两点之间至少存在一条 链，则称该图为连通图。否则称为不连通图，如 图8-7就是不连通图，但图8-7的左边（或右边）的图 就是一个连通图。 3 v4 v9 e5 e6 e8 e3 e4 el e2 e7 e9 v2 v5 v6 v7 v8 图8-7两个连通图 22
22 第一节 图的基本概念 在一个图中，若任意两点之间至少存在一条 链，则称该图为连通图。否则称为不连通图，如 图8-7就是不连通图，但图8-7的左边(或右边)的图， 就是一个连通图。 图8-7 两个连通图