Vés al contingut

Matriu laplaciana

De la Viquipèdia, l'enciclopèdia lliure

En el camp matemàtic de la teoria de grafs, la matriu laplacià, també anomenada graf laplacià, matriu d'admissió, matriu de Kirchhoff o laplacià discreta, és una representació matricial d'un graf. Anomenat després de Pierre-Simon Laplace, la matriu laplacià grafa es pot veure com una forma matricial de l'operador de Laplace discret negatiu en un graf que aproxima el laplacià continu negatiu obtingut pel mètode de diferències finites.[1]

La matriu laplaciana es relaciona amb moltes propietats útils d'un graf. Juntament amb el teorema de Kirchhoff, es pot utilitzar per calcular el nombre d'arbres que abasten un graf donat. El tall més escàs d'un graf es pot aproximar mitjançant el vector de Fiedler, el vector propi corresponent al segon valor propi més petit del graf Laplacià, tal com s'estableix per la desigualtat de Cheeger. La descomposició espectral de la matriu laplaciana permet construir incrustacions de dimensions baixes que apareixen en moltes aplicacions d'aprenentatge automàtic i determina un disseny espectral en el dibuix de grafs. El processament del senyal basat en grafs es basa en la transformada de Fourier d'un graf que amplia la transformada de Fourier discreta tradicional substituint la base estàndard de sinusoides complexos per vectors propis de la matriu laplacià d'un graf corresponent al senyal.[2]

La matriu laplaciana és la més fàcil de definir per a un graf simple, però més comuna en aplicacions per a un graf ponderat per arestes, és a dir, amb pesos a les seves vores, les entrades de la matriu d'adjacència del graf. La teoria de grafs espectrals relaciona les propietats d'un graf amb un espectre, és a dir, els valors propis i els vectors propis de les matrius associades amb el graf, com ara la seva matriu d'adjacència o la matriu laplaciana. Els pesos desequilibrats poden afectar indesitjablement l'espectre de la matriu, donant lloc a la necessitat de normalització (una escala de columna/fila de les entrades de la matriu) donant lloc a una adjacència normalitzada i matrius laplacianes.[3]

Definicions de grafs senzills

[modifica]

Matriu laplaciana

[modifica]

Donat un graf senzill amb vèrtexs , la seva matriu laplaciana es defineix per elements com [4]

o equivalent per la matriu

on D és la matriu de graus i A és la matriu d'adjacència del graf. Des que és un graf senzill, només conté 1 o 0 i els seus elements diagonals són tots 0.

Aquí teniu un exemple senzill d'un graf etiquetat i no dirigit i la seva matriu laplaciana.[5]

Graf etiquetat Matriu de graus Matriu d'adjacència

Observem per al graf no dirigit que tant la matriu d'adjacència com la matriu laplaciana són simètriques, i que les sumes de files i columnes de la matriu laplaciana són zeros (la qual cosa implica directament que la matriu laplaciana és singular).

Per als grafs dirigits, es pot utilitzar el grau o el grau superior, segons l'aplicació, com a l'exemple següent:

graf etiquetat Matriu d'adjacència Matriu fora de grau

En el graf dirigit, tant la matriu d'adjacència com la matriu laplaciana són asimètriques. En la seva matriu laplaciana, les sumes de columnes o les sumes de files són zero, depenent de si s'ha utilitzat el grau o el grau superior.

Referències

[modifica]
  1. «The graph Laplacian» (en anglès), 11-11-2020. [Consulta: 15 agost 2024].
  2. «[https://csustan.csustan.edu/~tom/Clustering/GraphLaplacian-tutorial.pdf A Short Tutorial on Graph Laplacians, Laplacian Embedding, and Spectral Clustering]» (en anglè). [Consulta: 15 agost 2024].
  3. «Laplacian Matrices | An Introduction to Algebraic Graph Theory» (en anglès). [Consulta: 15 agost 2024].
  4. Chung, Fan. Spectral Graph Theory (en anglès). American Mathematical Society, 1997. ISBN 978-0821803158. 
  5. Weisstein, Eric W. «Laplacian Matrix» (en anglès). [Consulta: 15 agost 2024].