例1一个简单图有多少个定向图？ 答：因为每条边有2种定向方式，所以共有2mG种定向。 例2求证：G存在一个定向图D,使得对v∈V(D),有 d()-d(s1 证明：不失一般性，设G是连通图。G中奇度顶点个数必 然为偶数个，将偶数个奇数度顶点配对，然后在每一对配对 顶点间连一条边得到欧拉图G1。在G,中用Fluery:算法求出G 的一欧拉环游C,然后顺次地在C上标上方向，由此得到C的 定向图C 在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 7 例1 一个简单图有多少个定向图？ 答：因为每条边有2种定向方式，所以共有2 m(G)种定向。 例2 求证：G存在一个定向图D，使得对 ，有 v VD( ) dv dv () () 1 证明：不失一般性，设G是连通图。G中奇度顶点个数必 然为偶数个，将偶数个奇数度顶点配对，然后在每一对配对 顶点间连一条边得到欧拉图G1。在G1中用Fluery算法求出G 的一欧拉环游C,然后顺次地在C上标上方向，由此得到C的 定向图C1。 在C1中，去掉添加的边后，得到G的定向图D.显然：
对vEV(D),有 d"(v)-d()s1 2、性质 定理1设D=(V,E)是有向图，则： ∑d(y)=∑d(m)=m(D) vEV(D) vEV(D) 证明：由出度与入度的定义立即可得上面等式。 3、有向图的矩阵表示 8
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 对 ，有 v VD( ) dv dv () () 1 2、性质 定理1 设D=(V, E)是有向图，则： () () () () ( ) vVD vVD d v d v mD 证明：由出度与入度的定义立即可得上面等式。 3、有向图的矩阵表示
定义6设D=(V,E)是有向图，其中V={v1V2,Vm} E=fepe2....em} ()称AD=(a)nxm是D的邻接矩阵，其中a是v为始点， v为终点的边的条数，1i≤n,1j≤n。 (2)若D无环。称矩阵M=(mm×m是D的关联矩阵，其中 1,y,是e的始点， -l,y,是边e的终点，(1≤i≤n,l≤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 9 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 in j m 是 的始点， ， 是边 的终点， 其它