1图的基本概A与基本定理 图85是一个有向图D=(V,A) 其中V={vnV2pybn A={(v1,v2),(v1,3)(v3,v2),(v3,v4, (v2,v4),(v4,5)v4,vb)(vs,v3), (vs,v4),(5,v),(6,) 17 106 14 图8-5
16 图8-5是一个有向图D=（V，A） 其中V = {v1 ,v2 ,v3 ,v4 ,v5 ,v6 ,v7 } A = {(v1 ,v2 ),(v1 ,v3 ),(v3 ,v2 ), (v3 ,v4 ), (v2 ,v4 ),(v4 ,v5 ),(v4 ,v6 ),(v5 ,v3 ), (v5 ,v4 ),(v5 ,v6 ),(v6 ,v7 )} 1.图的基本概念与基本定理 v3 v5 v7 v2 v4 v1 v6 图8-5
1.图的基本概心与基本定理 一些常用的名词:无向图G或有向图D 节点数记作PG成PD简记作P 边数或者弧数记作q(G者q(D简 记作q 如果边[vvE那么称v是边的端点, 或者vv是相邻的。 如果一个图a中,一条边的两个端点是 相同的那么称为这条边是环
一些常用的名词：无向图G 或 有向图D 节点数 记作P(G)或P(D),简记作P, 边数 或者 弧数 记作q(G)或者q(D),简 记作q。 如果边[vi ,vj ] E,那么称vi ,vj是边的端点， 或者vi ,vj是相邻的。 如果一个图G中，一条边的两个端点是 相同的,那么称为这条边是环。 1.图的基本概念与基本定理
1.图的基本概念与基本定理 如果两个端点之间有两个端点之间有两 条以上的边,那么称为它们为多重边。 个无环,无多重边的图为简单图。 一个无环,有 12 多重边的图称为 多重图。 环 图8-4
1.图的基本概念与基本定理 如果两个端点之间有两个端点之间有两 条以上的边，那么称为它们为多重边。 一个无环，无多重边的图为简单图。 一个无环，有 多重边的图称为 多重图。 v3 v2 v1 v4 图8-4 环
1.图的基本概心与基本定理 以点ν为端点的边的个数称为点v 的度,记作(v)。如上图中d(v)=3, d(v2)4,d(v3)=4,d(v)=3。 度为零的点称为弧立点,度为1的 点称为悬挂点。悬挂点的边称为悬挂 边 度为奇数的点称为奇点,度为偶数 的点称为偶点
以点v为端点的边的个数称为点v 的度，记作d(v)。如上图中d(v1 )=3, d(v2 )=4, d(v3 )=4, d(v4 )=3。 度为零的点称为弧立点，度为1的 点称为悬挂点。悬挂点的边称为悬挂 边。 度为奇数的点称为奇点，度为偶数 的点称为偶点。 1.图的基本概念与基本定理
1图的基本概心与基本定理 端点的度d():点ν作为边端点 的个数 奇点:d()奇数 偶点:d()=偶数 悬挂点:d()=1 悬挂边:与悬挂点连接的边 孤立点:d()=0 空图:E=,无边图
20 端点的度 d(v)：点 v 作为边端点 的个数； 奇点：d(v)=奇数； 偶点：d(v)=偶数； 悬挂点：d(v)=1； 悬挂边：与悬挂点连接的边； 孤立点：d(v)=0； 空图：E = ，无边图 1.图的基本概念与基本定理