그라프(Graph)는 수학과 컴퓨터 과학에서 객체 간의 관계를 나타내는 수학적 구조로, 개체를 정점(Vertex)으로, 개체 간의 연결 관계를 간선(Edge)으로 표현한다. 그라프는 여러 형태로 나뉘며, 주로 유향 그래프와 무향 그래프로 구분된다. 유향 그래프는 간선이 방향성을 가지며, 무향 그래프는 간선에 방향성이 없는 형태이다.

그라프는 또한 가중치가 있을 수도 있고, 없을 수도 있다. 가중치가 있는 그래프에서는 각 간선에 수치적 가중치가 부여되어 있으며, 이를 통해 두 정점 간의 거리나 비용을 나타낼 수 있다. 그라프는 연결 그래프와 비연결 그래프로 나뉘기도 한다. 연결 그래프는 모든 정점 쌍이 경로를 통해 서로 연결되어 있는 반면, 비연결 그래프는 일부 정점이 서로 연결되지 않은 상태이다.

그라프 이론은 알고리즘과 컴퓨터 네트워크, 데이터 구조, 최적화 문제 등 다양한 분야에서 응용된다. 예를 들어, 네트워크의 흐름을 분석하거나, 최단 경로를 찾는 데 사용되는 다익스트라 알고리즘과 같은 여러 유명한 알고리즘이 그라프 이론을 기반으로 한다. 또한, 소셜 네트워크 분석, 지도 제작, 물류 및 공급망 관리 등 다양한 실생활 문제 해결에도 그라프가 활용된다.

그라프의 형식적인 정의는 정점 집합과 간선 집합으로 구성된 쌍으로 표현할 수 있으며, 그래프 G는 G = (V, E)로 표기된다. 여기서 V는 정점의 집합, E는 간선의 집합을 의미한다. 정점의 수는 |V|로, 간선의 수는 |E|로 표기하며, 그래프의 복잡성을 이해하는 데 중요한 요소가 된다.