그림, 힌트, 자세한 풀이가 있는 무료 그래프 이론 연습 문제. 매번 새로운 값으로, 세 가지 난이도: 차수와 간선, 오일러 경로와 트리, 최단 경로와 신장 트리.
잘하셨어요. 다음 문제를 풀어 볼까요?다음 문제로 넘어갈까요? 모든 주제에서 매일 새 문제 5개.
먼저 알아 둘 것: 집합, 관계, 함수
그래프는 정점(점)과 간선(두 정점을 잇는 선)으로 이루어집니다. 단순 그래프에는 루프도 다중 간선도 없습니다.
정점의 차수는 그 정점에 닿는 간선의 수입니다. 모든 간선은 양 끝이 있으므로 각 끝점의 차수에 1씩 더합니다. 이로부터 악수 보조정리가 나옵니다.
두 가지 결과: 차수의 합은 항상 짝수이고, 차수가 홀수인 정점의 수도 짝수입니다.
인접 행렬은 i와 j가 이어져 있으면 (i, j)에 1을 둡니다. 무방향 그래프에서는 대칭이고, 행의 합이 차수이며, Mᴸ의 (i, j) 성분은 i에서 j까지 길이 L인 보행의 수입니다.
답: 6. 차수의 합은 12이고 모든 간선이 두 번 세어지므로 간선은 12/2 = 6개입니다. 5는 정점의 수입니다.
오일러 회로는 모든 간선을 정확히 한 번씩 지나 출발점으로 돌아옵니다. 오일러 경로는 모든 간선을 한 번씩 지나지만 다른 곳에서 끝날 수 있습니다. 연결 그래프에서는 다음이 성립합니다.
해밀턴 회로는 모든 정점을 정확히 한 번씩 방문합니다. 이를 판별하는 간단한 차수 검사는 없습니다. Kn에는 서로 다른 해밀턴 회로가 (n − 1)!/2개 있습니다. 시작점을 고정하고, 나머지 n − 1개 정점을 나열한 뒤, 두 방향이므로 2로 나눕니다.
답: 오일러 경로는 있지만 오일러 회로는 없다. 차수가 홀수인 정점이 정확히 두 개(두 개의 3)이므로 둘 사이에 오일러 경로는 있지만 회로는 없습니다.
트리는 사이클이 없는 연결 그래프입니다. 정점이 n개인 모든 트리는 정확히 n − 1개의 간선을 가집니다. 간선을 어느 것이든 추가하면 사이클이 생기고, 어느 것이든 제거하면 연결이 끊어집니다.
정점이 n개인 트리 c개로 이루어진 포리스트는 간선이 n − c개입니다. 간선이 m개인 연결 그래프는 m − n + 1개의 간선을 제거한 뒤에도 신장 트리를 유지합니다.
악수 보조정리로 잎의 수를 셉니다: Σ deg = 2(n − 1). 간단한 형태는 차수 d ≥ 3인 정점에 대한 L = 2 + Σ (d − 2)입니다. 차수 3인 정점이 두 개이고 나머지가 잎인 트리는 잎이 2 + 1 + 1 = 4개입니다.
다익스트라 알고리즘은 가중치가 음이 아닌 그래프에서 시작 정점으로부터의 최단 거리를 구합니다.
최소 신장 트리는 총 가중치가 가장 작게 모든 정점을 연결합니다. 크루스칼은 간선을 가벼운 것부터 무거운 것 순으로 정렬해 사이클을 만들지 않는 간선을 차례로 고릅니다. 프림은 시작 정점에서 트리 하나를 키우며 트리에서 뻗어 나가는 가장 가벼운 간선을 항상 추가합니다. 둘 다 간선 n − 1개에서 멈춥니다.
아래 그래프에서 A에서 E까지의 최단 거리를 구하시오.
d(A) = 0. 이웃은 d(B) = 4, d(C) = 1이 됩니다.
C를 거치면: d(B) = min(4, 1 + 2) = 3이고 d(E) = 1 + 8 = 9입니다.
B를 거치면: d(D) = 3 + 5 = 8입니다.
D를 거치면: d(E) = min(9, 8 + 1) = 9. 개선되지 않으며 같은 값입니다.
E가 확정되었습니다. 그 거리는 최종 값입니다.
최단 거리는 A → C → E를 따르는 d(E) = 9입니다. A → C → B → D → E 경로도 길이가 1 + 2 + 5 + 1 = 9로 같습니다.
답: 사이클을 만들게 되므로 건너뛴다. 크루스칼은 사이클을 절대 만들지 않습니다. 같은 성분에 속한 두 정점 사이의 간선은 건너뛰고 다음 간선으로 넘어갑니다.
단순 무방향 그래프의 인접 행렬이 주어져 있다. 그래프의 간선은 몇 개(|E|)인가?
구하는 값: |E|
차수: 정점의 차수는 그 정점에 닿는 간선의 수입니다. 모든 간선은 양 끝이 있으므로 차수의 합은 간선 수의 두 배입니다: Σ deg(v) = 2|E|(악수 보조정리). 따라서 차수가 홀수인 정점의 수는 짝수입니다. Kn은 간선이 n(n − 1)/2개이고, 정점이 n개인 k-정규그래프는 nk/2개이며, 정점이 n개인 트리는 간선이 n − 1개입니다.
연결 그래프에 오일러 회로가 있는가, 회로가 아닌 오일러 경로가 있는가, 둘 다 없는가? 답을 클릭하세요.
오일러, 해밀턴, 트리: 연결 그래프는 모든 정점의 차수가 짝수이면 오일러 회로(모든 간선을 한 번씩 지나 출발점으로 돌아옴)를 가지고, 차수가 홀수인 정점이 정확히 두 개이면 회로가 아닌 오일러 경로를 가집니다. 이 경로는 한 홀수 정점에서 다른 홀수 정점까지 이어집니다. 해밀턴 회로는 모든 정점을 한 번씩 방문하며, Kn에는 (n − 1)!/2개가 있습니다. 정점이 n개인 트리는 간선이 n − 1개이고, 간선이 m개인 연결 그래프는 m − n + 1개의 간선을 제거한 뒤에도 신장 트리를 유지합니다.
오일러 경로는 한 홀수 정점에서 시작해 다른 홀수 정점에서 끝납니다.
E에서 출발해 같은 정점으로 돌아오는 길이 3의 닫힌 보행은 몇 개인가? 보행에서는 정점과 간선이 반복될 수 있다. 그 수를 N(이)라 하자.
구하는 값: N
차수: 정점의 차수는 그 정점에 닿는 간선의 수입니다. 모든 간선은 양 끝이 있으므로 차수의 합은 간선 수의 두 배입니다: Σ deg(v) = 2|E|(악수 보조정리). 따라서 차수가 홀수인 정점의 수는 짝수입니다. Kn은 간선이 n(n − 1)/2개이고, 정점이 n개인 k-정규그래프는 nk/2개이며, 정점이 n개인 트리는 간선이 n − 1개입니다.
정점의 차수는 그 정점에 닿는 간선의 수입니다. 모든 간선은 양 끝이 있으므로 각 끝점의 차수에 1씩 더합니다. 이로부터 악수 보조정리가 나옵니다.
두 가지 결과: 차수의 합은 항상 짝수이고, 차수가 홀수인 정점의 수도 짝수입니다.
문제마다 값이 새로 바뀌므로 답이 아니라 푸는 방법을 익히게 됩니다. 막혔나요? 먼저 작은 힌트를 열고, 필요할 때만 전체 해설을 보세요.