컴퓨터에서 그래프로 작업하려면 컴퓨터 프로그램에서 그래프를 어떻게 표현하는지 알아야 한다. 그전에 그래프의 수학적 정의를 간단히 살펴보자. 일반적으로 정점들의 집합을 V, 간선들의 집합을 E라고 하며, 하나의 그래프 G는 G = (V, E)로 정의한다.

무방향 그래프에서 집합 E는 두 개의 노드 x와 y 사이의 각 간선에 대해 두 원소의 집합 {x, y}로 구성되는 집합이며, 일반적으로 {x, y} 대신에 (x, y)로 쓴다. 두 가지 모두 x와 y의 순서는 고려하지 않는다. 그림 2-5의 (a)에 있는 그래프는 다음과 같이 정의된다.

 

방향 그래프에서 집합 E는 두 노드 x와 y 사이의 간선을 나타내는 튜플 (x, y)들의 집합이며, x와 y 사이의 순서가 중요하다. 그림 2-5의 (b)에 있는 그래프는 다음과 같이 정의된다.

 

그래프의 수학적 정의를 보면 그래프를 나타내는 정점과 간선을 표현하는 방법이 필요하다. 그래프 G를 표현하는 직접적인 방법은 행렬을 사용하는 것이다. 인접 행렬(adjacency matrix)이라 불리는 이 행렬은 각 정점이 행과 열이 되는 정방 행렬 또는 정사각 행렬(square matrix)이고, 행렬의 값은 0과 1이다. i번째 행으로 표현된 정점이 j번째 열로 연결된 정점과 연결되면 행렬의 원소 (i, j)는 1이 되고, 연결되지 않으면 그 값은 0이 된다. 인접 행렬에서 정점은 행과 열의 인덱스로 표현되고, 간선들은 그 행렬의 값으로 표현된다.