그래프의 기초

쾨니히스베르크는 프레겔강에 의해 아래 그림처럼 섬 또는 육지가 A, B, C, D의 4개 지역으로 나누어지고, 이들 지역을 잇는 7개의 다리가 놓여 있 었어요.

수학자 L.오일러는 ‘섬 또는 육지의 한 지점으 로부터 출발하여 모든 다리를 정확히 한번만 지 나 원래 출발한 지점으로 돌아올 수 있는가’하 는 문제를 질문 받고 즉석에서 답을 했다고 전 해지고 있죠.

그러면 지금부터 오늘 학습할 내용에 대해 본격적으로 탐구해볼까요?

탐구문제 1 : 다음 세 가지 문제 상황을 해결하고, 공통점을 찾아봅시다.

① 지하철 노선도와 관광지가 표시된 지도를 가지고 있다면 어떤 도시든지 자유롭게 이동하면서 관광할 수 있습니다. 나눠주는 부산의 지하철 노선 도를 보고, 서면, 해운대, 자갈치시장, 부산대, 센텀시티, 김해공항을 지나 는 이동경로를 그림으로 그려보세요.

② 화학분자는 여러 개의 화학적 본드에 의해서 결합된 원자들로 구성되어 있습니다. 예를 들어, 물(H2O) 분자는 하나의 산소(O)와 두 개의 수소(H) 로 결합되어 있고 아래와 같이 나타낼 수 있습니다.

이와 같은 종류의 그림을 흔히 구조도라고 부릅니다. 에틸렌(ethylene, ethene; C2H4) 분자의 구조도를 아래의 빈칸에 그려봅시다. 그리고 이를 통해서 어떠한 정보를 얻을 수 있을지 생각해봅시다.

③ 다음은 어떤 집의 간단한 설계도입니다. 위의 설계도를 사람들이 지나다 니는 동선이 나타나게 그림을 그려보세요. 위와 같은 설계도와 비교해서 동선그림의 장점은 무엇일까요?

탐구문제 2 : 쾨니히스베르크의 지역과 다리를 점과 선으로 나타내어 봅시 다. 그리고 이와 같은 그림을 뭐라고 이름 붙이면 좋을지 생각해 봅시다.

약속하기 1

유한개의 점, 점과 점을 잇는 유한개의 선으로 구성된 도형을 그래프라고 부릅니다.

약속하기 2

두 꼭짓점을 잇는 변의 수가 두 개 이상인 변을 다중변, 한 꼭짓점과 그 자 신을 잇는 변을 고리라고 합니다. 한 꼭짓점에 연결된 변의 수를 그 꼭짓점의 차수라고 하는데, 고리는 두 번 헤아려집니다. 또한 차수가 홀수인 꼭짓점을 홀수점, 차수가 짝수인 꼭짓점을 짝수점이라고 부릅니다.

약속하기 3

다중변이나 고리가 없는 경우, 단순그래프라고 합니다.

연습문제 1 : 다음 그래프의 각 꼭짓점의 차수를 구해봅시다.

탐구문제 3 : 꼭짓점의 개수가 2, 3인 경우에 꼭짓점의 차수가 모두 다른 그래프를 각각 찾아봅시다. (단, 다중변은 2중변만 가능하며, 고리는 한 꼭 짓점에 한 개만 가능하다.)

보충 1 : 위의 각각 경우에서 공통적으로 발생하는 특징을 찾아보고, 타당한

연습문제 2 : 꼭짓점의 개수가 4개인 경우에 꼭짓점의 차수가 모두 다른 그래프를 찾아보고, 자신이 세운 가설이 맞는지 확인해봅시다.

그래프의 성질 1

꼭짓점의 차수가 모두 다른 그래프는 단순그래프가 아니다.

(= 단순그래프에서는 차수가 같은 꼭짓점이 항상 존재한다.)

탐구문제 4 : 어떤 모임에서 모임의 참석자들이 악수를 할 때, 각 참석자 가 악수한 횟수의 합과 모임에서 일어난 악수의 총 횟수와의 관계를 생각 해봅시다.(악수를 하지 않는 경우도 있을 수 있다.)

① 참석자가 2명 일 때 ② 참석자가 3명 일 때 ③ 참석자가 4명 일 때

보충 2 : ①~③의 경우에서 공통적으로 발생하는 특징을 찾아보고, 타당한 가설을 세워봅시다.

연습문제 3 : [탐구문제 4]에 대하여 참석자가 5명인 경우도 알아보고, 자 신이 세운 가설이 맞는지 확인해봅시다.

그래프의 성질 2

그래프에서 꼭짓점의 차수의 합은 변의 수의 2배이다.

탐구문제 5 : 어떤 모임에서 모임의 참석자들이 악수를 할 때, 홀수 번 악 수한 참석자의 총수는 각각 어떻게 되는지 생각해봅시다.(악수를 하지 않는 경우도 있을 수 있다.)

① 참석자가 2명 일 때 ② 참석자가 3명 일 때 ③ 참석자가 4명 일 때

보충 3 : ①~③의 경우에서 공통적으로 발생하는 특징을 찾아보고, 타당한 가설을 세워봅시다.

연습문제 4 : [탐구문제 5]에 대하여 참석자가 5명인 경우도 알아보고, 자 신이 세운 가설이 맞는지 확인해봅시다.

그래프의 성질 3

그래프에서 홀수점의 개수는 짝수 개다.

탐구문제 6 : 아래 네 개의 그래프 중에 같다고 생각되는 것을 찾아보고, 왜 같은지 이유를 설명해봅시다.

약속하기 4

꼭짓점 u, v가 변으로 이어졌을 때 ‘u, v는 서로 인접하다’라고 합니다.

꼭짓점 a, c는 서로 인접하다.

꼭짓점 b, c도 서로 인접하다.

하지만 꼭짓점 a, b는 서로 인접하지 않다.

꼭짓점의 개수가 같고 꼭짓점 사이의 인접성이 같은 두 그래프를 서로 동형이 라고 합니다. 즉, 두 그래프가 ‘그래프로써 서로 같다’는 말이기도 합니다.

연습문제 5 : 다음의 그래프에서 동형인 것은 어느 것일까요? 동형이 아 닌 것은 왜 그런지 이유를 설명해봅시다.

탐구문제 7 : 어떤 모임에서 모임의 참석자들이 악수를 할 때, 모든 참석 자들이 서로 악수를 했다면 모임에서 일어난 악수의 총 횟수는 어떻게 되 는지 생각해봅시다.

① 참석자가 2명 일 때 ② 참석자가 3명 일 때 ③ 참석자가 4명 일 때

보충 4 : ①~③의 경우에서 공통적으로 발생하는 특징을 찾아보고, 타당한 가설을 세워봅시다.

연습문제 6 : [탐구문제 7]에 대하여 참석자가 5명인 경우도 알아보고, 자 신이 세운 가설이 맞는지 확인해봅시다.

약속하기 5

모든 꼭짓점이 서로 인접한 단순그래프를 완전그래프라고 합니다.

꼭짓점 1개 꼭짓점 2개 꼭짓점 3개 꼭짓점 4개 꼭짓점 5개

탐구문제 8 : 3명의 사람 x1, x2, x3가 4가지의 물건 y1, y2, y3, y4를 선 택할 수 있는 방법이 다음 표와 같을 때, 이를 그래프로 나타내어 봅시다.

y1 y2 y3 y4

x1 × ○ ○ ×

x2 × × ○ ×

x3 ○ ○ × ○

약속하기 6

[탐구문제 8]의 그래프에서는 사람과 물건 사이의 선택은 가능하지만, 사람끼리 선택하거나 물건끼리 선택하는 것은 불가능 합니다. 이처럼 그래프 G의 꼭짓점이 두 그룹 X, Y로 나누어져, 같은 그룹의 꼭짓점끼리는 서로 인접하지 않을 때, G를 이분그래프라고 합니다.

특히, 임의의 x∈X와 임의의 y∈Y가 인접한 이분그래프를 완전이분그래프라 고 부릅니다.

연습문제 7 : 아래의 그래프를 이분그래프라고 할 수 있는지 생각해봅시다.

▣ 참고 자료 ▣

1. 네이버블로그. (2007). 쾨니히스베르크의 다리 건너기 문제. 2016. 10. 15.

https://bum94.blog.me/30025209727.html

2. 네이버블로그. (2010). 쾨니히스베르크의 현재. 2016. 10. 15.

https://blog.naver.com/scintillum/40103309567.html

3. 두산백과. (n.d.). 쾨니히스베르크의 다리 건너기 문제. 2016. 10. 15.

http://terms.naver.com/entry.nhn?docId=1150679&cid=40942&categoryId=32223.html

수학화 활동 사례 분석

수학자 오일러는 이 문제를 해결하였고, 이것이 그래프 이론의 시초이다. 현재

러나 아직 그래프에 대해서 정확하게 이해한 상황은 아니기 때문에, ‘탐구문제 2’를 제시하여 그래프의 정의와 이를 그리는 방법에 대해서 더 생각해보게 하였다.

탐구문제 2 쾨니히스베르크의 지역과 다리를 점과 선으로 나타내어 봅시다.

그리고 이와 같은 그림을 뭐라고 이름 붙이면 좋을지 생각해 봅시다.

처음에 학생들은 위의 그림을 어떻게 점과 선으로 나타내야 하는지 어려워했 다. 무엇을 점으로 나타내고, 무엇을 선으로 나타내야 하는지 알아내지 못했다.

한참을 기다린 후 수업자는 학생들에게 문제해결을 위한 힌트를 제공했다. 점은 지역인 A, B, C, D로 나타내고, 선은 다리인 a, b, c, d, e, f, g로 나타내어 보 라고 했다. 힌트를 받고나서도 학생들은 문제를 해결하는데 꽤 시간이 걸렸다.

[그림 Ⅳ-22]는 ‘탐구문제 2’에 대한 문제해결 아이디어이다. 첫 번째처럼 그 림에 바로 선을 연결하는 학생들이 가장 많았으며, 두 번째처럼 제대로 된 그래 프를 그리지 못하는 학생도 있었다. 그리고 세 번째처럼 모양은 복잡하지만 그 래프를 점과 선으로 잘 나타낸 학생들도 있었다. 마지막 네 번째는 가장 단순한 모양의 완성된 그래프이다.

탐구문제 3 꼭짓점의 개수가 2, 3인 경우에 꼭짓점의 차수가 모두 다른 그래 프를 각각 찾아봅시다. (단, 다중변은 2중변만 가능하며, 고리는 한 꼭짓점에 한 개만 가능하다.)

<표 Ⅳ-3> 학생들이 발견한 꼭짓점의 차수가 모두 다른 그래프(자료번호5-탐구문제3) 꼭짓점의

개수 발견한 그래프의 종류 발견한

그래프의 수

2개 3가지

3개 11가지

‘탐구문제 3’은 가능한 그래프를 모두 찾아내는 것이 목표이기 때문에 학생들 이 서로 의견을 나눌 수 있도록 모둠별로 해결하게 하였다. <표 Ⅳ-3>는 학생들 이 직접 발견한 꼭짓점의 차수가 모두 다른 그래프를 꼭짓점이 2개일 때, 3개일 때로 나누어 정리한 표이다.

학생들은 꼭짓점이 2개일 때는 세 가지 그래프를 모두 찾아냈다. 그러나 꼭짓 점이 3개일 때는 열한 가지 경우밖에 찾아내지 못했다. [그림 Ⅳ-23]은 꼭짓점이 3개일 때 학생들이 미처 발견하지 못한 나머지 다섯 가지 그래프이다. 학생들은 그래프를 찾기 위한 어떤 규칙을 세우지 않고 생각나는 대로 찾았기 때문에 몇 가지 그래프를 놓치게 되었다. 따라서 ‘탐구문제 3’에서 그래프를 찾기 위한 규칙 이나 기준에 대해서 연구해 보는 것도 가치가 있을 것이다.

[그림 Ⅳ-23] 학생들이 발견하지 못한 그래프(자료번호5-탐구문제3)

보충 1 위의 각각 경우에서 공통적으로 발생하는 특징을 찾아보고, 타 당한 가설을 세워봅시다.

‘보충 1’은 귀납적 추론 모형에 따라 미리 발견한 각각의 경우에 대해서 공통 적인 특징을 찾고 가설을 세우는 단계이다. 이 문제에서 학생들이 생각한 공통 점은 ‘반드시 고리가 있어야 한다.’였다. <표 Ⅳ-3>를 보면 학생들이 찾은 모든 그래프에 고리가 있다. 하지만 이것은 틀렸다. 왜냐하면 고리가 없어도 조건을 만족하는 그래프가 있기 때문이다. [그림 Ⅳ-23]의 두 번째 그래프가 그것이다.

따라서 수업자는 이 그래프를 제시하여 고리가 없어도 꼭짓점의 차수가 모두

따라서 수업자는 이 그래프를 제시하여 고리가 없어도 꼭짓점의 차수가 모두