3.1 Adjacency matrices and incidence matrices

Matrices offer powerful ways to represent graphs mathematically. Adjacency matrices use a square format to show connections between vertices, while incidence matrices use a rectangular format to explicitly represent edges.

These matrix representations have different strengths. Adjacency matrices are great for dense graphs and quick edge queries, while incidence matrices work well for sparse graphs and maintaining explicit edge information.

Graph Representation Matrices

Definition of adjacency matrices

• Square matrix represents graph structure with rows and columns corresponding to vertices
• Entries indicate presence or absence of edges between vertex pairs
• Symmetric matrix for simple undirected graphs with diagonal entries typically 0
• May not be symmetric for directed graphs, entry $(i,j)$ represents edge from vertex $i$ to $j$
• Matrix entries interpret edge relationships (0: no edge, 1: edge exists, other values: edge weights)

Construction of adjacency matrices

• Undirected graphs fill matrix symmetrically $A_{ij} = A_{ji} = 1$ for existing edges
• Directed graphs set $A_{ij} = 1$ for edges from $i$ to $j$, $A_{ji}$ may differ
• Weighted graphs replace 1s with edge weights, 0 still indicates no edge
• Self-loops represented by non-zero diagonal entries
• Multiple edges summed in edge counts or weights

Incidence matrices vs adjacency matrices

• Incidence matrix: rectangular, rows for vertices, columns for edges
• Undirected graphs: 1 if vertex incident to edge, 0 otherwise
• Directed graphs: -1 for tail, 1 for head, 0 for non-incident
• Both represent graph structure, incidence matrices show explicit edge info
• Adjacency matrices focus on vertex connections

Conversion between matrix representations

• Adjacency to incidence: create column for each non-zero adjacency entry
• Incidence to adjacency: multiply incidence matrix by transpose $A = MM^T$
• Conversion may lose multiple edge information
• Directed graph conversion requires additional steps

Space complexity of matrix storage

• Adjacency matrix: $O(|V|^2)$ space, efficient for dense graphs
• Incidence matrix: $O(|V||E|)$ space, better for sparse graphs
• Adjacency matrices suit graphs with $|E|$ close to $|V|^2$
• Incidence matrices preferred when $|E|$ much less than $|V|^2$
• Adjacency matrices allow faster edge queries
• Incidence matrices provide explicit edge representation