Graph Laplacian

Earlier in this chapter, in the Adjacency matrix section, we learned about the adjacency matrix and how we can use it to tell what the structure of a graph is. However, there are other ways of representing graphs in matrix form.

Now, let's suppose we have an undirected, unweighted graph. Then, its Laplacian matrix will be a symmetric n × n matrix, L, whose elements are as follows:

Here, . We can also write this as follows:

Here, A_i,j is the adjacency matrix and δ_i,j is the Kronecker delta. We can rewrite this in matrix form, as follows:

Here, we have the following:

Similarly, we can also write the graph Laplacian matrix for a weighted graph by replacing the adjacency matrix here with the one we defined previously for weighted graphs.