# Matrix Representation Of Graphs

**Matrix Representation of Graphs**: The adjacency matrix of the graph G = (V,E) is an n × n matrix D = (dij), where n is the number of vertices in G, V = {v1, . . . , vn} and d_{ij} = number of edges between vi and vj . In particular, dij = 0 if (vi, vj) is not an edge in G. The matrix D is symmetric, i.e. DT = D.

**Example.**

Obviously, an adjacency matrix defines a graph completely up to an isomorphism. The adjacency matrix of a directed graph G is D = (d_{ij}), where d_{ij} = number of arcs that come out of vertex vi and go into vertex vj .

The all-vertex incidence matrix of a non-empty and loopless graph G = (V,E) is an n×m matrix A = (a_{ij}), where n is the number of vertices in G, m is the number of edges in G and

**Example.**

The all-vertex incidence matrix of a non-empty and loopless directed graph G is A = (aij), where

**Example.**

Since every column of an all-vertex incidence matrix contains exactly two non-zero numbers, two ones, we can remove a row and still have enough information to define the graph. The incidence matrix of a graph is obtained by removing a row from the all-vertex incidence matrix. It is not unique because there are n possible rows to remove. The vertex corresponding to the row removed is called the reference vertex.

Similarly, every column in the all-vertex incidence matrix of a digraph contains exactly two non-zero numbers, 1 and −1. We can remove a row from the all-vertex incidence matrix and obtain the incidence matrix. Notice that the rows of an all-vertex incidence matrix are linearly dependent because the sum of rows is a zero vector.