방송대 방통대 이산수학 9강 - 그래프(I) - 요약 노트 시험족보 예상문제 - 올에이클래스

이산수학 9강 - 그래프(I)

그래프를 이루는 꼭지점과 변부터 차수, 워크·트레일·경로·사이클과 연결성까지 기본 용어를 익힌다. 이어 완전 그래프, 이분 그래프, 완전 이분 그래프, 정규 그래프를 구별하고 그래프를 발생행렬·인접행렬·인접리스트로 표현하는 방법을 학습한다.

제1장 그래프의 출발과 기본 용어

1. 쾨니히스베르크 다리 문제와 그래프

그래프 이론의 대표적인 출발점은 1736년 오일러가 다룬 쾨니히스베르크 다리 문제이다. 도시의 각 육지를 하나의 점으로, 육지를 잇는 다리를 선으로 바꾸면 실제 지형의 모양과 거리를 버리고 ‘어떤 대상들이 서로 연결되어 있는가’라는 구조만 남는다. 오일러는 이 추상화로 모든 다리를 정확히 한 번씩 건너는 문제가 가능한지를 분석하였다.

한 붓 그리기 판단: 연결된 그래프에서 차수가 홀수인 꼭지점의 수가 0개이면 출발점으로 돌아오는 한 붓 그리기가 가능하고, 2개이면 서로 다른 두 홀수 차수 꼭지점을 시작점과 끝점으로 삼아 가능하다. 강의록의 오일러 그래프는 이 관찰을 소개한다.

2. 그래프, 꼭지점, 변

그래프 G = (V, E)는 꼭지점들의 집합 V와 변들의 집합 E로 구성된다. 꼭지점(vertex)은 대상, 변(edge)은 두 대상 사이의 연결을 나타낸다. 변 e가 두 꼭지점 u와 v를 연결하면 e는 u와 v에 발생(incident)되었다고 하며, u와 v는 서로 인접(adjacent)한다고 한다.

용어	뜻
병렬 변	같은 두 꼭지점을 연결하는 변이 두 개 이상 있을 때의 변들이다.
루프	한 꼭지점에서 출발해 같은 꼭지점으로 돌아오는 변이다.
고립된 꼭지점	어떤 변과도 연결되지 않은 꼭지점으로 차수가 0이다.
동형 그래프	꼭지점과 변의 이름이나 그림의 배치만 다르고 연결 구조는 같은 그래프이다.

그래프의 동일성은 그림의 모양이 아니라 꼭지점과 변의 대응 관계로 판단한다. 선을 휘게 그리거나 꼭지점의 위치를 바꾸어도 인접 관계가 같으면 구조는 변하지 않는다. 이름을 적절히 일대일 대응시켰을 때 모든 연결 관계가 보존되는 그래프들은 서로 동형(isomorphic)이라고 한다.

3. 방향 그래프와 무향 그래프

방향 그래프(directed graph)는 변이 방향을 가지며, u에서 v로 향하는 변과 v에서 u로 향하는 변을 구별한다. 무향 그래프(undirected graph)는 변에 방향이 없어 u와 v의 연결을 양쪽에서 동일하게 본다.

단순 그래프(simple graph)는 루프와 병렬 변을 갖지 않는 무향 그래프이다. 이에 비해 루프나 병렬 변을 허용하는 그래프를 다중 그래프로 다룰 수 있다. 단순 그래프인지 판정할 때는 무향성, 루프 없음, 병렬 변 없음의 세 조건을 함께 확인해야 한다.

‘그래프가 동형이다’는 연결 구조가 같다는 뜻이고, ‘단순 그래프이다’는 그래프 안에 루프와 병렬 변이 없는 무향 그래프라는 뜻이다. 두 개념은 서로 다른 판정 기준이다.

제2장 부분 그래프와 차수

1. 부분 그래프와 신장 부분 그래프

G = (V, E)와 H = (V′, E′)가 그래프일 때 V′ ⊆ V이고 E′ ⊆ E이면 H를 G의 부분 그래프(subgraph)라고 한다. G에서 일부 꼭지점과 변을 골라 만든 그래프라고 이해할 수 있다. 다만 선택한 변의 양 끝 꼭지점은 H의 꼭지점 집합에도 포함되어야 한다.

부분 그래프 H가 원래 그래프의 꼭지점을 하나도 빠뜨리지 않아 V′ = V이고 E′ ⊆ E이면 H를 G의 신장 부분 그래프(spanning subgraph)라고 한다. 따라서 모든 신장 부분 그래프는 부분 그래프이지만, 꼭지점 일부가 빠진 일반 부분 그래프가 항상 신장 부분 그래프인 것은 아니다.

2. 꼭지점의 차수와 그래프의 총 차수

무향 그래프에서 꼭지점 v에 발생하는 변의 수를 v의 차수(degree)라 하고 deg(v)로 쓴다. 그래프 G의 총 차수는 모든 꼭지점 차수의 합으로, deg(G) = Σ_v∈V deg(v)이다. 루프는 한 꼭지점에 양 끝이 모두 닿으므로 그 꼭지점의 차수에 2만큼 기여한다.

악수 정리(Handshaking Lemma)
Σ_v∈V deg(v) = 2|E|

변 하나는 양 끝 꼭지점의 차수에 각각 한 번씩 기여하므로 모든 차수의 합은 변 수의 두 배이다. 따라서 총 차수는 항상 짝수이며, 그래프에서 홀수 차수를 가진 꼭지점의 개수도 반드시 짝수이다. 예를 들어 꼭지점 차수가 3, 5, 3, 3이면 총 차수는 14이고 변의 수는 7이다.

3. 방향 그래프의 진입차수와 진출차수

방향 그래프에서는 꼭지점 v로 들어오는 변의 수를 진입차수(in-degree), v에서 나가는 변의 수를 진출차수(out-degree)라고 한다. 방향이 반대인 변은 서로 다른 방식으로 계산한다. 강의록의 예에서는 v₁의 진입차수가 4, 진출차수가 1이고, v₃의 진입차수가 0, 진출차수가 3이다.

무향 그래프에서는 변의 방향이 없으므로 진입차수와 진출차수를 구분하지 않는다. 문제에 화살표가 있으면 각 화살표가 꼭지점으로 들어오는지 나가는지부터 확인해야 한다.

제3장 그래프 탐색의 기본 개념

1. 워크

그래프 G = (V, E)에서 v₀에서 v_k까지의 워크(walk)는 시작 꼭지점에서 종점까지 지나가는 꼭지점과 변을 순서대로 나열한 것이다. W = v₀e₁v₁e₂v₂…e_kv_k로 표시한다. v₀는 시작점, v_k는 종점, 그 사이의 꼭지점들은 내부점이며, 사용한 변의 수 k가 워크의 길이이다.

워크에서는 꼭지점과 변을 반복해서 지나도 된다. 시작점과 종점이 같아 v₀ = v_k이면 그 워크는 닫혀 있다고 한다.

2. 트레일, 경로, 사이클

워크에서 사용한 변들이 모두 서로 다르면 트레일(trail)이다. 트레일에서 시작점과 종점의 일치를 제외하고 꼭지점들이 모두 서로 다르면 경로(path)이다. 제한이 차례로 강해지므로 경로는 트레일이고, 트레일은 워크이다.

path ⊂ trail ⊂ walk
워크는 변과 꼭지점의 반복을 허용한다. 트레일은 변의 반복을 금지하고, 경로는 꼭지점의 반복까지 금지한다.

트레일이면서 시작점과 종점이 같으면 닫힌 트레일이다. 경로의 조건을 유지하면서 시작점과 종점만 같게 닫힌 구조를 사이클(cycle)이라고 한다. 길이가 k인 사이클은 k-사이클이라 부른다.

3. 연결과 연결성분

두 꼭지점 u와 v 사이에 경로가 존재하면 u와 v는 서로 연결되어 있다. 그래프의 꼭지점 집합은 서로 경로로 연결되는 꼭지점들을 묶은 서로 겹치지 않는 집합들로 나눌 수 있는데, 각각을 그래프의 연결성분(connected component)이라고 한다.

그래프의 임의의 두 꼭지점 u, v 사이에 항상 경로가 존재하면 그 그래프는 연결 그래프(connected graph)이다. 연결 그래프는 연결성분이 정확히 하나이다. 반대로 연결성분이 둘 이상이면 서로 다른 성분 사이를 잇는 경로가 없으므로 연결 그래프가 아니다.

제4장 그래프의 종류

1. 완전 그래프

서로 다른 임의의 두 꼭지점 사이에 항상 변이 존재하는 단순 그래프를 완전 그래프(complete graph)라고 한다. 꼭지점이 n개인 완전 그래프는 K_n으로 표시한다. 각 꼭지점은 자신을 제외한 나머지 n − 1개 꼭지점과 연결되므로 모든 꼭지점의 차수는 n − 1이다.

K_n의 변 수는 n(n − 1) / 2이고, K_n은 (n − 1)-정규 그래프이다.

변 수 공식은 총 차수가 n(n − 1)이고 악수 정리에 따라 이를 2로 나누어 얻을 수 있다. 예를 들어 K₅는 각 꼭지점의 차수가 4이고 변은 10개이다.

2. 이분 그래프

꼭지점 집합 V를 서로 겹치지 않는 두 집합 V₁, V₂로 분할하고, 모든 변이 V₁의 꼭지점과 V₂의 꼭지점을 연결하도록 할 수 있으면 G를 이분 그래프(bipartite graph)라고 한다. 즉 V₁ ∪ V₂ = V, V₁ ∩ V₂ = ∅이며 한 부분집합 내부의 꼭지점끼리는 변으로 연결되지 않는다.

3. 완전 이분 그래프

이분 그래프에서 V₁의 모든 꼭지점이 V₂의 모든 꼭지점과 연결되어 있으면 완전 이분 그래프이다. |V₁| = m, |V₂| = n인 완전 이분 그래프는 K_m,n으로 쓴다. 이때 각 V₁의 꼭지점 차수는 n, 각 V₂의 꼭지점 차수는 m이며 변의 수는 mn이다.

일반 이분 그래프는 존재하는 모든 변이 두 부분 사이를 연결하기만 하면 된다. 완전 이분 그래프는 여기서 더 나아가 서로 다른 두 부분에 속한 가능한 모든 꼭지점 쌍이 실제 변으로 연결되어야 한다.

4. 정규 그래프

모든 꼭지점이 같은 차수를 가지는 그래프를 정규 그래프(regular graph)라고 한다. 모든 v ∈ V에 대하여 deg(v) = k이면 G는 k-정규 그래프이다. 변이 전혀 없어 모든 꼭지점의 차수가 0이면 0-정규, 꼭지점마다 차수가 2이면 2-정규 그래프이다.

완전 그래프 K_n에서는 모든 꼭지점의 차수가 n − 1로 같으므로 언제나 (n − 1)-정규 그래프이다. 예를 들어 K₄는 3-정규 그래프이다.

제5장 그래프의 표현

같은 그래프를 그림이 아닌 자료 구조로 나타내면 계산과 알고리즘 처리에 활용할 수 있다. 강의에서는 발생행렬, 인접행렬, 인접리스트의 세 표현을 다룬다.

1. 발생행렬

그래프 G = (V, E)의 발생행렬(incidence matrix) M_I = (a_ij)는 꼭지점을 행, 변을 열로 놓아 꼭지점과 변의 발생 관계를 표시한다. 크기는 |V| × |E|이다. 꼭지점 v_i가 변 e_j에 의해 발생되면 a_ij = 1, 그렇지 않으면 0이다.

강의록의 예처럼 꼭지점이 3개, 변이 4개라면 발생행렬은 3 × 4 행렬이 된다. 단순 무향 그래프의 일반적인 변은 양 끝 꼭지점 두 곳에서 발생하므로 해당 열에 1이 두 개 나타난다.

2. 인접행렬

인접행렬(adjacency matrix) M_A = (a_ij)는 꼭지점을 행과 열에 모두 놓고 꼭지점 사이의 인접 관계를 나타낸다. 크기는 |V| × |V|이며 a_ij는 v_i에서 v_j로 연결되는 변의 개수이다.

방향 그래프에서는 행을 출발 꼭지점, 열을 도착 꼭지점으로 읽는다. 따라서 v_i → v_j가 있으면 i행 j열 값이 증가한다. 무향 그래프에서는 인접 관계가 양방향으로 같아 인접행렬이 주대각선을 기준으로 대칭이 된다.

3. 인접리스트

인접리스트(adjacency list)는 각 꼭지점에 인접한 꼭지점들을 차례로 연결 리스트로 표현한다. 꼭지점별 목록을 확인하면 어느 꼭지점과 바로 연결되는지 알 수 있다. 연결이 적은 그래프에서는 0이 많이 포함되는 인접행렬보다 실제 연결 정보만 저장하는 인접리스트가 구조를 간결하게 보여 준다.

표현	행과 열 또는 목록	핵심 정보
발생행렬	행: 꼭지점, 열: 변	어떤 변이 어떤 꼭지점에 발생하는가
인접행렬	행: 꼭지점, 열: 꼭지점	두 꼭지점 사이의 연결 개수
인접리스트	각 꼭지점별 이웃 목록	각 꼭지점에 인접한 꼭지점들

행렬의 크기를 먼저 확인하면 표현을 쉽게 구별할 수 있다. 발생행렬은 |V| × |E|, 인접행렬은 |V| × |V|이다.

핵심 개념 정리

• 그래프 G = (V, E)는 꼭지점 집합 V와 변 집합 E로 구성되며, 변이 두 꼭지점에 발생하면 그 꼭지점들은 서로 인접한다.
• 단순 그래프는 루프와 병렬 변이 없는 무향 그래프이다. 동형 그래프는 이름과 배치가 달라도 연결 구조가 같다.
• 신장 부분 그래프는 원래 그래프의 모든 꼭지점을 유지한 부분 그래프이다.
• 악수 정리에 따라 모든 꼭지점 차수의 합은 2|E|이고 홀수 차수 꼭지점의 개수는 짝수이다.
• 경로는 트레일이고 트레일은 워크이다. 워크의 길이는 사용한 변의 수이며, 닫힌 경로는 사이클이다.
• 임의의 두 꼭지점 사이에 경로가 존재하면 연결 그래프이고 연결성분은 하나이다.
• K_n의 변은 n(n − 1)/2개이며 K_n은 (n − 1)-정규 그래프이다.
• 이분 그래프의 변은 서로 다른 두 부분 사이에만 있고, K_m,n은 가능한 모든 두 부분 사이의 연결을 가진다.
• 발생행렬은 꼭지점과 변, 인접행렬과 인접리스트는 꼭지점 사이의 연결 관계를 표현한다.

그래프 문제는 먼저 방향성, 루프와 병렬 변의 존재를 확인한 뒤 꼭지점·변·차수를 정확히 센다. 탐색 용어는 반복 허용 범위에 따라 워크, 트레일, 경로를 구분하고, 그래프 종류는 모든 꼭지점 쌍의 연결 여부와 두 부분으로의 분할 가능성, 차수의 동일성을 기준으로 판정한다. 행렬 표현에서는 행과 열이 각각 꼭지점인지 변인지부터 확인하는 습관이 중요하다.

예상문제 20선

1. 그래프 G = (V, E)에서 E가 나타내는 것은?

① 연결성분의 집합 ② 꼭지점의 집합 ③ 변의 집합 ④ 차수의 집합

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
그래프 G = (V, E)에서 V는 꼭지점 집합이고 E는 꼭지점들을 연결하는 변의 집합이다.

2. 어떠한 변에도 연결되지 않은 꼭지점을 무엇이라 하는가?

① 고립된 꼭지점 ② 병렬 꼭지점 ③ 인접행렬 ④ 내부점

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
고립된 꼭지점은 어떤 변에도 발생하지 않으므로 차수가 0인 꼭지점이다.

3. 단순 그래프에 대한 설명으로 옳은 것은?

① 방향과 루프를 반드시 가진다. ② 병렬 변만 허용하는 방향 그래프이다. ③ 고립된 꼭지점을 가질 수 없다. ④ 루프와 병렬 변이 없는 무향 그래프이다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
단순 그래프는 무향 그래프이면서 루프와 병렬 변을 갖지 않는다.

4. 그래프 H = (V′, E′)가 G = (V, E)의 신장 부분 그래프가 되기 위한 조건은?

① V′ ⊂ V이고 E′ = E ② V′ = V이고 E′ ⊆ E ③ V′ ∩ V = ∅이고 E′ ⊆ E ④ V′ = E이고 E′ = V

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
신장 부분 그래프는 원래 그래프의 모든 꼭지점을 유지하므로 V′ = V이고, 변은 일부만 선택할 수 있어 E′ ⊆ E이다.

5. 무향 그래프의 꼭지점 차수가 3, 5, 4, 2일 때 변의 수는?

① 14 ② 6 ③ 7 ④ 5

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
총 차수는 3 + 5 + 4 + 2 = 14이다. 악수 정리에 따라 2|E| = 14이므로 |E| = 7이다.

6. 방향 그래프에서 꼭지점 v로 들어오는 변의 수를 무엇이라 하는가?

① 총 차수 ② 진출차수 ③ 경로 길이 ④ 진입차수

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
v로 들어오는 변은 진입차수, v에서 나가는 변은 진출차수로 센다.

7. 그래프에서 홀수 차수를 가진 꼭지점의 수에 관한 설명으로 옳은 것은?

① 항상 짝수이다. ② 항상 홀수이다. ③ 항상 변의 수와 같다. ④ 반드시 0이다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
악수 정리에 의해 모든 차수의 합이 짝수이므로 홀수 차수 꼭지점의 개수도 짝수여야 한다.

8. 워크의 길이는 무엇으로 정하는가?

① 서로 다른 꼭지점의 수 ② 지나간 변의 수 ③ 연결성분의 수 ④ 그래프의 총 차수

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
워크 W = v₀e₁…e_kv_k에서 사용한 변의 수 k가 워크의 길이이다.

9. 워크, 트레일, 경로의 관계를 올바르게 나타낸 것은?

① walk ⊂ path ⊂ trail ② trail ⊂ path ⊂ walk ③ walk ⊂ trail ⊂ path ④ path ⊂ trail ⊂ walk

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
경로는 꼭지점 반복이 없으므로 변 반복도 없는 트레일이며, 트레일은 워크의 한 종류이다.

10. 워크의 변들이 모두 서로 다를 때 이 워크를 무엇이라 하는가?

① 트레일 ② 연결성분 ③ 병렬 변 ④ 발생행렬

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
트레일은 같은 변을 반복하지 않는 워크이다. 꼭지점까지 반복하지 않으면 경로가 된다.

11. 연결 그래프의 연결성분 수는?

① 0개 ② 꼭지점 수와 같은 개수 ③ 1개 ④ 항상 2개

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
연결 그래프에서는 임의의 두 꼭지점 사이에 경로가 있으므로 모든 꼭지점이 하나의 연결성분에 속한다.

12. 완전 그래프 K₆의 변의 수는?

① 6 ② 15 ③ 30 ④ 12

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
K_n의 변 수는 n(n − 1)/2이므로 K₆은 6 × 5 / 2 = 15개의 변을 가진다.

13. 완전 그래프 K₅는 몇-정규 그래프인가?

① 4-정규 그래프 ② 5-정규 그래프 ③ 10-정규 그래프 ④ 3-정규 그래프

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
K_n의 각 꼭지점은 나머지 n − 1개 꼭지점과 인접한다. 따라서 K₅의 모든 꼭지점 차수는 4이다.

14. 이분 그래프에 대한 설명으로 옳지 않은 것은?

① 꼭지점 집합을 서로소인 두 부분으로 나눌 수 있다. ② 모든 변은 서로 다른 두 부분의 꼭지점을 연결한다. ③ 한 부분 내부의 두 꼭지점 사이에는 변이 없다. ④ 서로 다른 두 부분의 모든 꼭지점 쌍이 반드시 연결되어야 한다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
모든 가능한 두 부분 사이의 쌍이 연결되어야 하는 것은 완전 이분 그래프의 조건이다. 일반 이분 그래프에는 일부 변만 있어도 된다.

15. 완전 이분 그래프 K_2,4의 변의 수는?

① 6 ② 8 ③ 4 ④ 12

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
K_m,n은 한쪽 m개 꼭지점 각각이 다른 쪽 n개와 연결되므로 변의 수는 mn = 2 × 4 = 8이다.

16. 모든 꼭지점의 차수가 3으로 같은 그래프는?

① 0-정규 그래프 ② 완전 이분 그래프만 가능하다. ③ 3-정규 그래프 ④ 고립 그래프

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
모든 꼭지점 v에 대하여 deg(v) = k이면 k-정규 그래프이다. 여기서는 k = 3이다.

17. |V| = 5, |E| = 7인 그래프의 발생행렬 크기는?

① 5 × 7 ② 5 × 5 ③ 7 × 7 ④ 12 × 12

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
발생행렬은 꼭지점을 행, 변을 열로 두므로 크기는 |V| × |E| = 5 × 7이다.

18. 그래프의 인접행렬에 대한 설명으로 옳은 것은?

① 행은 변, 열은 꼭지점으로 구성된다. ② 크기는 |V| × |V|이다. ③ 각 원소는 연결성분의 개수만 표시한다. ④ 방향 그래프에서는 사용할 수 없다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
인접행렬은 꼭지점을 행과 열에 모두 배치하므로 |V| × |V| 크기이다. 방향 그래프에도 사용할 수 있다.

19. 방향 그래프의 인접행렬에서 a_ij가 나타내는 것은?

① v_i의 차수와 v_j의 차수의 합 ② e_i와 e_j의 발생 여부 ③ v_i가 속한 연결성분 번호 ④ v_i에서 v_j로 연결되는 변의 개수

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
방향 그래프의 인접행렬은 행을 출발점, 열을 도착점으로 읽으며 a_ij는 v_i에서 v_j로 가는 연결 개수이다.

20. 각 꼭지점에 인접한 꼭지점들을 연결 리스트로 나타내는 표현은?

① 발생행렬 ② 완전 그래프 ③ 인접리스트 ④ 차수 수열

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
인접리스트는 각 꼭지점별로 그 꼭지점과 인접한 이웃 꼭지점들을 연결 리스트에 나열한다.