incidence matrix
An incidence matrix (also node-edge matrix ) of a graph is a matrix which stores the relations of the nodes and edges of the graph. If the graph nodes and edges is its incidence matrix of a matrix. The entry in the i- th column and j -th row indicates whether the i-th edge contains the j-th node. If at this point a 1, an incidence relationship exists at a 0, there is no incidence ago. It is assumed that the nodes are numbered consecutively from 1 to n, and the edges of 1 to m.
- 2.1 Undirected Graphs
- 2.2 Directed graphs
- 3.1 Storage of graphs in the computer
- 3.2 Spectral Graph Theory
Definition
Undirected graphs
For a loop-free undirected graph with and the incidence matrix is formally defined by:
The incidence matrix of an undirected graph thus contains in each column exactly two entries different from 0
Directed graphs
For a loop-free, directed graph with and the incidence matrix is defined by:
Which here represents any node.
The incidence matrix of a directed graph thus contains in each column exactly once ( start node ) and once the ( end nodes ).
Examples
Undirected graphs
We now examine an example graph of the house of Nicholas as it is shown on the right with the given numbering of nodes and edges. To create this graph from an incidence matrix, we begin with an empty matrix. This includes for the graph in columns and rows. The edges are entered into the column and the corners in the line.
The numbers on the edges are not to be confused with weights of edges. Describe the names of the edges which are later on in the matrix columns.
Now ( edge ) are marked with the corresponding node 1 for each column, all other nodes with 0, it results in the following incidence matrix:
Is the incidence matrix constructed correctly, then it must be in total 2 since each edge connects exactly two points in each column ( edge). If a point connected to itself, stands in the corresponding cell a second The sum of each row corresponds to the edges that lead to the corresponding point.
Directed graphs
As an example, an incidence matrix of a directed graph, we now consider the rightmost graph. Again we take the numbering of the nodes as specified. The edges are numbered as follows: It is. The incidence matrix is thus a matrix.
The incidence matrix is constructed correctly: In each column, there are two non-zero entries, which cancel to zero.
Use
Storing graphs in the computer
Incidence matrices are used in computer science for storing graphs. The incidence matrix of a graph with nodes and edges requires a memory of. This is an advantage over storing the adjacency matrix for thin graphs with few edges.
Spectral Graph Theory
Furthermore, incidence matrices find applications in the spectral graph theory, where attempts due to certain properties of the incidence matrix to draw conclusions about the properties of the represented graph.