Step 1: Our Example Graph
This is our graph with 4 vertices. Each vertex is connected to some other vertices by edges.
Step 2: Graph with Edges
Now we see the connections between vertices:
Vertex 1 is connected to vertices 2 and 4.
Vertex 2 is connected to vertices 1 and 3.
Vertex 3 is connected to vertices 2 and 4.
Vertex 4 is connected to vertices 1 and 3.
Step 3: Adjacency Matrix
1
0
1
0
1
2
1
0
1
0
3
0
1
0
1
4
1
0
1
0
The adjacency matrix shows connections between vertices.
A 1 at position (i,j) means vertex i is connected to vertex j.
A 0 means there is no connection.
Step 4: Degree Matrix
1
2
0
0
0
2
0
2
0
0
3
0
0
2
0
4
0
0
0
2
The degree matrix is a diagonal matrix where each entry (i,i) shows the number of connections that vertex i has.
Here, each vertex has 2 connections, so all diagonal entries are 2.
Step 5: Laplacian Matrix Calculation
Laplacian Matrix = Degree Matrix - Adjacency Matrix
For diagonal elements: Use the vertex degree (number of connections)
For off-diagonal elements: Use -1 if vertices are connected, 0 otherwise
Step 6: Laplacian Matrix
1
2
-1
0
-1
2
-1
2
-1
0
3
0
-1
2
-1
4
-1
0
-1
2
The final Laplacian matrix:
- Diagonal elements (i,i) = degree of vertex i
- Off-diagonal elements (i,j) = -1 if vertices i and j are connected
- Off-diagonal elements (i,j) = 0 if vertices i and j are not connected
Step 7: Summary
1
2
-1
0
-1
2
-1
2
-1
0
3
0
-1
2
-1
4
-1
0
-1
2
The Laplacian matrix is useful for many graph algorithms and spectral graph theory.
Key properties:
- Row sums and column sums are zero
- It's a symmetric matrix
- The number of zero eigenvalues equals the number of connected components in the graph