软件测试人员的图论

Definition
A graph G = (V, E) is composed of a finite (and nonempty) set V of nodes and a set E of unordered pairs of nodes.

In the graph in above, the node and edge sets are

Degree of a Node
Definition
The degree of a node in a graph is the number of edges that have that node as an endpoint. We write deg(n) for the degree of node n.
节点的度，也就是该节点作为端点边的条数，记住deg(n).

The degrees of the nodes in above are

Incidence Matrices
Definition
The incidence matrix of a graph G = (V, E) with m nodes and n edges is an m × n matrix, where the element in row i, column j is a 1 if and only if node i is an endpoint of edge j; otherwise, the element is 0.
当且仅当节点i 是边j 的一个端点是，第i行j列元素才是1.

Adjacency Matrices
Definition
The adjacency matrix of a graph G = (V, E) with m nodes is an m × m matrix, where the element in row i, column j is a 1 if and only if an edge exists between node i and node j; otherwise, the element is 0.
The adjacency matrix is symmetric (element i,j always equals element j,i), and a row sum is the degree of the node (as it was in the incidence matrix).

Directed Graphs
Indegrees and Outdegrees
Definition
The indegree of a node in a directed graph is the number of distinct edges that have the node as a terminal node. We write indeg(n) for the indegree of node n. The outdegree of a node in a directed graph is the number of distinct edges that have the node as a start point. We write outdeg(n) for the outdegree of node n.

Indegrees and Outdegrees The degree of a node in an ordinary graph is refined to reflect direction, as follows:
Definition
The indegree of a node in a directed graph is the number of distinct edges that have the node as a terminal node. We write indeg(n) for the indegree of node n. The outdegree of a node in a directed graph is the number of distinct edges that have the node as a start point. We write outdeg(n) for the outdegree of node n. The nodes in the digraph in Figure 4.2 have the following indegrees and outdegrees:
Indegrees and Outdegrees The degree of a node in an ordinary graph is refined to reflect direction, as follows:
Definition
The indegree of a node in a directed graph is the number of distinct edges that have the node as a terminal node. We write indeg(n) for the indegree of node n. The outdegree of a node in a directed graph is the number of distinct edges that have the node as a start point. We write outdeg(n) for the outdegree of node n. The nodes in the digraph in Figure 4.2 have the following indegrees and outdegrees: