Main Content

incidence

Graph incidence matrix

Description

I = incidence(G) returns the sparse incidence matrix for graph G. If s and t are the node IDs of the source and target nodes of the jth edge in G, then I(s,j) = -1 and I(t,j) = 1. That is, each column of I indicates the source and target nodes for a single edge in G.

example

Examples

collapse all

Create a graph using an edge list, and then calculate the graph incidence matrix.

s = [1 1 1 1 1];
t = [2 3 4 5 6];
G = graph(s,t);
I = incidence(G)
I = 6x5 sparse double matrix (10 nonzeros)
   (1,1)       -1
   (2,1)        1
   (1,2)       -1
   (3,2)        1
   (1,3)       -1
   (4,3)        1
   (1,4)       -1
   (5,4)        1
   (1,5)       -1
   (6,5)        1

Each column in I contains two nonzero entries, which indicate the end nodes of a single edge in G.

Calculate the graph Laplacian matrix, L, and confirm the relation L = I*I' for undirected graphs.

L = laplacian(G);
L - I*I'
ans = 6x6 sparse double matrix
   All zero

Create a directed graph using an edge list, and then calculate the incidence matrix.

s = [1 2 1 3 2 3 3 3];
t = [2 1 3 1 3 4 5 6];
G = digraph(s,t)
G = 
  digraph with properties:

    Edges: [8x1 table]
    Nodes: [6x0 table]

I = incidence(G)
I = 6x8 sparse double matrix (16 nonzeros)
   (1,1)       -1
   (2,1)        1
   (1,2)       -1
   (3,2)        1
   (1,3)        1
   (2,3)       -1
   (2,4)       -1
   (3,4)        1
   (1,5)        1
   (3,5)       -1
   (3,6)       -1
   (4,6)        1
   (3,7)       -1
   (5,7)        1
   (3,8)       -1
   (6,8)        1

Each column in I represents the source and target nodes of a single edge in G.

Input Arguments

collapse all

Input graph, specified as either a graph or digraph object. Use graph to create an undirected graph or digraph to create a directed graph.

Example: G = graph(1,2)

Example: G = digraph([1 2],[2 3])

Output Arguments

collapse all

Incidence matrix, returned as a sparse matrix. The size of I is numnodes(G)-by-numedges(G). The graph incidence matrix is undefined for graphs with self-loops.

Tips

  • The incidence function calculates the variety of incidence matrix commonly known as a signed or oriented incidence matrix. The signed incidence matrix of an undirected graph, I, is related to the graph Laplacian matrix, L, such that L == I*I'.

Extended Capabilities

Thread-Based Environment
Run code in the background using MATLAB® backgroundPool or accelerate code with Parallel Computing Toolbox™ ThreadPool.

Version History

Introduced in R2015b