
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 crosssection of each column and row represents a link weight. In a matrix, each row of a matrix denotes the outlinks of the node corresponding to that node, and each column denotes the inlinks 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 a_{ij}.

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 Selfloop
If we find more than one nonzero entries in a row, then the node corresponding to that row is referred to as a “branch node”. If in a column, we find nonzero 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 selfloop. The link weight of selfloop about node i is denoted by a_{ii}.

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 A^{T} . Thus, if C=A^{T} then c_{ij} = a_{ji} .

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 c_{ij} = a_{ij}#b_{ij} . 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:9788131758366; Pages:341 + xxii) 
Follow Khannur 

Khannur's Company 

ISQT Process & Consulting Services Pvt. Ltd., Bangalore, INDIA

Khannur's Software Testing Forum 

STEPAUTO 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 
