例1一个简单图有多少个定向图？ 答：因为每条边有2种定向方式，所以共有2mG种定向。 例2求证：G存在一个定向图D,使得对v∈V(D),有 d*(v)-d(v)≤1 证明：不失一般性，设G是连通图。G中奇度顶点个数必 然为偶数个，将偶数个奇数度顶点配对，然后在每一对配对 J顶点间连一条边得到欧拉图G,。在G,中用Fluery.算法求出G 的一欧拉环游C,然后顺次地在C上标上方向，由此得到C的 定向图C1。 在C,中，去掉添加的边后，得到G的定向图D.显然：
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 6 例1 一个简单图有多少个定向图？ 答：因为每条边有2种定向方式，所以共有2 m(G)种定向。 例2 求证：G存在一个定向图D，使得对 v V D( ) ，有 d v d v ( ) ( ) 1 + − − 证明：不失一般性，设G是连通图。G中奇度顶点个数必 然为偶数个，将偶数个奇数度顶点配对，然后在每一对配对 顶点间连一条边得到欧拉图G1。在G1中用Fluery算法求出G 的一欧拉环游C,然后顺次地在C上标上方向，由此得到C的 定向图C1。 在C1中，去掉添加的边后，得到G的定向图D.显然：
对 vEV(D),有 d(y)-dr(v)l≤1 2、性质 定理1设D=(V,E)是有向图，则： ∑d*(y)=∑d(v)=m(D) vEV(D) veV(D) 证明：由出度与入度的定义立即可得上面等式。 3、有向图的矩阵表示
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 7 对 v V D( ) ，有 d v d v ( ) ( ) 1 + − − 2、性质 定理1 设D=(V, E)是有向图，则： ( ) ( ) ( ) ( ) ( ) v V D v V D d v d v m D + − = = 证明：由出度与入度的定义立即可得上面等式。 3、有向图的矩阵表示
定义6设D=(V,E)是有向图，其中V={vV2Vn} E={epe2.em} (I)称AD)=(a)nxm是D的邻接矩阵，其中a是v为始点， v为终点的边的条数，1in,1j≤n。 (2)若D无环。称矩阵M=(m)n×m是D的关联矩阵，其中 1,y,是e的始点， m,= -1,y,是边e,的终点，(1≤i≤n,1≤j≤m) 0,其它
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 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的关联矩阵，其中 1, -1 (1 ,1 ), 0, . i j ij i j v e m v e i n j m = 是 的始点， ， 是边 的终点， 其它
例1写出下面有向图D,的邻接阵和D,的关联阵。 D 0 0 0 0 0 0 -1 0 AD) M(D2)= 0 0 一1 0 0 0 0
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 9 例1 写出下面有向图D1的邻接阵和D2的关联阵。 v4 v3 v2 v1 D1 v3 v4 v2 v1 e1 e4 e3 e2 e5 D2 1 0 1 0 0 0 2 1 2 ( ) 0000 0 0 1 0 A D = 2 1 0 0 0 0 1 1 1 1 0 ( ) 0 1 1 0 1 0 0 0 1 1 M D − − = − − −
(二)、有向图的连通性 1、相关概念 (1)有向途径（闭途径）、迹（闭迹）和路（圈） 上面概念与无向图中相关概念类似。 (2)有向图中顶点间的连通性 定义7设D=(V,E)是有向图，u与v是D中两个顶点。 1)若D中存在一条(u,v)路，则称u可达y,记为u→v。 规定u→Ⅲ。 2)若D中存在一条(u,v)路或y,u)路，则称u与v是单 向连通的。 0
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 10 1、相关概念 (二)、有向图的连通性 (1) 有向途径(闭途径)、迹(闭迹)和路(圈) 上面概念与无向图中相关概念类似。 (2) 有向图中顶点间的连通性 定义7 设D=(V, E)是有向图，u与v是D中两个顶点。 1) 若D中存在一条(u，v)路，则称u可达v,记为u→v。 规定u →u。 2) 若D中存在一条(u，v)路或(v, u)路，则称u与v是单 向连通的