New Page 1
Welcome to basicsofcomputer.com

Home » Computer Dictionary » Letter A » Adjacency Matrix/Connectivity Matrix/Reachability Matrix Definition/Meaning

A matrix used as a means of representing a graph. If A is the adjacency matrix corresponding to a given graph G, then

aij = 1

if there is an edge from vertex i to vertex j in G; otherwise

aij = 0

If G is a directed graph then

aij = 1

if there is an edge directed from vertex i to vertex j otherwise

aij = 0

If the vertices of the graph are numbered 1,2, ... m, the adjacency matrix is of a type m x m. If

A x A x ... x A

(p terms, p≤m)

is evaluated, the nonzero entries indicate those vertices that are joined by a 'path of length p; indeed the valued the i,jth entry of Ap gives the number of paths of length p from the vertex i to vertex j. By examining the set of such matrices,

p = l,2,...,m - l

it can be determined whether two vertices are connected.

It is also possible for adjacency matrices to be formed from Boolean matrices.

Near by Terms:

New Page 1

Basic Computer Science

 » The Age of Information » Types of Computer and Digital Age » Input and Output Devices » Storage Devices Of Computer » Central Processing Unit » Software: The Power Behind The Power » Data Communication and Computer Networks » The Nature Of Information » The System Theory » Transaction Processing System (TPS) and Management Information System (MIS) » » Expert System (ES) and Office Information System (OIS)

Operating Systems

 » Introduction to Operating System » Introduction to Process Management » Threads and CPU Scheduling » Process Synchronization in Operating System » Deadlocks » Memory Management in Operating System » Virtual Memory in Operating System » File System Management in Operating System » I/O and Device Management » Security » Linux Operating System

Database Management System

 » Introduction to Database Systems » Database System Architecture » Database Administration and Database Development Process » The Entity-Relationship Model » Semantic Object Model » Logical Database Design and Relational Data Model » Normalization in Database » Transformation of E-R Model into Relational Data Model » Representing Semantic Object Model and Types of Semantic Object Model » Physical Database Design » Introduction to Structured Query Language (SQL) » Implementation of Relational Database and Database Application Design » Client Server Database Systems & Open Database Connectivity (ODBC)