Incidence Matrices - Software Testing

The incidence matrix of a graph G = (V, E) with m nodes and n edges is an m x n matrix

7/1/2009Print This PageTell - A - FriendAdd to Wish ListReport Error

Graphs need not be represented pictorially – they can be fully represented in an incidence matrix. This concept becomes very useful for testers. So we will formalize it here. When graphs are given a specific interpretation, the incidence matrix always provides useful information for the new interpretation.

Definition:

The incidence matrix of a graph G = (V, E) with m nodes and n edges is an m x 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. the incidence matrix of the graph in figure is:

We can make some observations about a graph by examining its incidence matrix. First notice that the sum of the entries in any column is 2. That is because edge has exactly two endpoints. If a column sum in an incidence matrix is over something other than 2, there is a mistake somewhere. Thus forming column sums is a form of integrity checking similar in spirit to that of parity checks. Next we se that the row sum is the degree of the node. When the degree of a node is zero, as it is for node n-, we say the node is isolated. (This might correspond to unreachable code or to objects that are included but never used.)

7/1/2009Print This PageTell - A - FriendAdd to Wish ListReport Error

Related Words:

Graph Theory, Linear Graph, Degree of a Node, Incidence Matrices, Adjacency Matrices, Paths, Connectedness, Condensation Graph, Cyclomatic Number, Directed Graph, Software Testing Notes, Online Software Testing Papers