incidence

Matriz de incidência: quais arestas tocam quais nós.

Categoria: Mathematics > Graph and Network Algorithms

Sintaxe

I = incidence(G)

Descrição

Cada coluna descreve uma aresta, então toda coluna tem exatamente um -1 e um 1 (um laço dá uma coluna de zeros). Multiplicar I pela sua transposta dá o Laplaciano do grafo: I*I' é igual a laplacian(G) para um grafo não direcionado sem laços.

A matriz de incidência é a base das formulações de fluxo e de circuitos em rede, em que expressa a conservação: I*f é o fluxo líquido que entra em cada nó para um vetor de fluxos f nas arestas.

Argumentos de entrada

G

Um graph ou digraph.

Argumentos de saída

I

Matriz com numnodes(G) linhas e numedges(G) colunas. A coluna k tem -1 no nó de origem da aresta k, 1 no nó de destino e zeros no resto.

Exemplo

Incidência e Laplaciano

G = graph([1 1 2 3], [2 3 3 4]);
I = incidence(G)
isequal(I*I', laplacian(G))

I = 4×4

    -1    -1     0     0
     1     0    -1     0
     0     1     1    -1
     0     0     0     1
ans = logical
   1

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 laplacian degree graph