Ask a Question

Juhi

The incidence matrix of a directed graph G=(V, E) is a V×E matrix B = (bij) such that -1 if edge j leaves vertex j. bij = 1 if edge j enters vertex j. 0 otherwise. If B is the incidence matrix and BT is its transpose, the diagonal of the product matrix BBT represents the degree of all the nodes, i.e., if P is the product matrix BBT then P[i, j] represents the degree of node i: Specifically we have BBT(i,j) = ∑eÎE bie bTej = ∑eÎE bie bje Now, * If i = j, then biebje = 1, whenever edge e enters or leaves vertex i and 0 otherwise. * If i ≠ j, then biebje = -1, when e = (i, j) or e = (j, i) and 0 otherwise. Therefore BBT(i,j) = deg(i) = in_deg + Out_deg if i = j = -(# of edges connecting i an j ) if i ≠ j