图论课件--有向图.ppt

1图论及其应用应用数学学院 2本次课主要内容(一)、有向图的概念与性质(二)、有向图的连通性有向图(三)、图的定向问题(四)、有向路与有向圈 3 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的弧头(终点)。(一)、有向图的概念与性质注:有向图可以简单地理解为“边有方向的图”。 4 例如: 有向图 D v 4v 3 v 2v 1e 2e 1e 4e 3e 6e 5e 7 1 3 2 , e v v ?? ? v 3与v 2分别是 e 1的起点与终点。定义 2 在一个有向图 D中,具有相同起点和终点的边称为平行边。两点间平行边的条数称为该两点间的重数。例如,在上图中, e 6与e 7是平行边。 5 定义 3 在一个有向图 D中,如果没有有向环和平行边,则称该图为简单有向图。定义 4 设D是有向图,去掉 D中边的方向后得到的无向图G,称为 D的基础图。又若 G是无向图,给 G的每条边加上方向后得到的有向图 D称为 G的一个定向图。 e 3非简单有向图 D v 4v 3 v 2v 1e 2e 1e 4e 6e 5e 7简单有向图 D v 4v 3 v 2v 1e 2e 1e 4e 6e 56 定义 5 设D是有向图, v是D中顶点。以 v为始点的边的条数称为点 v的出度,以 v为端点的一个自环算 1度。点 v的出度记为 d + (v); 以v为终点的边的条数称为点 v的入度,以 v为端点的一个自环算 1度。点 v的入度记为 d - (v); 点v的出度与入度之和称为点 v的度,记为 d(v) 。有向图 D v 4v 3 v 2v 1e 2e 1e 4e 6e 5e 7 4 ( ) 2 d v ?? 4 ( ) 2 d v ?? 4 ( ) 4 d v ? 7 例1 一个简单图有多少个定向图? 答:因为每条边有 2种定向方式,所以共有 2 m(G) 种定向。例2 求证: G存在一个定向图 D,使得对,有( ) v V D ??( ) ( ) 1 d v d v ? ?? ?证明:不失一般性,设 G是连通图。 G中奇度顶点个数必然为偶数个,将偶数个奇数度顶点配对,然后在每一对配对顶点间连一条边得到欧拉图 G 1。在 G 1中用 Fluery 算法求出 G 的一欧拉环游 C,然后顺次地在 C上标上方向,由此得到 C的定向图 C 1。在C 1中,去掉添加的边后,得到 G的定向图 : 8 对,有( ) v V D ??( ) ( ) 1 d v d v ? ?? ? 2、性质定理 1 设 D=(V, E) 是有向图,则: ( ) ( ) ( ) ( ) ( ) v V D v V D d v d v m D ? ?? ?? ?? ?证明:由出度与入度的定义立即可得上面等式。 3、有向图的矩阵表示 9 E= {e 1,e 2,…,e m} (1) 称 A(D)=(a ij ) n×n是D的邻接矩阵,其中 a ij是v i为始点, v j 为终点的边的条数, 1≦i≦ n,1 ≦j≦n。定义 6 设 D=(V,E) 是有向图,其中 V= {v 1,v 2,…,v n} (2) 若D无环。称矩阵 M=(m ij) n×m是D的关联矩阵,其中 1, -1 (1 ,1 ), 0, . i j ij i j v e m v e i n j m ??? ???????是的始点, , 是边的终点, 其它 10 例1 写出下面有向图 D 1的邻接阵和 D 2的关联阵。 v 4v 3v 2v 1D 1v 4v 3 v 2v 1e 1e 4e 3e 2e 5D 2 1 0 1 0 0 0 2 1 2 ( ) 0 0 0 0 0 0 1 0 A D ? ?? ?? ??? ?? ?? ??