Một ma trận đối xứng quan trọng khác liên kết với một đồ thị là ma trận Laplace. Đây là ma trận [latex]L = A^TA[/latex], với [latex]A[/latex] là ma trận liên thuộc cung-nút. Có thể chứng minh rằng phần tử [latex](i, j)[/latex] của ma trận Laplace được cho bởi
\[ L_{i j} = \begin{cases} \text{số cung liên thuộc với nút } i & \text{ nếu } i=j, \\ -1 & \text{ nếu có một cung nối nút } i \text{ với nút } j, \\ 0 & \text{ trong trường hợp khác. } \end{cases}\]
Xem thêm:
