한붓그리기
- 등록일 / 수정일
- 페이지 / 형식
- 자료평가
- 구매가격
- 2016.04.16 / 2016.04.16
- 5페이지 / hwp (아래아한글2002)
- 평가한 분이 없습니다. (구매금액의 3%지급)
- 800원
최대 20페이지까지 미리보기 서비스를 제공합니다.
자료평가하면 구매금액의 3%지급!
1
2
3
4
5
추천 연관자료
- 본문내용
-
한붓 그리기
1. 한붓 그리기란?
한붓그리기란 어떤 도형을 연필을 한 번도 종이 위에서 떼지 않고 그리는 것을 말한다.
단, 연필이 한 번 지나간 부분(한 점만을 지나는 것은 허용됨)을 다시 지나서는 안 됩니다. 이 문제의 시작은 지금으로부터 약 250년 전에 오일러의 고향 퀘니히스베르크의 프레게르강에 걸쳐 있는 7개의 다리를 한 번도 중복하지 않고 모두 건너는 문제에서 시작되었다. 여기에서 힌트를 얻어 한붓그리기의 가능 불가능을 조사한 오일러는 홀수점 짝수점이라는 개념에 도달, 한붓그리기가 불가능한 도형의 전형을 보였다. 이것을 한붓그리기에 관한 오일러의 정리라 한다.
2.쾨니히스베르크의 다리건너기 문제
18세기 동(東)프로이센의 수도 쾨니히스베르크(현재의 칼리닌그라드)에 있던 프레게르강의 다리건너기를 제재로 한 초기의 위상기하학 문제를 말한다. 이것은 ‘한붓그리기’의 문제이나, 불가능하다는 것이 스위스의 수학자 L.오일러에 의해 밝혀졌다. 그런데 이 7개의 다리에 대해 “같은 다리를 두 번 건너는 일 없이 이들 다리를 모두 건너라”는 문제가 누군가에 의해 출제되었다. 이것은 ‘한붓그리기’의 문제이며, 위상기하학의 기초적인 문제로서 유명하다.
쾨니히스베르크에는 위와 같이 7개의 다리가 있다. 여기서 사람들은 7개의 다리를 한 번만 건너서 모든 다리를 건널 수 있을까? 당시 사람들은 여러 가지 방법으로 시도를 해 보았지만 아무도 그러한 경로를 발견하지 못했다. 그래서 이 문제를 부탁 받은 오일러는 그러한 경로가 존재하지 않는다는 사실에 대한 엄밀한 수학적 증명을 하였다고 한다. 오일러는 이 문제가 섬의 모양이나 다리의 길이 등과는 무관한 위치와 관계의 문제라는 것을 통찰했다. 그래서 우선 육지를 점으로, 다리와 길을 선으로 표시하였고, 다음 한붓그리기와 같은 원리로 해결하였던 것이다.
* 연결된 선분이 홀수 개인 점이 4개이므로 한붓그리기, 즉 한 번에 모두 건널 수 없다.
http://news.naver.com/main/read.nhn?mode=LSD&mid=sec&sid1=102&oid=032&aid=0000258262
3.오일러 경로
그래프 이론에서 오일러 경로(Euler path, Eulerian path)는 그래프의 모든 변을 단 한 번씩만 통과하는 경로를 뜻한다. 1736년 레온하르트 오일러가 쾨니히스베르크의 다리 문제를 푼 것에서 유래되었다. 흔히 한붓그리기 문제라고도 한다. 그 중에서 같은 꼭지점에서 시작해서 끝나는 오일러 경로를 오일러 회로(Euler circuit, Eulerian circuit)라고 한다. 오일러 회로를 지닌 무향그래프를 오일러 그래프라고 한다.
그래프가 오일러 회로를 가질 필요충분조건
자료평가
-
아직 평가한 내용이 없습니다.