Adjacency & Incidence Matrices

ADJACENCY MATRICES:

           

            Suppose G(V,E) is a simple graph with n vertices v₁,v₂,….,v_n. The adjacency matrix or sometimes called connection matrix of the graph G(V,E), denoted by A(G) is a matrix (a_ij)_{n x n} (with respect to the particular ordering of vertices) such that,

                        a_ij=1, if there is an edge between i th and j th vertices

                           =0, if there is no edge between i th and j th vertices

 Example:

     

INCIDENCE MATRICES:

            Let G(V,E) be an undirected graph (without parallel edges and loops) with n vertices v_1,v₂,….,v_n and m edges e₁,e₂,….e_m then the incidence matrix with respect to this ordering of V and E is the n x m matrix B=(b_ij)_{n x m} where

                   b_ij=1, when the edge e_j is incident on v_i

                      =0, otherwise