그래프는 정점(Vertex)과 정점들을 연결하는 변(Edge)으로 구성이 된다. 일반적으로 정점은 원으로 표현하고 변은 화살표나 선분으로 표현한다. 변을 화살표로 나타내는 경우에는 해당 방향으로만 이동할 수 있으며, 이러한 그래프를 유향 그래프(Directed graph)라고 말한다. 반대로 선분으로 표현되는 경우에는 양방향 모두 이동이 가능하며, 이러한 그래프를 무향 그래프(Undirected graph)라고 말한다. 그리고 변의 경우에는 특정한 수치를 가질 수 있는데 이를 가중치(Weighted value)라고 말한다.

예를 들어 도시를 정점으로 생각하고 도시 사이를 잇는 도로를 변으로 생각하면 그래프는 곧 하나의 간략화된 지도가 된다. 위의 그림에서 1~6번 원이 도시고 연결선이 도로인 셈. 여기에 각 도로마다 도로의 길이 또는 이용 요금을 써 넣으면 이것이 바로 그 도로의 가중치이다.

위에서 알 수 있듯이 그래프는 도시와 도로로도 비유될 수 있기 때문에 두 지점 간의 최단 경로(또는 가장 저렴한 경로)를 구하는 데 널리 이용된다. 그래프는 도시-도로뿐만 아니라 컴퓨터 통신망, SNS에서의 친구관계 등등 여러 상황을 모델링 할 수 있어 많은 분야에서 널리 사용된다. 예를 들어 어떤 웹 페이지를 정점으로 하고 페이지에 달린 링크들을 다른 페이지로 가는 변이라고 보면, 나무위키 역시 하나의 거대한 그래프라고 볼 수 있다.

위의 그림에서는 2,3,4,5번 도시(정점)들이 서로 연결되어 순환할 수 있다. 다시 말해서 2번 도시에서 출발하여 3,4,5번 도시를 거쳐 다시 2번에 도착할 수 있다는 것. 이와는 반대로, 이렇게 순환하지 않는 그래프를 특히 트리(그래프)라고도 부른다.

순수수학에서는 수학자 오일러가 한붓그리기 문제, 즉 쾨니히스베르크 다리 건너기 문제를 푼 것을 그래프 이론의 시작으로 보고 있다. 이 외에도 그래프 이론에서 대중에게 비교적 친숙한 문제로는 4색 정리나 해밀턴 경로[1] 등이 있을 것이다.

과거 2007 개정 교육과정까지 고등학교 수학에 등장했던 '행렬과 그래프'라는 단원에서의 그래프는 해석학적인 그래프가 아니라 바로 이 그래프를 뜻한다.

그래프는 일반적으로 위 그림과 같이 점과 선분을 이용한 그림으로써 표현되는 경우가 많다. 그러나 그래프 이론 또한 수학의 한 분야인 이상, 이를 이용하여 정리를 세우거나, 각종 문제를 풀기 위해서는 우선 그래프와 그에 관련된 개념을 수학적으로 엄밀하게 정리할 필요가 있다. 그래프와 관련된 용어는 집합과 함수 등을 이용하여 정의될 수 있다.

예를 들어, 위 그림의 그래프를 $G = (V, E)$라 했을 때 꼭짓점의 집합 $V$와 변의 집합 $E$를 엄밀하게 정의하면 다음과 같다.


그래프 이론이 비교적 최근에 생긴 이론인 만큼 시간대나 활용하는 분야에 따라 같은 정의라도 용어가 다르거나, 심지어 정의 자체가 다른 경우도 있다. 그러므로 위키러는 상황에 따라 용어를 유동적으로 해석할 수 있어야 하며, 정의를 분명하게 명시해야만 한다. 예를 들어 '꼭짓점(vertex)'은 컴퓨터공학을 비롯한 공학계열에서는 '노드(node)'라는 이름으로 불리기도 한다. 사정이 이렇다보니 이를 번역한 교재에 따라 한국어 번역이 중구난방이다.

그래프는 그래프 이론에서 다루는 수학적 대상이다. 그래프 이론의 초기에는 그래프가 한 종류였지만, 현대에 들어 전산학, 전자공학 등의 발전으로 인해 여러 변형이 생겼다.

그래프(graph) $G$는 꼭짓점의 집합 $V$[2]와 변의 집합 $E$의 순서쌍으로 정의된다. 즉,

당연하게도 $V$의 원소는 꼭짓점(vertex), $E$의 원소는 변(모서리, edge)라 부른다. 흔히 그림에서 꼭지점은 점이나 원으로 표현되고, 변은 두 끝점을 잇는 선분으로 표현된다.

변의 집합 $E$는 모든 $e \in E$가 $v_1, v_2 \in V$에 대해

가 되도록 정의한다. 이 때 $v_1, v_2$를 $e$의 끝점(endpoint)이라 하고, $v_1$과 $v_2$는 서로 인접한다(adjacent) 또는 이웃한다(neighbor)고 한다. '$e$는 $v_1, v_2$와 붙어있다(incident)' 또는 '$v_1, v_2$를 연결한다(connect)'고 한다. 두 꼭짓점 $v_1$, $v_2$를 연결하는 변을 간단히 $v_{1}v_{2}$와 같이 표기하기도 한다.

그래프의 정의 중 $e \in E$에 대한 정의를 다음과 같이 바꾸어 준 것을 유향그래프(directed graph, digraph)라고 한다.

보다시피, 순서를 나타내기 위해 집합이 아닌 순서쌍을 이용하였다. 여기서 $e$는 유향변(방향모서리, directed edge 또는 arc)이라고 한다. 이때, $v_1$은 $e$의 시점, $v_2$은 $e$의 종점이라 하며, '$e$는 $v_1$에서 시작하여 $v_2$에서 끝난다', 또는 '$v_1$에서 $v_2$로 간다'와 같이 표현한다. 흔히 그림에서 유향변은 시점에서 종점으로 향하는 화살표로 표현된다.

한편, 유향그래프가 아닌 그래프를 무향그래프(비방향성 그래프, undirected graph)라 한다.

유향그래프는 무향그래프와 달리 두 정점 사이의 단방향적인 관계를 표현할 수 있다.

다중그래프(multigraph)는 두 꼭짓점을 연결하는 변이 여러 개인 그래프이다. 엄밀하게는, 그래프의 정의를 다음과 같이 변형한 것을 다중그래프라고 한다.

여기서 $\partial : E \to S^2(V)$는 함수이고, 공역 $S^2(V) = \left\{ \left\{ u, v \right\}|u, v \in V \right\}$이다. 즉, $S^2(A)$는 $A$의 부분집합들 중 원소가 2개인 것만 원소로 하는 집합족이다.

이전의 정의와는 달리, $E$의 원소, 즉 변은 끝점을 이용하여 정의되지 않는다. 그 대신 어떤 변이 어떤 두 끝점과 연결되는지를 함수 $\partial$로 정의하는 것이다. 예를 들어 $\partial e_1 = \{u, v\}$라면 변 $e_1$의 끝점은 $u$와 $v$라는 뜻이다. $\partial e = \{u, v\}$가 되는 변 $e$는 $e_1$ 이외에도 여러 개가 있을 수 있는데, 이 경우 두 꼭짓점은 여러 변과 연결되어 있다고 할 수 있는 것이다.

다중그래프가 아닌 그래프를 단순 그래프(simple graph)라 한다.

다중그래프는 단순그래프와 달리 두 정점 사이의 여러 관계를 표현할 수 있다.

다중 그래프에도 변의 방향을 적용하는 방법을 생각할 수 있다. 그러나 다중 그래프에서는 변의 두 끝점을 $E$의 정의가 아닌 새로운 함수 $\partial$를 이용해 결정했으므로, 유향 다중그래프(directed multigraph)는 다음과 같이 $\partial$의 공역을 고쳐 새롭게 정의해야 한다.

여기서 $V^2 = V \times V = \left\{ \left( u, v \right)|u, v \in V \right\}$이다. 즉, 유향 그래프와 마찬가지로 두 꼭짓점들의 집합을 순서쌍으로 바꾼 것이다.

가중 그래프(weighted graph)는 각각의 변에 가중치(weight)라 불리는 값을 대응한 그래프이다. 엄밀하게는 가중치 함수 $W : E \to \mathbb{R}$를 추가한 그래프로 정의할 수 있다.

가중치는 그래프 모델이 쓰이는 상황에 따라 다르게 정의되어 다양하게 활용될 수 있다. 예를 들어 비행기의 항로를 그래프로 모델링한다면, 운항 거리, 시간, 항공비 등을 가중치로 고려할 수 있는데, 최단 경로 문제의 풀이법을 이용하면 '목적지까지 가장 빨리, 비용이 적게 도착할 수 있는 항공편은?' 같은 질문에 답할 수 있게 된다.

Complete graph
모든 서로 다른 꼭짓점끼리 연결되는 그래프를 말한다. 이때 꼭짓점이 $n$개인 그래프를 n-완전 그래프(n-complete graph)라 하며, $K_n$로 쓴다.
꼭짓점의 개수가 $n$개일 때, 변의 개수는 $n(n+1) \over 2$개이며, 모든 꼭짓점의 차수는 $n-1$라는 성질이 있다.
완전 그래프가 아닌 그래프, 즉, 최소 한 쌍의 서로 연결되지 않은 꼭짓점 쌍이 존재하는 그래프를 불완전 그래프(incomplete graph)라 한다.

$i$번째 꼭짓점을 $v_i$라고 할 때, 사이클(cycle) $C_n$은 꼭짓점의 개수가 $n$개이며,

인 그래프이다.

$i$번째 꼭짓점을 $v_i$라고 할 때, 휠(wheel) $W_n$은 꼭짓점의 개수가 $n+1$개이며,

인 그래프이다.
사이클 $C_n$에 새로운 꼭짓점 $v_{n+1}$을 추가하고, $C_n$에 있던 꼭짓점들과 $v_{n+1}$을 서로 연결함으로써 만들 수 있다.

꼭짓점 $v$에 대해서, $v$의 이웃(neighborhood) 또는 인접(adjacent)은 $v$와 이웃한(neighbor) 꼭짓점들의 집합이며, 기호로는 $N(v)$와 같이 쓴다. 예를 들어 단순 무향 그래프인 경우에는 다음과 같다.


꼭짓점의 집합 $A$에 대해서, $A$의 이웃은 모든 $v \in A$의 이웃의 합집합이다. 즉 다음과 같다.

무향 그래프의 꼭짓점 $v$의 차수(degree)는 기호로 $\operatorname{deg}(v)$ 또는 $d(v)$라 쓰며, 다음과 같이 정의된다.


즉, 모든 $v$와 연결된 모서리에 대해 다음의 과정을 통해 정의될 수 있다.

차수는 꼭짓점에 연결된 모서리의 수를 나타내는데, 고리에 대해 2를 더하는 것은 고리를 포함하는 그래프에서 일반적인 성질을 유지하기 위한 장치이다.

유향 그래프의 꼭짓점 $v$의 입력차수(in-degree) $\operatorname{deg}^{-}(v)$와 출력차수(out-degree) $\operatorname{deg}^{+}(v)$는 다음과 같이 정의된다.

즉, 입력차수와 출력차수는 $v$를 종점과 시점으로 갖는 모서리의 수이다. 단, 고리(loop)는 입, 출력차수 모두에 1씩 영향을 미친다.