NoteVerse

Incidence matrix

Comprehensive study notes, diagrams, and exam preparation for Incidence matrix.

Incidence Matrix

Definition

An incidence matrix is a fundamental data structure in graph theory used to represent a graph. It is a rectangular matrix that shows the relationship between vertices (nodes) and edges (links) in a graph. Each row of the matrix corresponds to a vertex, and each column corresponds to an edge. The entries in the matrix indicate whether a vertex is an endpoint of a particular edge.

Main Content

1. Structure of an Incidence Matrix

The structure of an incidence matrix depends on whether the graph is undirected or directed.

  • For Undirected Graphs:
    • The matrix $M$ has dimensions $V \times E$, where $V$ is the number of vertices and $E$ is the number of edges.
    • An entry $M_{ij}$ is typically '1' if vertex $i$ is incident to edge $j$ (i.e., vertex $i$ is one of the two endpoints of edge $j$).
    • An entry $M_{ij}$ is '0' if vertex $i$ is not incident to edge $j$.
    • Example: Consider a simple undirected graph (Graph 1) with 4 vertices and 4 edges: (A)---e1---(B) | | e4 e2 | | (D)---e3---(C) The incidence matrix for Graph 1 would be: | | e1 | e2 | e3 | e4 | |---|----|----|----|----| | A | 1 | 0 | 0 | 1 | | B | 1 | 1 | 0 | 0 | | C | 0 | 1 | 1 | 0 | | D | 0 | 0 | 1 | 1 |

2. Properties of an Incidence Matrix

The arrangement of 0s and 1s (or -1s) in an incidence matrix reveals several important properties about the graph:

  • Column Sums (Undirected Graphs): For an undirected graph without loops (edges connecting a vertex to itself), the sum of entries in each column is always '2'. This is because every edge connects exactly two distinct vertices, and thus has '1's in exactly two rows corresponding to its endpoints. If a graph has a self-loop, the column for that loop would have a sum of '1' (as it is incident to only one vertex, twice).
  • Row Sums (Undirected Graphs): The sum of entries in each row represents the degree of the corresponding vertex. The degree of a vertex is the number of edges incident to it. Each '1' in a row indicates an edge connected to that vertex.
  • Parallel Edges: If a graph contains parallel edges (multiple edges connecting the same pair of vertices), they will appear as identical columns in the incidence matrix. Each parallel edge gets its own distinct column.
  • Disconnected Components: A graph with multiple disconnected components will have its incidence matrix partitioned into blocks, where each block represents a component.

3. Directed Incidence Matrix (Oriented Incidence Matrix)

For directed graphs (digraphs), the incidence matrix is modified to reflect the direction of edges.

  • For Directed Graphs:
    • The matrix $M$ still has dimensions $V \times E$.
    • An entry $M_{ij}$ is '1' if vertex $i$ is the head (destination) of directed edge $j$.
    • An entry $M_{ij}$ is '-1' if vertex $i$ is the tail (source) of directed edge $j$.
    • An entry $M_{ij}$ is '0' if vertex $i$ is not incident to edge $j$.
    • Column Sums (Directed Graphs): The sum of entries in each column is always '0'. This is because every directed edge has exactly one head (+1) and one tail (-1).
    • Example: Consider a simple directed graph (Graph 2) with 4 vertices and 4 directed edges: (A) ---e1---> (B) ^ | | e2 e4 v | | (D) <---e3---- (C) The incidence matrix for Graph 2 would be: | | e1 | e2 | e3 | e4 | |---|----|----|----|----| | A | -1 | 0 | 0 | 1 | | B | 1 | -1 | 0 | 0 | | C | 0 | 1 | -1 | 0 | | D | 0 | 0 | 1 | -1 |

Working / Process

1. Constructing an Undirected Incidence Matrix

To build an incidence matrix for an undirected graph:

  • Identify Vertices and Edges: First, list all the vertices ($V_1, V_2, ..., V_n$) and all the edges ($e_1, e_2, ..., e_m$) in your graph.
  • Create Matrix Structure: Draw an empty matrix with $n$ rows (one for each vertex) and $m$ columns (one for each edge). Label the rows with vertex names and columns with edge names.

  • Populate Entries: Go through each edge one by one. For an edge $e_j$ connecting vertices $V_a$ and $V_b$:

    • Place a '1' in the cell corresponding to row $V_a$ and column $e_j$.
    • Place a '1' in the cell corresponding to row $V_b$ and column $e_j$.
    • For all other rows (vertices) in column $e_j$, place a '0'.
    • Repeat this for all edges.

    Example: Let's construct an incidence matrix for a graph with vertices {1, 2, 3} and edges {e1=(1,2), e2=(2,3), e3=(1,3)}.

    1. Vertices: {1, 2, 3}; Edges: {e1, e2, e3}
    2. Matrix will be 3x3.

    3. Populate:

      • e1 connects 1 and 2: $M_{1,e1}=1, M_{2,e1}=1$.
      • e2 connects 2 and 3: $M_{2,e2}=1, M_{3,e2}=1$.
      • e3 connects 1 and 3: $M_{1,e3}=1, M_{3,e3}=1$.

      Resulting Matrix: | | e1 | e2 | e3 | |---|----|----|----| | 1 | 1 | 0 | 1 | | 2 | 1 | 1 | 0 | | 3 | 0 | 1 | 1 |

2. Constructing a Directed Incidence Matrix

To build an incidence matrix for a directed graph:

  • Identify Vertices and Directed Edges: List all the vertices ($V_1, V_2, ..., V_n$) and all the directed edges ($e_1, e_2, ..., e_m$), noting their source (tail) and destination (head) vertices.
  • Create Matrix Structure: Draw an empty matrix with $n$ rows (for vertices) and $m$ columns (for directed edges). Label rows with vertex names and columns with edge names.

  • Populate Entries: Go through each directed edge one by one. For a directed edge $e_j$ from vertex $V_{source}$ to vertex $V_{destination}$:

    • Place a '-1' in the cell corresponding to row $V_{source}$ and column $e_j$.
    • Place a '+1' in the cell corresponding to row $V_{destination}$ and column $e_j$.
    • For all other rows (vertices) in column $e_j$, place a '0'.
    • Repeat this for all directed edges.

    Example: Let's construct a directed incidence matrix for a graph with vertices {A, B, C} and directed edges {e1: A->B, e2: B->C, e3: C->A}.

    1. Vertices: {A, B, C}; Edges: {e1, e2, e3}
    2. Matrix will be 3x3.

    3. Populate:

      • e1: A->B: $M_{A,e1}=-1, M_{B,e1}=1$.
      • e2: B->C: $M_{B,e2}=-1, M_{C,e2}=1$.
      • e3: C->A: $M_{C,e3}=-1, M_{A,e3}=1$.

      Resulting Matrix: | | e1 | e2 | e3 | |---|----|----|----| | A | -1 | 0 | 1 | | B | 1 | -1 | 0 | | C | 0 | 1 | -1 |

3. Extracting Information from an Incidence Matrix

Once an incidence matrix is constructed, you can derive various properties of the graph:

  • Vertex Degrees: For undirected graphs, sum the '1's in each row to find the degree of that vertex. For directed graphs, the sum of '-1's in a row gives the out-degree (edges originating from the vertex), and the sum of '1's gives the in-degree (edges terminating at the vertex). The absolute sum of values in a row gives the total degree.
  • Identifying Edges and Their Endpoints: Each column directly tells you which vertices are connected by that specific edge. For example, in an undirected matrix, a column with '1's in rows $V_a$ and $V_b$ means edge $e_j$ connects $V_a$ and $V_b$. In a directed matrix, a column with '-1' in row $V_a$ and '1' in row $V_b$ means edge $e_j$ goes from $V_a$ to $V_b$.
  • Parallel Edges and Loops: Identify parallel edges by looking for identical columns (for undirected graphs) or columns with the same -1/+1 pattern (for directed graphs). A self-loop in an undirected graph would appear as a column with a single '1' (at the row of the vertex it loops to).

Advantages / Applications

  • Direct Edge-Vertex Relationship: Provides an explicit and clear representation of which vertices are connected by which edges, which is useful in algorithms that process edges individually.
  • Handling Parallel Edges and Loops: Easily accommodates graphs with multiple edges between the same two vertices (parallel edges) or edges connecting a vertex to itself (self-loops), by assigning each a distinct column. Adjacency matrices typically struggle with this without modification.
  • Network Flow and Electrical Networks: Incidence matrices are fundamental in setting up systems of linear equations for analyzing network flow problems (e.g., maximum flow, minimum cut) and electrical circuits (e.g., Kirchhoff's laws), where edges represent conduits or wires.
  • Graph Isomorphism Testing (Advanced): While not straightforward, the incidence matrix can sometimes be used in conjunction with other techniques for determining if two graphs have the same structure.
  • Basis for Cycle and Cut Spaces: In algebraic graph theory, the incidence matrix is crucial for defining the cycle space and cut space of a graph, which are fundamental vector spaces over the field of two elements ($GF(2)$).

Summary

An incidence matrix is a matrix representation of a graph where rows correspond to vertices and columns correspond to edges. Its entries indicate the relationship between vertices and edges, typically using 0 and 1 for undirected graphs (showing incidence) or -1, 0, and 1 for directed graphs (showing incidence and direction). It effectively captures the detailed connectivity structure, making it particularly useful for network analysis and algorithms that require explicit edge-vertex relationships.

← Prev: Tree and Tree branch & link
Next: cut set and tie set matrices →