laplacian

Matriz Laplaciana de um grafo.

Categoria: Mathematics > Graph and Network Algorithms

Sintaxe

L = laplacian(G)

Descrição

Cada linha de L soma zero, então o vetor de uns é um autovetor com autovalor 0. O número de autovalores nulos é igual ao número de componentes conexos, e o segundo menor autovalor mede quão bem conexo é o grafo. Os autovetores são usados em particionamento espectral e no desenho de grafos.

Argumentos de entrada

G

Um graph.

Argumentos de saída

L

Matriz simétrica numnodes(G)-por-numnodes(G) com os graus dos nós na diagonal e -1 onde dois nós são adjacentes.

Exemplo

Conectividade pelos autovalores

G = graph([1 2 4], [2 3 5]);
L = laplacian(G);
ev = eig(L)'
sum(abs(ev) < 1e-10)
[~, sizes] = conncomp(G)

ev = 1×5

   -0.0000         0    1.0000    2.0000    3.0000
ans = 2
sizes = 1×2

     3     2

Observações

O MatLivre retorna matrizes cheias (densas) aqui, enquanto o MATLAB retorna matrizes esparsas. Valores e tamanhos são os mesmos.

Veja também

adjacency degree incidence eig conncomp