第1节图的基本概念 有向图的例子 V={,"2r,",n,n,n A={a1,a2,a3,a4,a5,…,a1 其中 (v,n).a2=(n)a3=(v,n)a=(y,,a=(,n a=(,l),a=(,),a=(y,n),a=(y,),am=(v) 1 C 有向图 11 图10-8 清华大学出版社5
第1节 图的基本概念 v 有向图的例子 V v1 ,v2 ,v3 ,v4 ,v5 ,v6 ,v7, A a1 ,a2 ,a3 ,a4 ,a5 ,,a11 其中 1 2 3 3 3 4 3 4 5 2 4 6 5 7 4 6 8 5 3 9 5 10 5 6 11 6 7 , 1 2 1 2 4 4 a = v ,v ,a = v ,v ,a = v ,v ,a = v ,v ,a = v ,v , a = v ,v ,a = v ,v ,a = v ,v ,a v ,v a = v ,v , a = v ,v 有向图 图10-8 清华大学出版社 12
第1节图的基本概念 今图的重要概念(续) 图G或D中的点数记为pG或p(D),边(弧)数记为q(G(q(①), 分别简记为p,q。 o无向图G=(V,E)常用的一些名词和记号 o若边e=[u,v]∈E,则称u,v是e的端点,也称u,v是相 邻的。称e是点及点v)的关连边 o若图G中,某个边e的两个端点相同,则称e是环(如图10-7中 的 ego o若两个点之间有多于一条的边,称这些边为多重边如图10- 7中的e1e2) 13 清华大学出版社
第1节 图的基本概念 v 图的重要概念（续） ¢ 图G或D中的点数记为p(G)或p(D)，边(弧)数记为q(G)(q(D))， 分别简记为p，q。 ¢ 无向图G=(V，E)常用的一些名词和记号： ¢ 若边e =［u，v］∈E，则称u，v是e的端点，也称u，v是相 邻的。称e是点u(及点v)的关连边。 ¢ 若图G中，某个边e的两个端点相同，则称e是环(如图10-7中 的e7)。 ¢ 若两个点之间有多于一条的边，称这些边为多重边(如图10- 7中的e1 ,e2)。 清华大学出版社 13
第1节图的基本概念 今图论中几个重要记号和术语 o图G或D中的点数记为p(G或p(D),边(弧)数记为q(G)或q(D), 分别简记为p,q。 o无向图G=(V,E常用的一些名词和记号: 口若边e=[w,v∈E,则称v,v是e的端点,也称u,y是相邻 的。称e是点(及点)的关连边。 口若图G中,某个边e的两个端点相同,则称e是环(如图10-7中的 口若两个点之间有多于一条的边,称这些边为多重边(如图10-7 中的e1,e2) 清华大学出版社
第1节 图的基本概念 v 图论中几个重要记号和术语 ¢ 图G或D中的点数记为p(G)或p(D)，边(弧)数记为q(G)或 q(D)， 分别简记为p，q。 ¢ 无向图G=(V，E)常用的一些名词和记号： o 若边e =［u，v］∈E，则称u，v是e的端点，也称u，v是相邻 的。称e是点u(及点v)的关连边。 o 若图G中，某个边e的两个端点相同，则称e是环(如图10-7中的 e7)。 o 若两个点之间有多于一条的边，称这些边为多重边(如图10-7 中的e1 ,e2)。 清华大学出版社 14
第1节图的基本概念 图论中几个重要记号和术语(续) o一个无环,无多重边的图称为简单图;一个无环,但允许有多 重边的图称为多重图。 o以点为端点的边的个数称为v的次,记为d(v)或d(v)。如图10-7 中,d(v1)4,d(v2)=3,d(v3)=3,d(v4)=4(环e7在计算d(V4)时算作 两次)。 称次为1的点为悬挂点,悬挂点的关连边称为悬挂边,次为零的 点称为孤立点。 清华大学出版社
第1节 图的基本概念 v 图论中几个重要记号和术语（续） ¢ 一个无环，无多重边的图称为简单图；一个无环，但允许有多 重边的图称为多重图。 ¢ 以点v为端点的边的个数称为v的次，记为dG(v)或d(v)。如图10-7 中，d(v1)=4，d(v2)=3，d(v3)=3，d(v4)=4(环e7在计算d(v4)时算作 两次)。 ¢ 称次为1的点为悬挂点，悬挂点的关连边称为悬挂边，次为零的 点称为孤立点。 清华大学出版社 15
第1节图的基本概念 冷定理1图G=(V,E)中,所有点的次之和 是边数的两倍,即 ∑d(v)=2q o证明:显然,在计算各点的次时,每条边 被它的端点各用了一次 o次为奇数的点,称为奇点,否则称为偶点。 清华大学出版社
v 定理1 图G=(V，E)中，所有点的次之和 是边数的两倍，即 第1节 图的基本概念 v V v 2q d( ) ¢ 证明：显然，在计算各点的次时，每条边 被它的端点各用了一次。 ¢ 次为奇数的点，称为奇点，否则称为偶点。 清华大学出版社 16