관계의 크기, 가중치
지하철 노선도에서 두 역이 이어졌다는 사실만으로는 몇 분이 걸리는지 알 수 없습니다. 엣지에 숫자를 붙여 봅니다.
이번 회차, 내 속도로.
기초를 더 짚거나 궁금한 주제로 잠깐 넓혀 보세요. 최대 3단계를 거쳐 DAY 3로 돌아옵니다.
난이도·관심 주제 고르기
1/2개 선택 · 새 보충·심화 수업과 본과정 다시 읽기를 선택할 수 있어요.
이렇게 다녀와요 1단계 · 약 12분
- 출발 · DAY 3가중치·경로 비용
- 1. 관심 주제오일러 경로·홀수 차수추가 01 · 새 추가 수업
- 복귀 · DAY 3원래 회차 이어가기
- 오일러 경로·홀수 차수 · 1회차에서 노드·엣지·이웃을 배운 뒤, 그래프 이론의 첫 문제를 차수로 직접 풀어 봅니다.
선택과 경로 기록은 이 브라우저에 저장됩니다. 본과정의 회차 완료와는 별도입니다.
핵심 개념
가중치(weight)는 엣지에 붙인 숫자입니다. 역 사이 이동 시간, 도로 거리, 두 사람이 주고받은 메시지 수, 송금액처럼 관계의 크기를 담습니다. 가중치가 있는 그래프를 가중 그래프(weighted graph)라고 합니다. 가중치가 없는 그래프는 모든 엣지의 값이 1이라고 생각하면 같은 방식으로 다룰 수 있습니다.
경로(path)는 엣지를 따라 이어지는 노드의 순서이고, 경로 비용은 지나간 엣지 가중치의 합입니다. 반면 홉(hop) 수는 지나간 엣지의 개수만 셉니다. 한 번 더 갈아타는 지하철 경로가 오히려 일찍 도착하는 일이 흔하듯, 홉 수가 가장 적은 경로와 비용이 가장 작은 경로는 다를 수 있습니다. 비용이 가장 작은 경로를 체계적으로 찾는 방법은 13회차의 다익스트라 알고리즘에서 배웁니다.
가중치의 뜻을 먼저 정해야 합니다. 시간·거리·요금처럼 작을수록 좋은 값은 더해서 가장 작은 합을 찾습니다. 친밀도·연락 횟수처럼 클수록 가까운 관계를 뜻하는 값을 그대로 더해 ‘최단 경로’를 구하면, 오히려 가장 약한 관계들을 골라 잇는 셈이 됩니다. 이런 값은 역수를 취하는 등 ‘작을수록 가깝다’로 바꾼 뒤에 써야 하며, 같은 숫자라도 뜻을 섞으면 계산은 맞아도 해석이 틀어집니다.
작은 예제로 따라가기
역 S에서 T까지 두 경로가 있습니다. S→A→T는 4분+6분으로 2홉·10분입니다.
S→B→C→T는 2분+3분+2분으로 3홉·7분입니다. 한 번 더 지나가지만 3분 빠릅니다.
공사로 B→C 구간이 3분에서 7분이 되면 두 번째 경로는 2+7+2=11분이 되어, 다시 S→A→T(10분)가 최저 비용 경로가 됩니다.
직접 실험해 보기
경로 후보를 하나씩 골라 footer의 홉 수와 총 비용을 비교한 뒤, 슬라이더로 한 엣지의 가중치를 바꿔 최저 비용 경로가 바뀌는 지점을 찾으세요.
경로마다 홉 수와 소요 시간 비교하기
| 경로 | 홉 | 가중치 | 합 |
|---|---|---|---|
| ① S→A→C→T | 3홉 | 2 + 6 + 3 | 11분 |
| ② S→B→D→T | 3홉 | 5 + 3 + 5 | 13분 |
| ③ S→A→B→D→C→T | 5홉 | 2 + 1 + 3 + 1 + 3 | 10분 · 최저 |
이번에는 직접 풀어 보세요
정답을 보기 전에 계산과 이유를 적어 보세요. 해설과 비교하고 확인 표시를 남기면 완료할 수 있습니다.
힌트 보기
공원→도서관 시간을 x분이라 하면 두 번째 경로의 비용은 3+x+4입니다.
풀이와 비교하기
첫 경로는 2홉·10분, 두 번째 경로는 3홉·9분입니다. 3+x+4=10에서 x=3분일 때 두 경로가 같아지고, 그보다 오래 걸리면 첫 경로가 더 빠릅니다.
풀이와 확인 표시는 이 브라우저에 저장됩니다.
오늘 이해한 것과 다시 볼 것
계산이 달라진 이유, 헷갈린 개념, 다음에 확인할 질문을 남겨 보세요.
메모는 이 브라우저에 저장됩니다. 홈에서 전체 기록을 내려받을 수 있습니다.오늘의 이해 확인
2홉·12분 경로와 4홉·9분 경로가 있을 때 이동 시간이 더 짧은 경로는?
완료 조건: 확인 퀴즈 정답 · / 직접 풀기 0/1
더 깊이 읽기
예제와 실험 데이터는 이 과정을 위해 만든 것입니다. 원문은 선택 자료이며, 강의와 직접 풀기만으로도 다음 회차를 이어갈 수 있습니다.
Network Science, Chapter 2: Graph TheoryBarabási (2016)A note on two problems in connexion with graphsDijkstra (1959)이 자료는 개념 학습용입니다. 실제 데이터베이스·라이브러리·플랫폼의 동작과 설정은 제품과 버전마다 다를 수 있습니다.