Representations | Sahithyan's Notes

A graph can be represented in multiple ways.

Diagrammatic Representation

Vertices are denoted by points, edges are denoted by lines. Intuitive. Not practical for big graphs.

A graph $G$ is represented as an ordered pair $(V, E)$ where:

$V$ is the set of vertices
$E$ is the set of edges (2-element subsets of $V$ for simple graphs; multi-sets for multigraphs)

An adjacency matrix records how many edges connect each pair of vertices. Shows vertex-vertex relationships.

Suppose a graph $G$ has $n$ vertices. $G$ ’s adjacency matrix representation is defined as:

A(G) = (a_{ij})_{n\times n}

Where $a_{ij}$ is the number of edges between $v_i$ and $v_j$ .

For undirected graphs, $A(G)$ is a symmetric matrix.

For simple graphs:

If $A$ is the adjacency matrix of $G$ , entry $(i, j)$ of $A^m$ is equal to the number of walks of length $m$ from $v_i$ to $v_j$ .

Useful for dense graphs (close to the maximum number of edges).

Shows vertex-edge relationships.

For a graph $G$ with $n$ vertices and $m$ edges. Its incidence matrix representation is defined as:

I(G) = (a_{ij})_{n\times m}

is defined as:

$a_{ij} = 1$ if vertex $v_i$ is incident with edge $e_j$ and the edge joins two distinct vertices
$a_{ij} = 2$ if $e_j$ is a loop at $v_i$
$a_{ij} = 0$ otherwise

Rows correspond to vertices. Columns correspond to edges.

Useful for edge-based algorithms. Useful for sparse graphs.

Let $e_j$ be an edge from head $u$ to tail $v$ . Then:

a_{ij} = \begin{cases} 1 & \text{if } v_i \text{ is the tail of } e_j \\ -1 & \text{if } v_i \text{ is the head of } e_j \\ 2 & \text{if } e_j \text{ is a loop at } v_i \\ 0 & \text{otherwise} \end{cases}