Matriu laplaciana

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]

Donat un graf senzill ${\displaystyle G}$ amb ${\displaystyle n}$ vèrtexs ${\displaystyle v_{1},\ldots ,v_{n}}$, la seva matriu laplaciana ${\textstyle L_{n\times n}}$ es defineix per elements com ^[4]

${\displaystyle L_{i,j}:={\begin{cases}\deg(v_{i})&{\mbox{si}}\ i=j\\-1&{\mbox{si}}\ i\neq j\ {\mbox{i}}\ v_{i}{\mbox{ és adjacent a }}v_{j}\\0&{\mbox{altrament}},\end{cases}}}$

o equivalent per la matriu

${\displaystyle L=D-A,}$

on D és la matriu de graus i A és la matriu d'adjacència del graf. Des que ${\textstyle G}$ és un graf senzill, ${\textstyle A}$ 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
	${\textstyle \left({\begin{array}{rrrrrr}2&0&0&0&0&0\\0&3&0&0&0&0\\0&0&2&0&0&0\\0&0&0&3&0&0\\0&0&0&0&3&0\\0&0&0&0&0&1\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrrrrr}0&1&0&0&1&0\\1&0&1&0&1&0\\0&1&0&1&0&0\\0&0&1&0&1&1\\1&1&0&1&0&0\\0&0&0&1&0&0\\\end{array}}\right)}$

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
	${\textstyle \left({\begin{array}{rrr}0&1&1\\0&0&1\\1&0&0\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrr}2&0&0\\0&1&0\\0&0&1\\\end{array}}\right)}$

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.