그래프 이론(문화어: 그라프리론, graph理論, 영어: graph theory；圖論，도론)은 수학에서 객체 간에 짝을 이루는 관계를 모델링하기 위해 사용되는 수학 구조인 그래프에 대한 연구이다. 이 문맥에서 그래프는 꼭짓점(버텍스/vertex) or 교점(노드/node) or 점(포인트/point)으로 구성되며 이것들은 변(엣지/edge, 간선), 즉 선으로 연결된다. 그래프는 무향(무방향성)일 수 있는데 이는 각 변(선)으로 연결되는 두 개의 꼭짓점 간에 구별이 없다는 의미이며, 한편 변은 한 꼭짓점에서 다른 꼭짓점 간에 방향이 있을 수도 있다.
그래프(graph)는 순서쌍 G = (V, E)으로 볼 수 있으며, 여기에서 집합 V는 꼭짓점, E는 간선(변)을 의미한다.
쾨니히스베르크의 다리 문제는 프로이센의 쾨니히스베르크(지금의 러시아 칼리닌그라드)에 있는 7개의 다리에 관련된 문제이다. 쾨니히스베르크에는 프레겔 강이 흐르고 있고, 이 강에는 두 개의 큰 섬이 있다. 그리고 이 섬들과 도시의 나머지 부분을 연결하는 7개의 다리가 있다. 이때 7개의 다리들을 한 번만 건너면서 처음 시작한 위치로 돌아오는 길이 있는가 하는 것이 문제이다. 1735년에 레온하르트 오일러가 이것이 불가능하다는 것을 증명했다.
[Math in Biz] 7개 다리 한번씩만 건너는 그래프이론...자율주행에도 쓰여
Q1) "오일러 경로"와 "해밀턴 경로"란 무엇인가?
