그래프 이론
정점·간선, 오일러 경로, 최단경로, SNS 네트워크 분석.
카카오 내비게이션은 어떻게 최단 경로를 찾을까? 인스타그램은 어떻게 '알 수도 있는 사람'을 추천할까? 그래프 이론은 '연결 관계'를 수학으로 다루는 학문이다. 물류, SNS, 반도체 설계의 핵심.
수학에서 그래프는 좌표평면의 그래프가 아니다. 점(정점, Vertex)과 점을 잇는 선(간선, Edge)의 집합이다. 지하철 노선도, 인물 관계도, 인터넷 구조 — 모두 그래프로 모델링할 수 있다.
쾨니히스베르크 다리 문제: '7개의 다리를 모두 한 번씩만 건너서 돌아올 수 있는가?' 오일러가 1736년에 '불가능'임을 증명하며 그래프 이론이 탄생했다. 모든 정점의 차수가 짝수여야 오일러 회로가 존재한다.
| 개념 | 의미 | 응용 |
|---|---|---|
| 정점(Vertex) | 점 (노드) | 사람, 도시, 웹페이지 |
| 간선(Edge) | 점을 잇는 선 | 친구 관계, 도로, 링크 |
| 차수(Degree) | 한 정점에 연결된 간선 수 | 친구 수, 연결 수 |
| 최단경로 | 두 점 간 가장 짧은 경로 | 네비게이션(다익스트라 알고리즘) |
SNS 네트워크 분석: 페이스북의 '6단계 분리 이론' — 지구상 누구와도 평균 6명만 거치면 연결된다. 그래프 이론으로 영향력 있는 노드(인플루언서), 커뮤니티 구조, 정보 전파 속도를 분석할 수 있다.
실생활 응용: ① 카카오 내비게이션 다익스트라 최단경로 ② 인스타그램 '알 수도 있는 친구' 추천 ③ 반도체 회로 배선 설계(VLSI) ④ 택배·물류 경로 최적화(TSP) ⑤ 지식 그래프 기반 검색.
정점 수 V = 5, 간선 수 E = 7인 단순 그래프에서 모든 정점의 차수의 합은?
오일러 회로가 존재하려면 모든 정점의 차수가 짝수여야 한다.
카카오 내비게이션이 음수 가중치 없는 도로망에서 최단 경로를 찾을 때 사용하는 대표적 알고리즘은?
n개 정점의 트리(Tree)는 항상 정확히 n-1개의 간선을 가진다.