今天继续图论。
1 定义
有向图对一般图做了一点改进，边有了方向含义，也就是一般图组成边的是无序对偶集(Ni，Nj)，而有向图组成边的是有序对偶集<Ni, Nj>，其中Ni是初始节点，而Nj是结束节点。
图1 有向图示意
2 内度和外度
内度是指以该节点为结束节点的边的条数，例如图1中N4的内度为2。外度指的是以该节点为开始节点的边的条数，例如图1中N1的外度为2。
3 节点的类型
内度为0的节点为源节点，外度为0的节点为吸收节点，内度和外度均不为0的节点为传递节点。
4 相邻矩阵
相邻矩阵行的和是节点的外度，列的和是节点的内度。例如，第1行表示<N1,N2>、<N1,N4>两条边。
图2 相邻矩阵
5 路径与半路径
（有向）路径：第一条边的终止节点是第二条边的起始节点，例如图1中N1到N6为路径。
（有向）半路径：第一条边的起始节点也是第二条边的起始节点，或者第一条边的终止节点也是第二条边的终止节点。注意：某序列中只要有一对边满足上述要求即可认为是半路径。图1中N1和N3、N2和N4以及N5和N6序列均为半路径。
6 可到达矩阵
顾名思义，就是从某个点可以到达某个点的矩阵，其中行为起始点，列为结束点。例如，对于N1行，N1作为起始点时，可以到达N2、N4、N5和N6，因此第一行为[0, 1, 0, 1, 1, 1, 0]
图3 可到达矩阵
7 n-连接性
n-连接性包括了以下几种类型：
0-连接性：两个节点之间没有路径
1-连接性：两个节点之间有一条半路径，但是没有路径
2-连接性：两个节点之间有一条路径
3-连接性：从Ni到Nj之间有一条路径，从Nj到Ni之间也有一条路径
8 强组件
有向图的强组件是3-连接节点的最大集合。
将图1的有向图修改为下图，显然集合{N3，N4，N6}为强组件，由此得到压缩图，如图5。
图4 有向图
图5 压缩图
参考资料：
《软件测试》第二版 Paul C. Jorgensen 韩柯 杜旭涛 译
