Кіріспе
Граф теориясының математикалық саласында Лаплас матрицасы, сондай-ақ граф Лапласы, өткізгіштік матрицасы, Кирхгофф матрицасы немесе дискретті Лаплас деп аталатын матрица, графтың матрицалық бейнелеуі болып табылады. Пьер Симон Лаплас есімімен аталған граф Лаплас матрицасын, граф үстіндегі теріс дискретті Лаплас операторы ретінде қарастыруға болады, бұл шекті айырмалар әдісімен алынған теріс үздіксіз Лаплас операторын шамалайды. Лаплас матрицасы графтың көптеген пайдалы қасиеттерімен байланысты. Кирхгофф теоремасымен бірге, ол берілген граф үшін қамтитын ағаштардың санын есептеу үшін қолданылуы мүмкін. Графтың ең сирек кесімдері Фидлер векторы арқылы жуықталады – бұл Шегер теңсіздігімен белгіленген граф Лапласының екінші ең кішкентай өзіндік мәніне сәйкес келетін өзіндік вектор. Лаплас матрицасының спектрлік декомпозициясы көптеген машиналық оқу қолданбаларында кездесетін төмен өлшемді енгізулерді құруға мүмкіндік береді және графты сызуда спектрлік орналасуды анықтайды. Графқа негізделген сигнал өңдеуі графтың Фурье түрленуіне негізделген, бұл сигналға сәйкес графтың Лаплас матрицасының өзіндік векторларымен күрделі синусоидалардың стандартты негізін ауыстыру арқылы дәстүрлі дискретті Фурье түрленуін кеңейтеді. Лаплас матрицасын қарапайым граф үшін анықтау оңай, бірақ жиектері салмақталған граф үшін, яғни жиектерінде салмақтары бар графтың жанындағы матрица элементтері үшін жиі қолданылады. Спектрлік граф теориясы графтың қасиеттерін оның спектрімен байланыстырады, яғни графпен байланысты матрицалардың (мысалы, оның жанындағы матрицасы немесе Лаплас матрицасы) өзіндік мәндерімен және өзіндік векторларымен. Теңгерімсіз салмақтар матрица спектріне кері әсер етуі мүмкін, сондықтан матрица элементтерінің баған/қатар масштабталуы – нормализация қажет болады, нәтижесінде нормаланған жанындағы және Лаплас матрицалары пайда болады.
In the mathematical field of graph theory, the Laplacian matrix, also called the graph Laplacian, admittance matrix, Kirchhoff matrix or discrete Laplacian, is a matrix representation of a graph. Named after Pierre Simon Laplace, the graph Laplacian matrix can be viewed as a matrix form of the negative discrete Laplace operator on a graph approximating the negative continuous Laplacian obtained by the finite difference method. The Laplacian matrix relates to many useful properties of a graph. Together with Kirchhoff's theorem, it can be used to calculate the number of spanning trees for a given graph. The sparsest cut of a graph can be approximated through the Fiedler vector — the eigenvector corresponding to the second smallest eigenvalue of the graph Laplacian — as established by Cheeger's inequality. The spectral decomposition of the Laplacian matrix allows constructing low dimensional embeddings that appear in many machine learning applications and determines a spectral layout in graph drawing. Graph based signal processing is based on the graph Fourier transform that extends the traditional discrete Fourier transform by substituting the standard basis of complex sinusoids for eigenvectors of the Laplacian matrix of a graph corresponding to the signal. The Laplacian matrix is the easiest to define for a simple graph, but more common in applications for an edge weighted graph, i. e., with weights on its edges — the entries of the graph adjacency matrix. Spectral graph theory relates properties of a graph to a spectrum, i. e., eigenvalues, and eigenvectors of matrices associated with the graph, such as its adjacency matrix or Laplacian matrix. Imbalanced weights may undesirably affect the matrix spectrum, leading to the need of normalization — a column/row scaling of the matrix entries — resulting in normalized adjacency and Laplacian matrices.
Лаплак матрицасының нормализациясы
Үлкен дәрежелі түйін, сондай-ақ ауыр түйін деп аталады, Лаплас матрицасындағы үлкен диагональдық элементке алып келеді, бұл матрицаның қасиеттерін анықтайды. Нормалдаудың мақсаты – мұндай түйіндердің басқа түйіндерге қарағанда ықпалын теңестіру, Лаплас матрицасының элементтерін түйіндердің дәрежелеріне бөлу арқылы. Нөлге бөлуді болдырмау үшін, нөлдік дәрежелі оқшауланған түйіндер нормалдау процесінен алынып тасталады.
Симметриялық нормаланған лаплациан
Симметриялық нормаланған Лаплас матрицасы былай анықталады: Бұл тұжырымдамада әрбір графтың төбесі тор нүктесі ретінде қарастырылады; төбелердің жергілікті байланысы осы тор нүктесіндегі шекті айырмашылықтарды есептеу схемасын анықтайды, тордың өлшемі әр қабырға үшін бірге тең болады және ешқандай тор нүктесінде шектеулер болмайды, бұл біртекті Нейман шекаралық шартына сәйкес келеді, яғни еркін шекара. Мұндай тұжырымдама, мысалы, Лаплас матрицасын шексіз көп төбелері мен қабырғалары бар графтар үшін жалпылауға мүмкіндік береді, нәтижесінде шексіз өлшемді Лаплас матрицасы пайда болады.
Бағытталған мультиграфтар
Бағытталған мультиграфтар үшін Лаплас матрицасының аналогын анықтауға болады. Бұл жағдайда Лаплас матрицасы L былай анықталады:
мұнда D – диагональдық матрица, оның Dі,і элементі i төбесінің шығу дәрежесіне тең, ал A – i-ден j-ге бағытталған қабырғалар санына тең Aі,j элементтері бар матрица (өздік циклдарды қоса алғанда).