Arunkumar Khannur's Software Testing Knowledge Center
   
 

11.4 Terminology: The Matrix of a Graph

Matrix representation of a graph is a tabular representation with a provision to represent every possible link between any nodes to any other node. In matrix, number of columns as well as number of rows is equal to number of nodes, and the value in a cell corresponding to cross-section of each column and row represents a link weight. In a matrix, each row of a matrix denotes the out-links of the node corresponding to that node, and each column denotes the in-links corresponding to that node.

The Size of the Matrix
The Size of the Matrix (i.e., the number of rows or columns) equals the number of nodes.

Link Weight
In the matrix representation, the link weight of the link between the two nodes is the entry at the intersection of a row and a column in the direction from first node to second node. The link weight between node i and node j is denoted by aij.

Path Segment
Path segment between two nodes is an expression that consists of a sequence of contiguous links or link weights that are part of the specified path.

Connection Matrix and Relation Matrix
In case, we wish to represent a links between two nodes just to represent “is connected to” using a more general relationship using a matrix, we call such a matrix as “relation matrix”.
In another representation of matrix referred to as “connection matrix”, we can use the “1” to mean that there is a connection and “0” to indicate that there is no connection.

Branch Node, Junction Node, and Self-loop
If we find more than one non-zero entries in a row, then the node corresponding to that row is referred to as a “branch node”. If in a column, we find non-zero entries, then the node corresponding to that row is referred to as a “junction node”.
An entry along the diagonal in a matrix is referred to as self-loop. The link weight of self-loop about node i is denoted by aii.
Notational Representation of Matrix Graph
The set of all possible paths between node i and node j via at least one intermediate node k is represented in the most compact notational form using link weight representation as:


Transpose of a Matrix
The transpose of a matrix is the matrix with rows and columns interchanged. Notationally, transpose of a matrix A is denoted by a superscript letter “T” as AT . Thus, if C=AT then cij = aji .

Intersection of Two Matrices
The intersection of two matrices of the same size is a matrix obtained by an element by element multiplication operation on the entries of the two matrices. Intersection of two matrices is denoted by A#B. Thus, intersection of two matrices, C = A#B with elements in C as cij = aij#bij . The multiplication operation is usually Boolean AND or set intersection.

Union of Two Matrices
The union of two matrices of the same size is a matrix obtained by an element by element addition operation on the entries of the two matrices. The union operation is usually Boolean OR or set union.
 
 
Khannur's Book
Arunkumar Khannur, Software Testing - Techniques and Applications, Published by Pearson Publications, 2011 (ISBN:978-81-317-5836-6; Pages:341 + xxii)
Follow Khannur
         
Khannur's Company
ISQT Process & Consulting Services Pvt. Ltd., Bangalore, INDIA
Khannur's Software Testing Forum
STEP-AUTO Forum
 Contact Khannur
ISQT Process & Consulting Services Pvt. Ltd.
#732, 1st Floor, 12th Main,
3rd Block, Rajajinagar,
Bangalore - 560010, INDIA
Phone: +91 80 23012511
URL: www.isqtinternational.com
Email: khannur@isqtinternational.com
Skype: arun.isqt