그래프 이론(영어: graph theory, 문화어: 그라프리론)은 그래프의 성질과 구조를 연구하는 수학의 한 분야이다. 그래프는 꼭짓점과 그 사이를 잇는 변으로 이루어진 이산적 구조이며, 그래프 이론은 이러한 연결 구조에서 나타나는 경로, 순환, 연결성, 색칠, 부합, 평면성, 마이너 등을 연구한다. 그래프 이론에서 중요한 것은 꼭짓점의 위치나 변의 길이가 아니라, 어떤 대상들이 어떤 방식으로 연결되어 있는가 하는 인접 관계이다. 따라서 같은 연결 구조를 가진 두 그림은 점과 선의 배치가 다르더라도 같은 그래프로 볼 수 있다. 이러한 점에서 그래프 이론의 그래프는 함수의 그래프처럼 양이나 함수를 시각적으로 나타낸 그림과는 구별된다. 그래프 이론은 조합론과 이산수학의 중심 분야 가운데 하나이다. 동시에 컴퓨터 과학, 운용과학, 네트워크 이론, 화학, 생물정보학, 사회 연결망 분석 등에서도 널리 쓰인다. 예를 들어 도로망, 통신망, 분자의 결합 구조, 웹 페이지의 링크 구조, 사람들 사이의 관계 등은 모두 그래프로 모델링할 수 있다. 그래프 이론의 문제는 대체로 연결 구조에 관한 질문으로 나타난다. 예를 들어 어떤 두 꼭짓점 사이에 경로가 존재하는지, 모든 변을 정확히 한 번씩 지나는 경로가 있는지, 그래프를 몇 가지 색으로 칠할 수 있는지, 특정한 부분 그래프가 반드시 존재하는지, 또는 주어진 조건을 만족하는 그래프가 최대 몇 개의 변을 가질 수 있는지 등을 묻는다. 이러한 질문들은 순수수학의 정리뿐 아니라 실제 네트워크를 분석하고 최적화하는 문제와도 연결된다. == 연구 대상 == 가장 기본적인 경우, 그래프는 꼭짓점 집합 V {\displaystyle V} 와 변 집합 E {\displaystyle E} 의 순서쌍 G = ( V , E ) {\displaystyle G=(V,E)} 으로 정의된다. 여기서 변은 서로 다른 두 꼭짓점으로 이루어진 2원소 부분집합이다. 즉, E ⊆ { { u , v } ∣ u , v ∈ V , u ≠ v } {\displaystyle E\subseteq \{\{u,v\}\mid u,v\in V,\ u\neq v\}} 이다. V {\displaystyle V} 의 원소를 꼭짓점 또는 정점이라 하고, E {\displaystyle E} 의 원소를 변 또는 간선이라고 한다. 이 정의의 그래프는 변에 방향이 없고, 한 꼭짓점에서 자기 자신으로 가는 고리와 같은 두 꼭짓점 사이의 중복 변을 허용하지 않는다. 따라서 더 정확히는 무향 단순 그래프이다. 많은 그래프 이론 문헌에서는 문맥상 혼동이 없을 때 무향 단순 그래프를 간단히 그래프라고 부른다. 그래프 이론에서는 무향 단순 그래프뿐 아니라 여러 관련 구조도 함께 다룬다. 변에 방향이 있는 그래프는 유향 그래프, 같은 두 꼭짓점 사이에 여러 변을 허용하는 그래프는 다중 그래프, 변이나 꼭짓점에 수치 값을 붙인 그래프는 가중 그래프라고 한다. 한 변이 두 꼭짓점이 아니라 임의의 개수의 꼭짓점을 연결하도록 일반화한 구조는 초그래프이다. 다만 이 문서는 그래프라는 대상 자체의 세부 정의와 종류를 모두 설명하기보다, 그래프 이론이라는 분야에서 어떤 문제를 연구하고 어떤 방법을 사용하는지를 중심으로 서술한다. 그래프의 기본 용어, 예, 종류, 연산은 그래프 (조합론) 문서에서 더 자세히 다룬다. 그래프 이론의 연구 대상은 개별 그래프의 성질에만 머무르지 않는다. 두 그래프가 같은 구조를 갖는지 판정하는 동형 문제, 그래프 안에 특정한 부분 구조가 들어 있는지를 묻는 부분 그래프 문제, 그래프를 단순한 조각으로 나누는 분해 문제, 조건을 만족하는 그래프의 최대·최소 크기를 구하는 문제, 그리고 그래프 위에서 효율적인 알고리즘을 찾는 문제도 모두 그래프 이론의 중요한 연구 대상이다. == 주요 문제와 기본 관점 == 그래프 이론은 그래프라는 대상을 정의하는 데서 그치지 않고, 그래프 안의 연결 구조가 어떤 성질을 가지는지, 어떤 부분 구조가 반드시 존재하는지, 그래프를 어떻게 비교하거나 분해할 수 있는지, 그리고 그래프 위의 문제를 얼마나 효율적으로 풀 수 있는지를 연구한다. 이 절에서는 그래프 자체의 세부 정의를 반복하기보다, 그래프 이론에서 자주 등장하는 문제의 유형과 관점을 요약한다. === 연결성과 경로 문제 === 가장 기본적인 관점은 그래프의 꼭짓점들이 서로 어떻게 연결되어 있는지를 조사하는 것이다. 두 꼭짓점 사이에 경로가 존재하는지, 그래프 전체가 연결되어 있는지, 연결 성분이 몇 개인지, 두 꼭짓점 사이의 거리가 얼마인지는 그래프 이론의 기본적인 질문이다. 이러한 관점은 여러 고전적 문제로 이어진다. 모든 변을 정확히 한 번씩 지나는 오일러 경로가 존재하는지, 모든 꼭짓점을 정확히 한 번씩 지나는 해밀턴 경로가 존재하는지, 두 꼭짓점 사이의 가장 짧은 경로가 무엇인지는 모두 경로와 연결성을 중심으로 한 문제이다. 특히 최단 경로 문제는 그래프 알고리즘의 대표적인 문제이며, 도로망·통신망·물류망의 분석에 직접 응용된다. 연결성은 단순히 “연결되어 있는가”를 넘어서 더 정밀하게 측정될 수 있다. 예를 들어 어떤 꼭짓점이나 변을 제거해도 그래프가 여전히 연결되어 있는지를 묻는 문제는 꼭짓점 연결도와 변 연결도의 개념으로 이어진다. 이러한 개념은 네트워크의 견고성이나 장애 허용성을 분석할 때 중요하다. === 부분 구조와 분류 문제 === 그래프 이론의 또 다른 핵심 질문은 주어진 그래프 안에 어떤 부분 구조가 들어 있는지를 밝히는 것이다. 예를 들어 그래프 안에 큰 클리크가 있는지, 큰 독립 집합이 있는지, 특정한 부분 그래프나 유도 부분 그래프가 존재하는지, 또는 특정한 그래프를 마이너로 포함하는지를 묻는다. 이러한 문제는 그래프의 구조를 분류하는 데에도 사용된다. 예를 들어 평면 그래프는 특정한 그래프를 마이너로 포함하지 않는다는 방식으로 특징지을 수 있고, 나무는 연결되어 있으면서 순환을 갖지 않는 그래프로 특징지어진다. 이처럼 그래프의 종류는 보통 어떤 부분 구조를 포함하거나 포함하지 않는다는 조건으로 설명된다. 두 그래프가 같은 구조를 가지는지를 판정하는 그래프 동형 문제도 중요한 연구 대