图论课件--有向图.ppt

图论及其应用
应用数学学院
1
本次课主要内容
(一)、有向图的概念与性质
(二)、有向图的连通性
有向图
(三)、图的定向问题
(四)、有向路与有向圈
2
1、概念
定义1 一个有向图D是指一个三元组(V(D) , E(D), фD)。其中,V(D)是非空的顶点集合,E(D)是不与V(D)相交的边集合,而фD是关联函数,它使D的每条边对应D的有序顶点对(不必相异)。
如果e是D的一条边,而u与v是使得фD(u,v)=e的顶点,那么称e是由u连接到v,记为e=<u, v>。同时,称u为e的弧尾(起点), v为e的弧头(终点)。
(一)、有向图的概念与性质
注:有向图可以简单地理解为“边有方向的图”。
3
例如:
有向图D
v4
v3
v2
v1
e2
e1
e4
e3
e6
e5
e7
v3与v2分别是e1 的起点与终点。
定义2 在一个有向图D中,具有相同起点和终点的边称为平行边。两点间平行边的条数称为该两点间的重数。
例如,在上图中,e6与e7是平行边。
4
定义3 在一个有向图D中,如果没有有向环和平行边,则称该图为简单有向图。
定义4 设D是有向图,去掉D中边的方向后得到的无向图G,称为D的基础图。又若G是无向图,给G的每条边加上方向后得到的有向图D称为G的一个定向图。
e3
非简单有向图D
v4
v3
v2
v1
e2
e1
e4
e6
e5
e7
简单有向图D
v4
v3
v2
v1
e2
e1
e4
e6
e5
5
定义5 设D是有向图,v是D中顶点。以v为始点的边的条数称为点v的出度,以v为端点的一个自环算1度。点v的出度记为d+(v);以v为终点的边的条数称为点v的入度,以v为端点的一个自环算1度。点v的入度记为d-(v);
点v的出度与入度之和称为点v的度,记为d(v)。
有向图D
v4
v3
v2
v1
e2
e1
e4
e6
e5
e7
6
对,有
2、性质
定理1 设D=(V, E)是有向图,则:
证明:由出度与入度的定义立即可得上面等式。
3、有向图的矩阵表示
8
E={e1,e2,…,em}
(1) 称A(D)=(aij) n×n是D的邻接矩阵,其中aij是vi为始点,vj为终点的边的条数,1≦i≦n,1≦j≦n。
定义6 设D=(V,E)是有向图,其中V={v1,v2,…,vn}
(2) 若D无环。称矩阵M=(mij)n×m是D的关联矩阵,其中
9
例1 写出下面有向图D1的邻接阵和D2的关联阵。
v4
v3
v2
v1
D1
v4
v3
v2
v1
e1
e4
e3
e2
e5
D2
10