维基百科
调和矩阵
此條目翻譯品質不佳。 (2020年2月17日) |
在图论中,调和矩阵(harmonic matrix),也称拉普拉斯矩阵或拉氏矩阵(Laplacian matrix)、离散拉普拉斯(discrete Laplacian),是图的矩阵表示。[1]
定义
若G是简单图,G有n个顶点,A是邻接矩阵,D是度数矩阵,则调和矩阵是[1]
动机
这跟拉普拉斯算子有什么关系?若f 是加权图G的顶点函数,则[2]
w是边的权重函数。u、v是顶点。f = (f(1), ..., f(n)) 是n维的矢量。上面泛函也称为Dirichlet泛函。[3]
接续矩阵
而且若K是接续矩阵(incidence matrix),则[2]
Kf 是f 的图梯度。另外,特征值满足
举例
其他形式
对称正規化调和矩阵
注意[4]
随机漫步
动力学和微分方程
使用矩阵矢量
解是
平衡举动
当 的时候,
MATLAB代码
N = 20;%The number of pixels along a dimension of the image A = zeros(N, N);%The image Adj = zeros(N*N, N*N);%The adjacency matrix %Use 8 neighbors, and fill in the adjacency matrix dx = [-1, 0, 1, -1, 1, -1, 0, 1]; dy = [-1, -1, -1, 0, 0, 1, 1, 1]; for x = 1:N for y = 1:N index = (x-1)*N + y; for ne = 1:length(dx) newx = x + dx(ne); newy = y + dy(ne); if newx > 0 && newx <= N && newy > 0 && newy <= N index2 = (newx-1)*N + newy; Adj(index, index2) = 1; end end end end %%%BELOW IS THE KEY CODE THAT COMPUTES THE SOLUTION TO THE DIFFERENTIAL %%%EQUATION Deg = diag(sum(Adj, 2));%Compute the degree matrix L = Deg - Adj;%Compute the laplacian matrix in terms of the degree and adjacency matrices [V, D] = eig(L);%Compute the eigenvalues/vectors of the laplacian matrix D = diag(D); %Initial condition (place a few large positive values around and %make everything else zero) C0 = zeros(N, N); C0(2:5, 2:5) = 5; C0(10:15, 10:15) = 10; C0(2:5, 8:13) = 7; C0 = C0(:); C0V = V'*C0;%Transform the initial condition into the coordinate system %of the eigenvectors for t = 0:0.05:5 %Loop through times and decay each initial component Phi = C0V.*exp(-D*t);%Exponential decay for each component Phi = V*Phi;%Transform from eigenvector coordinate system to original coordinate system Phi = reshape(Phi, N, N); %Display the results and write to GIF file imagesc(Phi); caxis([0, 10]); title(sprintf('Diffusion t = %3f', t)); frame = getframe(1); im = frame2im(frame); [imind, cm] = rgb2ind(im, 256); if t == 0 imwrite(imind, cm, 'out.gif', 'gif', 'Loopcount', inf, 'DelayTime', 0.1); else imwrite(imind, cm, 'out.gif', 'gif', 'WriteMode', 'append', 'DelayTime', 0.1); end end
应用
参考文献
- ^ 1.0 1.1 Weisstein, Eric W. (编). Laplacian Matrix. at MathWorld--A Wolfram Web Resource. Wolfram Research, Inc. [2020-02-14]. (原始内容于2019-12-23) (英语).
- ^ 2.0 2.1 Muni Sreenivas Pydi (ముని శ్రీనివాస్ పైడి)'s answer to What's the intuition behind a Laplacian matrix? I'm not so much interested in mathematical details or technical applications. I'm trying to grasp what a laplacian matrix actually represents, and what aspects of a graph it makes accessible. - Quora. www.quora.com. [2020-02-14].
- ^ 3.0 3.1 Shuman, David I.; Narang, Sunil K.; Frossard, Pascal; Ortega, Antonio; Vandergheynst, Pierre. The Emerging Field of Signal Processing on Graphs: Extending High-Dimensional Data Analysis to Networks and Other Irregular Domains. IEEE Signal Processing Magazine. 2013-05, 30 (3): 83–98 [2020-02-14]. ISSN 1053-5888. doi:10.1109/MSP.2012.2235192. (原始内容于2020-01-11).
- ^ Chung, Fan. Spectral Graph Theory. American Mathematical Society. 1997 [1992] [2020-02-14]. ISBN 978-0821803158. (原始内容于2020-02-14).
- ^ Newman, Mark. Networks: An Introduction. Oxford University Press. 2010. ISBN 978-0199206650.
阅读
- T. Sunada. Chapter 1. Analysis on combinatorial graphs. Discrete geometric analysis. P. Exner, J. P. Keating, P. Kuchment, T. Sunada, A. Teplyaev (编). 'Proceedings of Symposia in Pure Mathematics 77. 2008: 51–86. ISBN 978-0-8218-4471-7.
- B. Bollobás, Modern Graph Theory, Springer-Verlag (1998, corrected ed. 2013), ISBN 0-387-98488-7, Chapters II.3 (Vector Spaces and Matrices Associated with Graphs), VIII.2 (The Adjacency Matrix and the Laplacian), IX.2 (Electrical Networks and Random Walks).