방송대 이산수학 10강: 그래프 순회와 데이크스트라 최단 경로
같은 그래프를 보고도 어떤 문제는 면과 교차를 세고, 어떤 문제는 변을, 또 어떤 문제는 꼭짓점이나 가중치를 추적합니다. 이 글은 문제에서 무엇을 한 번씩 써야 하는지 먼저 판별하고, 평면 그래프의 수치 검산부터 오일러·해밀턴 순회, 데이크스트라의 거리 갱신과 경로 복원까지 직접 재현하도록 돕습니다.
그래프 문제는 먼저 목표 대상을 고르는 데서 시작한다
배달 차량이 모든 도로를 한 번씩 지나야 하는 문제와 모든 지점을 한 번씩 방문해야 하는 문제는 그림이 비슷해도 답을 찾는 기준이 다릅니다. 여기에 도로마다 이동 시간이 붙으면 “모두 방문”이 아니라 “출발지에서 목적지까지 총비용이 가장 작은 길”을 묻게 됩니다. 풀이 전에 다음 네 질문으로 문제의 종류를 분리해야 합니다.
| 문제에서 확인할 말 | 핵심 대상 | 사용할 개념 | 대표 판정·계산 |
|---|---|---|---|
| 교차 없이 다시 그릴 수 있는가 | 꼭짓점·변·면 | 평면 그래프 | 평면 임베딩과 오일러 공식 |
| 모든 변을 한 번씩 지나는가 | 변 | 오일러 트레일·투어 | 연결성과 꼭짓점 차수 |
| 모든 꼭짓점을 한 번씩 지나는가 | 꼭짓점 | 해밀턴 경로·사이클 | 실제 방문 순서 구성 |
| 가중치의 합이 가장 작은가 | 경로의 총비용 | 최단 경로 | 데이크스트라의 선택과 이완 |
판단 핵심: “한 번씩”이라는 말만 보고 알고리즘을 고르지 않습니다. 한 번씩 사용해야 하는 대상이 변이면 오일러, 꼭짓점이면 해밀턴이며, 비용 최소화가 붙으면 가중 그래프의 최단 경로 문제입니다.
교차가 보이면 그림이 아니라 그래프의 가능성을 판단한다
평면 그래프는 모든 변이 꼭짓점 이외의 곳에서 서로 교차하지 않도록 그릴 수 있는 그래프입니다. 현재 그림에 교차가 있다는 사실만으로 비평면 그래프가 되는 것은 아닙니다. 꼭짓점 사이의 연결 관계를 유지한 채 위치와 변의 모양을 바꾸어 교차를 없앨 수 있다면 평면 그래프입니다.
예를 들어 완전그래프 K4는 대각선이 교차하도록 그릴 수도 있지만, 한 꼭짓점을 삼각형 안쪽으로 옮기면 교차 없이 그릴 수 있습니다. 반면 강의에서 제시한 K5, K3,3, Petersen 그래프는 평면 그래프가 아닌 예입니다. K5에서 변 하나를 제거한 그래프는 교차 없이 다시 그릴 수 있으므로, 선이 복잡해 보이는 정도와 평면성은 구분해야 합니다.
오일러 공식으로 평면 그림을 검산한다
연결된 평면 그래프를 교차 없이 그렸을 때 꼭짓점 수를 v, 변의 수를 e, 면의 수를 f라 하면 다음 관계가 성립합니다.
v − e + f = 2
여기서 면은 변들로 둘러싸인 내부 공간만 뜻하지 않습니다. 그림 바깥의 무한히 넓은 영역도 한 면으로 셉니다. 학습용 예로 정사각형에 대각선 하나를 그으면 v=4, e=5이고 내부 면 2개와 바깥 면 1개를 합쳐 f=3입니다. 따라서 4−5+3=2가 되어 공식을 만족합니다. 바깥 면을 빼고 f=2라고 세는 것이 가장 흔한 오류입니다.
공식의 역할: v−e+f=2는 연결된 평면 그래프의 올바른 평면 그림에서 수를 검산하는 관계입니다. 등식 하나만 맞는다고 임의의 그래프가 자동으로 평면이라고 결론 내리는 판정법은 아닙니다.
4색 정리는 인접 관계를 색으로 번역한다
평면 지도에서는 경계를 공유하는 두 구역이 서로 다른 색을 갖도록 칠할 때 네 가지 색이면 충분합니다. 같은 내용을 평면 그래프의 꼭짓점 색칠로 표현하면 인접한 꼭짓점끼리 다른 색을 배정하는 데 네 색이면 충분하다는 뜻입니다. “네 색을 반드시 모두 써야 한다”가 아니라 “아무리 복잡해도 네 색을 넘길 필요가 없다”는 상한임을 기억해야 합니다.
모든 변을 한 번씩 쓰려면 차수의 짝을 확인한다
오일러 트레일은 그래프의 모든 변을 각각 한 번만 지나는 트레일이고, 오일러 투어는 시작점과 끝점이 같은 닫힌 오일러 트레일입니다. 이때 꼭짓점은 다시 방문할 수 있습니다. 제한되는 것은 꼭짓점이 아니라 변의 재사용입니다.
연결 그래프가 오일러 투어를 가질 필요충분조건은 모든 꼭짓점의 차수가 짝수인 것입니다. 투어가 어떤 꼭짓점에 들어오면 사용하지 않은 다른 변으로 나가야 하므로, 그 꼭짓점에서 사용되는 변은 ‘들어옴·나감’의 쌍을 이룹니다. 시작점도 마지막에 되돌아오므로 같은 짝 구조가 성립합니다.
짝수 차수 그래프에서 투어를 만드는 절차
- 임의의 꼭짓점 v에서 시작해 다시 v로 돌아오는 사이클 C를 하나 만든다.
- C가 모든 변을 포함하면 C가 오일러 투어이므로 끝낸다.
- 사용한 변을 제외한 그래프와 C가 공유하는 꼭짓점 w를 찾는다.
- w에서 시작해 w로 돌아오는 새 사이클 C′을 만든다.
- w 위치에 C′을 끼워 넣어 C를 확장하고, 모든 변이 포함될 때까지 반복한다.
강의 예제의 두 사각형처럼 한 꼭짓점 w를 공유하는 구조에서는 위 절차가 특히 잘 보입니다. 위쪽 사이클을 먼저 돌고 w에서 아래쪽 사이클을 끼워 넣으면 모든 변을 한 번씩 사용하면서 출발점으로 돌아옵니다.
오답 방지: 차수만 짝수인지 보고 끝내면 안 됩니다. 서로 떨어진 두 사이클처럼 모든 꼭짓점의 차수가 짝수여도 그래프가 연결되어 있지 않으면 하나의 오일러 투어로 전체 변을 순회할 수 없습니다.
모든 꼭짓점을 한 번씩 방문하면 해밀턴 문제다
해밀턴 경로는 그래프의 모든 꼭짓점을 한 번씩만 지나는 경로이고, 해밀턴 사이클은 출발점으로 되돌아오는 닫힌 해밀턴 경로입니다. 오일러 문제와 달리 모든 변을 사용할 필요는 없습니다. 방문하지 않은 변이 남아도 모든 꼭짓점을 정확히 한 번씩 방문했다면 조건을 만족합니다.
| 구분 | 반드시 한 번 사용하는 대상 | 남아도 되는 것 | 강의에서의 핵심 판정 |
|---|---|---|---|
| 오일러 트레일 | 모든 변 | 반복 방문한 꼭짓점 | 투어는 연결성과 모든 차수의 짝수 여부 |
| 해밀턴 경로 | 모든 꼭짓점 | 사용하지 않은 변 | 꼭짓점이 중복되지 않는 실제 경로 구성 |
차수가 모두 짝수라는 오일러 투어의 판정 규칙을 해밀턴 문제에 옮겨 쓰면 안 됩니다. 강의의 12면체 그래프와 Herschel 그래프 예에서도 핵심은 간선을 몇 개 남기더라도 모든 꼭짓점을 잇는 방문 순서를 실제로 찾는 것입니다. 그림에서 후보 경로를 표시한 뒤에는 꼭짓점을 하나씩 세어 누락과 중복을 동시에 검사해야 합니다.
짧은 점검 활동: 후보 순서를 적고, 각 연속한 두 꼭짓점 사이에 실제 변이 있는지 확인한 다음, 전체 꼭짓점 목록에 방문 표시를 하십시오. 마지막으로 사이클을 요구한다면 끝점과 시작점 사이에도 변이 있는지 한 번 더 확인합니다.
가중 그래프에서는 ‘짧다’의 의미를 합으로 계산한다
가중 그래프는 각 변에 실수값이 붙은 그래프이며, 그 값을 가중치라고 합니다. 가중치는 거리, 시간, 비용처럼 경로를 평가하는 양을 나타낼 수 있습니다. 변의 개수가 가장 적은 경로와 가중치 합이 가장 작은 경로는 다를 수 있으므로, 최단 경로에서는 지나간 변의 수가 아니라 가중치의 합을 비교합니다.
최단 경로 문제는 주어진 출발지와 도착지 사이에서 총가중치가 가장 작은 경로를 찾습니다. 반면 최소 신장 트리 문제는 그래프의 모든 꼭짓점을 사이클 없이 연결하는 신장 트리들 가운데 총가중치가 가장 작은 것을 찾습니다. 목적지 하나까지의 이동을 묻는지, 전체 꼭짓점의 연결망을 묻는지가 결정적인 차이입니다.
선택 규칙: “s에서 t까지”라면 최단 경로를, “모든 꼭짓점을 연결하되 전체 비용 최소”라면 최소 신장 트리를 떠올립니다. 신장 트리는 연결 그래프의 모든 꼭짓점을 포함하고 사이클이 없는 부분 그래프이며, 최소 신장 트리의 자세한 내용은 다음 11강에서 이어집니다.
데이크스트라는 가장 가까운 미확정 꼭짓점부터 확정한다
데이크스트라 알고리즘은 출발점 s에서 각 꼭짓점까지 알려진 최선의 거리 d[v]를 관리합니다. 처음에는 d[s]=0, 나머지는 ∞로 놓습니다. 아직 확정하지 않은 집합 Q에서 d가 가장 작은 꼭짓점 u를 꺼내고, u를 거쳐 이웃 v로 가는 비용이 더 작으면 값을 갱신합니다. 이 비교를 이완이라고 부릅니다.
각 꼭짓점 v에 대해 d[v] ← ∞
d[s] ← 0
Q ← 모든 꼭짓점의 집합
Q가 빌 때까지 반복:
Q에서 d[u]가 최소인 꼭짓점 u를 선택하고 제거
Q에 남아 있는 u의 각 이웃 v에 대해
d[v] ← min(d[v], d[u] + w(u,v))이 절차의 핵심은 “방금 본 변이 짧다”가 아니라 출발점에서 u까지의 누적거리 d[u]에 변의 가중치 w(u,v)를 더한다는 점입니다. 이 강의의 예처럼 음이 아닌 가중치를 다룰 때, 최소값으로 선택된 u의 거리는 이후 더 줄어들지 않는다고 보고 확정할 수 있습니다.
강의 예제의 거리표를 단계별로 다시 계산한다
출발점을 a로 두면 연결과 가중치는 a-b=2, a-e=4, b-c=1, b-d=5, b-e=4, b-f=2, c-d=3, f-e=3, d-e=5입니다. e와 f처럼 거리 4로 동률인 꼭짓점의 처리 순서는 달라질 수 있지만 최종 최단거리는 같습니다.
| 선택한 꼭짓점 | 계산한 이완 | 남은 주요 거리 |
|---|---|---|
| a, d[a]=0 | d[b]=min(∞,0+2)=2 d[e]=min(∞,0+4)=4 | b=2, e=4 |
| b, d[b]=2 | d[c]=2+1=3 d[d]=2+5=7 d[e]=min(4,2+4)=4 d[f]=2+2=4 | c=3, d=7, e=4, f=4 |
| c, d[c]=3 | d[d]=min(7,3+3)=6 | d=6, e=4, f=4 |
| e 또는 f, 거리 4 | e를 거치면 d는 min(6,4+5)=6 f와 e 사이도 기존 거리보다 작아지지 않음 | d=6 유지 |
| d, d[d]=6 | 목적지 d의 최소거리 확정 | 최종 거리: 6 |
직접 검산하면 후보 a-b-d의 비용은 2+5=7, a-e-d는 4+5=9, a-b-c-d는 2+1+3=6입니다. 따라서 계산된 최단거리 6과 실제 후보 경로의 합이 일치합니다.
실패 원인: d[d]=7을 처음 얻었을 때 바로 확정하면 안 됩니다. d[d]는 그 시점의 최선인 임시값입니다. 아직 더 작은 거리 3인 c를 먼저 선택한 뒤 c-d를 이완하면 6으로 줄어듭니다.
최단거리의 숫자에서 실제 경로를 복원한다
거리만 구하면 “비용이 6”이라는 사실은 알 수 있지만 어느 꼭짓점을 지났는지는 알 수 없습니다. 이완으로 d[v]가 실제로 작아질 때 prev[v]=u를 함께 기록하면, 목적지에서 출발점 방향으로 직전 꼭짓점을 거슬러 올라갈 수 있습니다.
- b의 거리를 2로 갱신할 때 prev[b]=a
- c의 거리를 3으로 갱신할 때 prev[c]=b
- d의 거리를 7에서 6으로 줄일 때 prev[d]=c
목적지 d에서 역추적하면 d←c←b←a이고, 이를 뒤집으면 a→b→c→d가 됩니다. 가중치 합은 2+1+3=6입니다. 거리표의 최종값, prev 연결, 경로의 직접 합산이라는 세 검사가 모두 같은 결과를 내야 풀이가 완결됩니다.
경로 복원 체크: prev를 목적지부터 따라가고, 출력할 때만 순서를 뒤집습니다. d값이 줄어들지 않았는데 prev를 바꾸면 거리와 경로가 서로 맞지 않을 수 있으므로 갱신 조건과 prev 기록을 함께 묶습니다.
처음 보는 그래프는 다섯 단계로 풀이한다
- 대상을 식별한다. 교차·면, 모든 변, 모든 꼭짓점, 총가중치 중 무엇을 묻는지 표시한다.
- 필요조건을 먼저 검사한다. 오일러 투어라면 연결성과 짝수 차수, 평면 그림이라면 바깥 면을 포함한 v·e·f를 확인한다.
- 상태를 기록한다. 해밀턴 문제는 방문 목록을, 데이크스트라는 d와 미확정 집합 Q를 적는다.
- 한 단계씩 갱신한다. 데이크스트라는 최소 d를 선택한 뒤 그 꼭짓점의 이웃만 이완하고, 값이 줄 때 prev도 바꾼다.
- 다른 방식으로 검산한다. 오일러 투어는 모든 변 사용 여부, 해밀턴 경로는 꼭짓점 누락·중복, 최단 경로는 가중치 직접 합산으로 확인한다.
이 순서를 사용하면 그림의 모양에 끌려가기보다 문제의 제약을 계산 가능한 기록으로 바꿀 수 있습니다. 특히 오일러와 해밀턴을 구분한 뒤, 가중치가 등장하면 경로의 변 개수 대신 누적합을 비교하는 습관이 중요합니다.
핵심 개념 정리
- 평면성은 현재 그림에 교차가 있는지가 아니라 연결 관계를 유지하며 교차 없이 다시 그릴 수 있는지에 달려 있습니다.
- 연결된 평면 그래프에서는 바깥 면을 포함해 v−e+f=2이며, 4색 정리는 네 색이 충분하다는 상한을 말합니다.
- 오일러 투어는 모든 변을 한 번씩 쓰고 출발점으로 돌아오며, 연결 그래프에서는 모든 꼭짓점의 차수가 짝수일 때 존재합니다.
- 해밀턴 경로는 모든 꼭짓점을 한 번씩 방문하므로, 오일러 문제의 차수 규칙을 그대로 적용하지 않습니다.
- 데이크스트라는 최소 임시거리 선택과 이완을 반복하며, prev를 함께 기록하면 목적지에서 출발지까지 실제 경로를 복원할 수 있습니다.
그래프 문제를 만나면 먼저 한 번씩 사용해야 할 대상과 최소화할 양을 찾으십시오. 평면 문제는 그림을 다시 그리고 면을 세어 검산하고, 오일러 문제는 변과 차수를, 해밀턴 문제는 꼭짓점 방문 순서를 추적합니다. 가중치가 있으면 d의 최소값을 선택하고 이웃을 이완한 뒤, prev 역추적과 가중치 합산으로 결과를 다시 확인하면 됩니다.
예상문제 10선
1. 평면 그래프에 대한 설명으로 옳은 것은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ②
- ① 오답: 평면성은 특정 그림의 교차가 아니라 교차 없는 그림의 존재 가능성으로 판단합니다.
- ② 정답: 꼭짓점의 인접 관계를 바꾸지 않고 변의 교차를 제거할 수 있다는 정의를 정확히 표현합니다.
- ③ 오답: 모든 차수가 짝수라는 조건은 연결 그래프의 오일러 투어 판정에 쓰입니다.
- ④ 오답: 4색 정리는 네 색이면 충분하다는 뜻이지 모든 평면 그래프가 네 색을 모두 써야 한다는 뜻이 아닙니다.
2. 오일러 투어와 해밀턴 사이클의 차이를 가장 정확하게 설명한 것은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ④
- ① 오답: 해밀턴 사이클에서는 사용하지 않은 변이 남을 수 있습니다.
- ② 오답: 오일러 투어에서는 같은 꼭짓점을 여러 번 방문할 수 있습니다.
- ③ 오답: 두 개념이 추적하는 대상을 서로 뒤바꾼 설명입니다.
- ④ 정답: 오일러는 변, 해밀턴은 꼭짓점을 제한하며 ‘투어·사이클’은 모두 시작점으로 되돌아오는 닫힌 순회입니다.
3. 연결된 평면 그래프의 꼭짓점이 6개, 변이 9개라면 면은 몇 개인가?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ①
- ① 정답: 6−9+f=2에서 f=5이며 바깥 면도 포함한 수입니다.
- ② 오답: 계산된 5개에서 바깥 면을 빼면 4가 되지만, 오일러 공식의 f에는 바깥 면도 들어갑니다.
- ③ 오답: e−v=3만 계산하고 우변 2를 반영하지 않은 값입니다.
- ④ 오답: v+e를 면의 수로 사용하는 공식은 성립하지 않습니다.
4. 연결 그래프의 꼭짓점 차수가 각각 2, 2, 4, 4일 때 옳은 결론은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ③
- ① 오답: 짝수 차수 조건은 해밀턴 사이클의 존재를 보장하는 규칙이 아닙니다.
- ② 오답: 문제에서 이미 연결 그래프라고 주었고, 홀수 차수의 부재는 연결성을 부정하지 않습니다.
- ③ 정답: 연결성과 모든 꼭짓점의 짝수 차수라는 오일러 그래프 정리의 두 조건을 모두 만족합니다.
- ④ 오답: 오일러 투어는 변의 사용 여부를 다루므로 가중치 정보가 필요하지 않습니다.
5. 어떤 학생이 “두 개의 떨어진 삼각형은 모든 꼭짓점의 차수가 2이므로 하나의 오일러 투어가 있다”고 말했다. 오류를 바로잡은 것은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ③
- ① 오답: 단순한 삼각형의 각 꼭짓점에는 두 변이 닿으므로 차수는 2입니다.
- ② 오답: 닫힌 오일러 투어에는 모든 꼭짓점의 차수가 짝수여야 합니다.
- ③ 정답: 한 성분에서 다른 성분으로 갈 변이 없으므로 모든 변을 포함하는 단일 닫힌 트레일을 만들 수 없습니다.
- ④ 오답: 색칠 가능성과 오일러 투어의 존재는 서로 다른 판정 문제입니다.
6. 짝수 차수 연결 그래프에서 만든 사이클 C가 모든 변을 포함하지 않을 때 다음 단계로 가장 적절한 것은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ①
- ① 정답: 공유 꼭짓점에서 닫힌 새 사이클을 만든 뒤 기존 사이클에 합치면 닫힘을 유지하면서 사용 변을 늘릴 수 있습니다.
- ② 오답: 꼭짓점까지 삭제하면 남은 변과 기존 사이클을 연결할 접점이 사라집니다.
- ③ 오답: 오일러 투어는 출발점으로 돌아와야 하므로 열린 경로로 끝내면 정의를 만족하지 않습니다.
- ④ 오답: 오일러 투어 구성에는 변의 가중치 순서가 필요하지 않습니다.
7. 강의의 가중 그래프에서 a-b=2, b-c=1, c-d=3, b-d=5일 때 a에서 d까지 두 후보 a-b-c-d와 a-b-d를 비교한 결과는?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ④
- ① 오답: 각 경로의 가중치를 합하면 2+1+3=6과 2+5=7로 서로 다릅니다.
- ② 오답: a-b의 가중치 2를 빠뜨렸으며 a-b-d의 총비용은 7입니다.
- ③ 오답: 최단 경로는 변의 개수에 벌점을 주는 것이 아니라 주어진 가중치의 합을 비교합니다.
- ④ 정답: 누적합을 정확히 계산하면 세 변을 지나는 경로가 오히려 비용 1만큼 작습니다.
8. 최단 경로 문제와 최소 신장 트리 문제를 구분하는 기준으로 옳은 것은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ②
- ① 오답: 가중 그래프의 최단 경로도 경로에 포함된 가중치 합을 최소화합니다.
- ② 정답: 두 문제는 모두 비용을 다룰 수 있지만, 특정 두 지점의 이동과 전체 연결망이라는 목표 범위가 다릅니다.
- ③ 오답: 모든 꼭짓점을 포함해야 하는 쪽은 신장 트리이며, 최단 경로에는 불필요한 꼭짓점이 빠질 수 있습니다.
- ④ 오답: 모든 변을 한 번씩 쓰는 조건은 오일러 순회의 조건이지 두 최적화 문제의 공통조건이 아닙니다.
9. 데이크스트라 계산 중 d[d]=7이고 미확정 꼭짓점 c의 거리가 3, 변 c-d의 가중치가 3이다. 올바른 갱신은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ①
- ① 정답: c까지의 누적거리 3에 c-d의 가중치 3을 더한 후보 6이 기존 7보다 작으므로 이완합니다.
- ② 오답: d가 최소 임시거리로 선택되기 전의 7은 확정값이 아니며 더 짧은 우회로로 줄어들 수 있습니다.
- ③ 오답: 이완 후보에는 현재 꼭짓점까지의 거리뿐 아니라 새로 지나는 변의 가중치도 더해야 합니다.
- ④ 오답: c를 선택한 단계에서는 c의 미확정 이웃 d를 갱신하는 것이 목적이며 비교 방향을 거꾸로 잡았습니다.
10. 데이크스트라 계산으로 d[d]=6을 얻은 뒤 실제 최단 경로까지 정확히 제시하려면 어떤 기록과 절차가 필요한가?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ③
- ① 오답: 차수의 짝은 오일러 투어를 판정할 때 쓰며 최단 경로의 선행 꼭짓점을 알려 주지 않습니다.
- ② 오답: 오일러 공식은 평면 그래프의 수치 관계이고 최단 경로 복원과 관련이 없습니다.
- ③ 정답: prev는 각 최단거리 갱신의 출발 꼭짓점을 보존하므로 목적지에서 역으로 연결한 뒤 뒤집으면 경로가 됩니다.
- ④ 오답: 마지막 변 하나의 가중치만으로는 출발점에서 그 변의 시작점까지 든 누적비용을 비교할 수 없습니다.
참고 자료와 작성 기준
이 글은 해당 차시 강의자료를 바탕으로 학습 목적에 맞게 재구성한 비공식 학습자료입니다. 강의의 반복 장면과 이전 차시 복습, 다음 차시 예고를 현재 차시 본문과 구분하고, 개념 관계·계산 과정·오류 교정과 문제 해설을 학습자의 이해 흐름에 맞게 구성해 검토했습니다.
- 작성·편집: 올에이클래스 학습연구팀
- 주요 근거: 한국방송통신대학교 컴퓨터과학과, 이산수학 제10강 「그래프(Ⅱ)」 강의자료(2021)
- 자료 범위: 평면 그래프와 4색 정리, 오일러 투어, 해밀턴 경로, 가중 그래프와 데이크스트라 최단 경로 알고리즘
- 편집 원칙: 올에이클래스 편집 정책
- 최종 내용 검토: 2026-09-06
댓글
댓글 쓰기