Ch.6 수학이 모든 학문의 언어가 된다 (대학교)

그래프 이론

그래프가 점(꼭짓점)과 선(변)의 연결 구조임을 이해한다최단경로 문제의 핵심을 안다

서울에서 부산까지 가장 빠른 길은?

도시와 도로를 점과 선으로 그리면, 최단경로를 찾을 수 있다!

수십 개 도시, 수백 개 도로 중에서 어떻게 최적을 찾지?

그래프 이론 = 관계를 점과 선으로 그려서 최적 경로를 찾는 학문.

article

핵심 내용

도시 = 점, 도로 = 선 이것이 그래프다

꼭짓점(노드) = 도시·사람·웹페이지. 변(엣지) = 도로·친구관계·링크. 관계가 있으면 선으로 잇는다!

A역에서 D역으로 가야 하는데 경로가 3개나 있다! 어떤 길이 가장 빠를까?

G = (V, E) |V| = n, |E| = m

지하철 노선도, SNS 친구 관계, 인터넷 — 모두 점(V)과 선(E)으로 표현 가능

다익스트라 알고리즘: 가장 가까운 역부터 하나씩 탐색하며 최단 거리를 갱신한다!

A→B: 4분, A→C: 2분, B→D: 5분, C→D: 8분, B→C: 3분 다익스트라로 A→D 최단 경로를 찾아보자

A역에서 D역까지 가장 빠른 경로는?

모든 역까지의 거리를 '무한대'로 놓고, 가장 가까운 역부터 하나씩 확정해 나간다.

d(A)=0, d(B)=∞, d(C)=∞, d(D)=∞

출발점 A의 거리를 0으로 설정하고, 나머지는 무한대로 초기화한다.

A \xrightarrow4 B ⇒ d(B) = \min(∞, 0+4) = 4

A에서 B까지 가중치 4 — B의 거리를 4로 갱신한다.

A \xrightarrow10 C ⇒ d(C) = \min(∞, 0+10) = 10

A에서 C까지 직행 가중치 10 — 일단 C의 거리를 10으로 기록한다.

B \xrightarrow3 C ⇒ d(C) = \min(10, 4+3) = 7

미확정 중 가장 가까운 B를 방문 — B 경유 C가 7로 더 짧아 갱신한다.

C \xrightarrow2 D ⇒ d(D) = \min(∞, 7+2) = 9

C를 확정하고 D까지 가중치 2를 더하면 9 — D의 거리가 확정된다.

A \to B \to C \to D = 4+3+2 = 9분

최종 최단 경로는 A→B→C→D, 총 소요 시간 9분이다.

다익스트라 알고리즘: 가장 가까운 노드를 확정하며 전파 — 그리디하지만 최적해를 보장한다.

다익스트라 알고리즘으로 A→B→C→D = 9분 최단 경로 발견! 구글 지도, 카카오 내비가 정확히 이 방법을 쓴다

그래프 최단경로 = 다익스트라! 수백만 개 도로도 순식간에 최적 경로를 찾는다.

그래프 이론 = 점(노드)과 선(엣지)으로 관계를 표현하는 수학

관계와 연결이 있는 곳에 그래프 이론이 있다

그래프 이론에서 '꼭짓점(노드)'에 해당하는 것은?

그래프에서 간선(엣지)은 두 노드 사이의 연결을 나타낸다

다익스트라 알고리즘의 동작 원리를 파악하세요

다익스트라 알고리즘에서 방문하지 않은 노드 중 다음으로 선택하는 노드는?

그래프의 종류를 구분하세요

SNS 팔로우처럼 '내가 너를 팔로우해도 너는 나를 팔로우하지 않을 수 있는' 관계를 표현하기에 적합한 그래프 유형은?

다익스트라 알고리즘은 음의 가중치(음수 거리)가 있는 그래프에서도 올바른 최단 경로를 찾는다

노드 $n$개, 간선 $n-1$개로 이루어진 연결 그래프를 '트리(Tree)'라고 한다

그래프에서 특정 노드와 직접 연결된 간선의 수를 그 노드의 ___ 라고 한다

그래프 이론의 세계를 열었습니다!

compare_arrows

비교 정리

항목	분야	예시
내비게이션	최단 경로 탐색	다익스트라 알고리즘
SNS	친구 추천	공통 연결 노드 분석
구글 검색	페이지 순위	PageRank 알고리즘
전산망	데이터 경로	최적 라우팅

퀴즈와 인터랙션으로 더 깊이 학습하세요

play_circle인터랙티브 레슨 시작