1图的基本概A与基本定理 图8.5是一个有向图D(V,A) 其中v{vnV2Vyvv5VV A={( (vv),( V2. v V. v. 6 了3 V4 图8.5 16
16 图8.5是一个有向图D=（V，A） 其中V={v1,v2,v3,v4,v5,v6,v7} A={(v1,v2),(v,v3),(v3,v2), (v3,v4),(v2,v4),(v4,v5), (v4,v6),(v,v3),(v5,v4), (v5,v6),(v6,v7)} 1.图的基本概念与基本定理 v3 v5 v7 v2 v4 v1 v6 图8.5
1图的基本概A与基本定理 下面介绍一些常用的名词 个图碱或有向图D中的点数,记作P(G或 (加),简记作P,边数或者弧数,记作q(G或者 g(mD,记作q 如果边[v,阿E那么称VV是边的端点 或者VV是相邻的。如果一个图(中,一条边 的两个端点是相同的,那么称为这条边是环,如 图8.4中的边[v以是环。如果两个端点之间有 两个端点之间有两条以上的边,那么称为它价 为多重边,如图8.4中的边[vnV2,[v2 无环,无多重边的图标为简单图,一个无 环,有多重边的囹标图称为多重图
17 下面介绍一些常用的名词： 一个图G或有向图D中的点数,记作P(G)或 P(D),简记作P,边数或者弧数,记作q(G)或者 q(D),简记作q。 如果边[vi,vj] E,那么称vi,vj是边的端点， 或者vi,vj是相邻的。如果一个图G中，一条边 的两个端点是相同的,那么称为这条边是环，如 图8.4中的边[v,v3]是环。如果两个端点之间有 两个端点之间有两条以上的边，那么称为它们 为多重边，如图8.4中的边[v1,v2] ,[v2,v1]。 一个无环，无多重边的图标为简单图，一个无 环，有多重边的图标图称为多重图。 1.图的基本概念与基本定理
1图的基本概A与基本定理 以点V端点的边的个数称为点 v的度,记作d(,如图84中 d(v1)=3,d(v2)=4,d(v3)=4,d(v)=3。 度为零的点称为弧立点,度为1 的点称为悬挂点。悬挂点的边称为 悬挂边。度为奇数的点称为奇点 度为偶数的点称为偶点
18 以点v为端点的边的个数称为点 v 的 度 ， 记 作 d(v), 如 图 8—4 中 d(v1)=3， d(v2)=4,d(v3)=4,d(v4)=3。 度为零的点称为弧立点，度为1 的点称为悬挂点。悬挂点的边称为 悬挂边。度为奇数的点称为奇点， 度为偶数的点称为偶点。 1.图的基本概念与基本定理
1图的基本概与基本定理 端点的度d(v):点V作为边端点 的个数 奇点:d(v)奇数; 偶点:d()偶数; 悬挂点:d(V)=1; 燙挂边:与悬挂点连接的边; 孤立点:d(v)=0; 控图:E=,无边图
19 端点的度 d(v)：点 v 作为边端点 的个数； 奇点：d(v)=奇数； 偶点：d(v)=偶数； 悬挂点：d(v)=1； 悬挂边：与悬挂点连接的边； 孤立点：d(v)=0； 空图：E = ，无边图 1.图的基本概念与基本定理
1.图的基本概心与基本定理 定理8.1所有顶点次数之和 等于所有边数的2倍。 定理8.2在任一图中,奇 点的个数必为偶数
定理8.1 所有顶点次数之和 等于所有边数的2倍。 定理8.2 在任一图中，奇 点的个数必为偶数。 1.图的基本概念与基本定理