강의자료/알고리즘 수학

[컴퓨팅사고력] 프레겔 강의 7개의 다리로 배우는 그래프

파아란기쁨 2021. 11. 30. 08:38

18세기 초 프러시아의 옛 지점 쾨니히베르크의 중심을 흐르는 프레겔 강에 7개의 다리가
놓여있었습니다. 

당시 시민들 사이에서 같은 다리를 두 번 이상 지나지 않고 이들 7개의 다리
를 꼭 한 번씩 모두 건널 수 있을지 없을지에 대한 논의가 많았는데요 만일 한 번만
다리를 지나는 것이 가능하다면 어떤 방법으로 다리를 건너야만 할까? 라는 문제입니다. 

여러분이라면 이 문제를 어떻게 말할 수 있을까요? 

 

이 문제를 해결하기 위해 오일러라는 수학자는 이 문제를 쉽고 단순하게 표현하기 위해
다리와 섬들의 사이 관계를 평면상의 점과 선분으로 표현하였습니다. 

이렇게 여러 관계를 점과 선분으로 표현한 모양을 그래프라고 합니다. 

즉, 위 문제를 점과 선분으로 표기 하면 다음과 같은 그림이 된다.

이처럼 그래프는 문제를 해결하기 위한 하나의 중요한 구조로 다양한 분야에서 사용되는데요~

오늘은 그래프에 대해서 알아 보겠습니다.

 

그래프란?

그래프는 다음과 같이 표현을 합니다.

G=(V,E)

여기서 G는 그래프를 의미하고 V는 꼭짓점의 집합 즉 위의 그림에서 A,B,C,D 에 해당합니다.

V={v1,v2,v3,....vn} 과 같이 표현을 합니다.

E는 위의 그림에서 AB,AC,AD,BD,CD 와 같은 간선의 집합입니다.

E={e1,e2,e3,...en} 과 같이 표현을 합니다.

여기서 ei =(vi,vj) 와 같이 i번 정점에서 j번정점으로 연결되는 간선으로 표현할 수 있습니다. 

위와 같이 그래프는 차수(Degree)를 가지게 됩니다.

그래프의 차수란?

그래프에서 차수(Degree)는 꼭짓점 v에 근접하는 모서리 수를 의미합니다.

프레겔 강에 7개의 다리를 그래프로 표현했을때 A는 차수가 5,B는 차수가 3, C는 차수가 3, D는 차수가 3이 됩니다.

이와 같은 차수는 홀수점/짝수점을 가지게 됩니다.

한붓그리기가 가능한 그래프?

 한붓그리기는 모든 모서리를 한번씩만 지나서 그래프를 그릴 수 있는가 하는 문제입니다.

이때 한붓그리기가 가능한 그래프는 그래프의 차수에서 홀수점의 갯수가 0개 또는 2개인 경우에 한붓그리기가 가능합니다.

홀수점의 갯수가 0개인 경우 출발한 점에서 다시 자신으로 돌아 올 수 있는데 이것을 오일러 회로 또는 오일러 순환이라고 합니다.

홀수점이 두개인 경우는 홀수점에서 시작해서 다른 홀수점으로 끝나는 한붓그리기 경로가 존재 합니다.

 

생각해 보기)

위의 문제는 정보올림피아드 2009년에 출제된 문제입니다.

문제를 어떻게 해결해야 되는지 생각해 보세요.

 

문제풀이)

더보기

완전그래프는 모든 정점에 선이 연결되어 있어야 합니다.

정점의 개수가 6인 완전그래프

따라서 시작점과 끝점이 같기 위해서는 홀수점이 0개 이어야 합니다.

위츼 그래프에서 홀수점이 6개이며 선을 하나 제거하면 홀수점이 2개씩 사라질 수 있으므로 최소 3개를 제거해야 됩니다.

 

인천 서구 원당컴퓨터학원

 

원당컴퓨터학원에서는?

1. 4차 산업 시대의 흐름은 컴퓨터를 얼마나 이해하느냐에 따라 삶의 질이 틀려 질 수 있다는 것을 항상 염두에 두고 있습니다.

2. 알고리즘은 프로그래밍의 근원이 되는 문제해결 능력이며, 머신러닝은 IoT등에 의해 모여진 데이터를 활용하는 기법입니다.

3. 이에 따라 초,중,고 학생들이 알기 쉽게 이해하는 인공지능 부터 알고리즘까지 학생들의 실력에 맞춰 수업을 진행중에 있습니다.

4. 현재 초등학생이 고등학생이 되는 때에는 고교학점제 도입에 따라 자신이 전공하고자 하는 특기가 크게 부각 될것입니다.

5. IT 업체중 규모가 큰 곳에서는 코딩테스트(알고리즘테스트)로 블라인드 면접을 수행하는곳이 늘고 있습니다.

6. 미래 IT를 꿈꾸는 학생들의 산실이 되기 위해 항상 최선을 다하는 원당컴퓨터학원이 되겠습니다.

 

※ 정보영재 혹은 인공지능 관련 수업에 관해 궁금하신 분은 문의(032-565-5497) 주세요.

 

 

원당컴퓨터학원 커리큘럼

- OA : 학교 수행 평가에 꼭 필요한 컴퓨터 활용능력 향상

- IT 자격증 과정 : 취업대비,대학생인증제,승진을 위한 국가공인 자격증 취득과정

- 정보영재 : 정보올림피아드 및 알고리즘 대회/소프트웨어특기자전형/디미고 특별전형 대비/코딩테스트 대비를 위한 알고리즘 과정

- 프로젝트반 : 응용프로그래밍/웹프로그래밍/앱프로그래밍 등을 통해 직접 만들어 보면서 컴퓨터 프로그래밍 이해(소프트웨어 학생부종합전형/특성화고(디미고,선린고등) 특별전형대비)

- 인공지능 : 인공지능의 이해 및 실습을 통해 빅데이터 가공(4차 산업 시대의 축이 되는 인공지능 시대를 대비)

- 일반고,과고,영재고,특성화고,컴퓨터학과(SW) 대학생을 위한 내신대비 : python,java,c++,자료구조,알고리즘,이산수학 

사업자 정보 표시
원당컴퓨터학원 | 기희경 | 인천 서구 당하동 1028-2 장원프라자 502호 | 사업자 등록번호 : 301-96-83080 | TEL : 032-565-5497 | Mail : icon001@naver.com | 사이버몰의 이용약관 바로가기