DISCRETE MATHEMATICS: MATRIX REPRESENTATIONS
OF GRAPHS
PAGE 1: INTRODUCTION AND ADJACENCY MATRIX
What are Matrices and Graphs?
In discrete mathematics, both matrices and graphs are fundamental structures. A
matrix is a rectangular array of numbers, symbols, or expressions, arranged in
rows and columns. A graph is a collection of vertices (or nodes) connected by
edges (or links).
Matrices provide a powerful and structured way to represent and analyze graphs,
enabling us to perform computations on graph properties.
The Adjacency Matrix
The adjacency matrix is one of the most common ways to represent a graph. For a
graph with $n$ vertices, the adjacency matrix $A$ is an $n imes n$ matrix where:
• $A_{ij} = 1$ if there is an edge connecting vertex $i$ and vertex $j$.
• $A_{ij} = 0$ if there is no edge connecting vertex $i$ and vertex $j$.
For undirected graphs, the adjacency matrix is symmetric ($A_{ij} = A_{ji}$).
Example: Adjacency Matrix
Consider an undirected graph with 3 vertices, labeled 1, 2, and 3, and edges {(1, 2),
(2, 3)}.
The adjacency matrix would be:
1 2 3
1[0 1 0]
2[1 0 1]
3[0 1 0]
PAGE 2: INCIDENCE MATRIX AND CONCLUSION
The Incidence Matrix
Another useful representation is the incidence matrix. For a graph with $n$ vertices
and $m$ edges, the incidence matrix $I$ is an $n imes m$ matrix where:
• $I_{ij} = 1$ if vertex $i$ is an endpoint of edge $j$.
• $I_{ij} = 0$ if vertex $i$ is not an endpoint of edge $j$.
For undirected graphs, each column (representing an edge) will have exactly two
1s, corresponding to its two endpoints.
Example: Incidence Matrix
Using the same graph as before, with vertices {1, 2, 3} and edges {e1=(1, 2), e2=(2,
3)}:
The incidence matrix would be:
e1 e2
1[1 0]
2[1 1]
3[0 1]
Conclusion
Matrix representations like the adjacency and incidence matrices are crucial tools in
graph theory and computer science. They allow for efficient algorithms related to
graph traversal, connectivity, and analysis. Different representations have different
strengths and are suited for various types of problems.