1图的基本概念与基本定理 下面介绍一些常用的名词 一个图G或有向图D中的点数,记作PG或 P(⑩D),记作P,边数或者弧数,记作q(G或者 q(D),简记作q 如果边[vVE那么称VV是边的端点 或者v,V是相邻的。如果一个图G中,一条边 的两个端点是相同的,那么称为这条边是环,如 图8.4中的边[v,V是环。如果两个端点之间有 两个端点之间有两条以上的边,那么称为它们 为多重边,如图8.4中的边[V,V2,[V2V。 一个无环,无多重边的图标为简单图,一个无 环,有多重边的图标图称为多重图
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图的基本概念与基本定理 以点端点的边的个数称为点 V的度,记作d(V,如图8-4中 d(v)=3,d(v2)=4,d(v3=4,d(vp=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):点作为边端点的个数 点:d(V)=奇数; 偶点:d(V)偶数; 是挂点: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.图的基本概念与基本定理
1图的基本概念与基本定理 图的连通性 链 由两两相邻的点及其相 关联的边构成的点边序 列;如:V e2, v v分别为链的起点和终点 简单链:链中所含的边均不相同; 初等链:链中所含的点均不相同, 也称通路;
21 图的连通性： 链： 由两两相邻的点及其相 关联的边构成的点边序 列;如:v0 ,e1 ,v1 ,e2 ,v2 e3 ,v3 ,…,vn-1,en , vn ; vn分别为链的起点和终点 简单链：链中所含的边均不相同； 初等链：链中所含的点均不相同, 也称通路； 1.图的基本概念与基本定理