Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

그래프이론과 한붓그리기

by

지민 옥

on 4 January 2013

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of 그래프이론과 한붓그리기

그래프이론과 한붓그리기 1학년 3반 옥지민 결과분석 끝 오일러의 오솔길 나. 한붓그리기를
할 수 있는 도형의 조건 찾기 라.한붓그리기가 가능한 도형 가.그래프 이론 1.주제설정이유 2. 탐구계획 그래프 이론 중에서 한붓그리기의 기본적인 내용을 초등학교에서 배운적이 있다. 이것은 현재 각 도시들을 연결하는 도로망이나 항공망, 또는 대도시의 지하철노선, 각 전화국들의 통신망 등 다양한 분야에서 응용되고 있기 때문에 활동을 통해 생활에서의 여러 가지 문제를 합리적으로 해결할 수 있는 능력을 기르기 위해 이번 프로젝트 주제로 설정했다.
가. 그래프 이론
나. 한붓그리기를 할 수 있는 도형의 조건 찾기
다. 오일러 순환길과 오일러 길에 대해 알아 보기
라. 한붓그리기가 가능한 도형 만들기
마. 해밀턴경로와 순환로 •오일러의 오솔길:한 그래프의 모든 모서리를 다 포함하는 오솔길
•오일러의 순환로:닫혀있는 오일러의 오솔길 가. 그래프 이론을 알게 되었다.
나. 한붓그리기를 할 수 있는 도형의 조건을 알게 되었다.
다. 오일러 순환길과 오일러 길에 대해 알게 되었다.
라. 한붓그리기가 가능한 도형 만들어 보았다.
마. 해밀턴경로와 순환로를 알게 되었다. 감사합니다 내가 전에 한 번 배워 보았던 주제였지만 이번
프로젝트를 통해 전에는 알지 못했던 새로운
사실을 알게되어 기쁘다.
다음에 이런 기회가 다시 한 번 더 온다면 내가 프로젝트를 하며 이해가지 않았던 부분이나 내가 조사하지
못했던 것을 한번 더 해보고 싶다. 그래프란? 꼭짓점이라 불리는 점들과 두 꼭짓점을 연결하는 변이라 불리는 선분으로 이루어진 그림. 역사적 배경 [오일러의 그래프] [쾨니히스베르크의 다리 일부] 그래프는 1736년 쾨니히스베르크다리 문제를 해결하기 위해 수학자이며 물리학자인 오일러 처음으로 사용한 것으로 기록되어 있다.
쾨니히스베르크의 다리 문제란 임의의 한 점에서 출발하여 일곱 개의 다리를 단 한번씩만 지나서 출발점으로 되돌아 올 수 있는가 하는 문제로 오일러는 모든 다리를 단 한 번만 거쳐서는 절대 출발한 지점으로 돌아올 수 없다고 결론지었다. 홀수점과 짝수점 • 홀수점 : 꼭짓점이 홀수개의 선분이 만나는 점
• 짝수점 : 꼭짓점이 짝수개의 선분이 만나는 점 그래프에서 용어
① 그래프
② 꼭짓점
③ 변
④ 꼭짓점의 차수
⑤ 인접행렬 지도를 이용한 그래프 ① ② ③ ④ ⑤ ⑥ 도형





⑥ 홀수점의갯수 짝수점의 갯수 2 3
5 4
2 2
0 12
4 3
4 7

한붓그리기가 가능한 도형의 특징
1.홀수점의 개수가 0개 또는 2개
2.홀수점이 0개인 경우는 출발점과 도착점 일치
3.홀수점이 2개인 경우 한 홀수 점은 출발점, 다른
홀수 점은 도착점 •한붓그리기를 할 수 있는 도형- ①, ③, ④ 다. 오일러 순환길과 오일러 길 오일러 •800여 편이나 되고 전집만도 45권의 분량을 남겼
다.
•해석학의 체계를 세웠고, 변분학 등 많은 수학상의 업적을 남겼다
•삼각함수의 기호인 sin,cos,tan 등을 비롯하여 자연 대수의 근에 쓰이는 기호e, 허수의 기호인 i도 전부 그가 처음으로 사용한 기호이다. •오일러 경로: 그래프의 경로가 모든 변을 단 한 번씩만 포함






•오일러 순환(오일러 회로):회로를 형성하는 오일러 경로





•오일러 그래프:오일러 회로를 갖는 그래프 오일러 경로 와 회로 오일러 회로와 경로의 특징
1. 그래프가 연결그래프이고 모든 꼭짓점의 차수가 짝수이면 그래프 안에는 오일러 회로가 존재한다.
2.연결그래프가 홀수 차수의 꼭짓점을 꼭 두 개 가지고 있으면 그래프에는 오일러 경로가 존재한다. 이 때 그래프 안의 모든 오일러 경로는 홀수 차수의 한 꼭짓점에서 시작하고 나머지 하나에서 끝이 난다. •오일러 순환길:도형에서 출발점과 도착점이 같으면서 모든 선을 꼭 한 번씩만 지나는 길 오일러 순환길 오일러 순환길의 특징
1.오일러 순환길은 홀수점이 없는 경우이므로 아무 점에서 출발하여도 다시 그 점에서 끝나도록 되어 있으므로 다양한 경우가 나올 수 있다.
2.오일러 순환길이 있는 도형의 홀수점의 개수가 0개이다. 오일러의 길 •오일러의 길:출발점과 도착점이 같지 않으면서 모든 선을 꼭 한 번씩만 지나는 길 오일러 길의 특징
1.오일러 길은 홀수점이 2개 있는 경우로 한 홀수점에서 출발하여 다른 홀수점에서 끝나도록 오일러 길을 찾아본다.
2.오일러 길이 있는 도형의 홀수점의 개수는 2개이다. •각 다리를 한 번씩만 건너서 모든 다리를 지날 수 있을까? •어느 지역에서 출발하더라도 모든 다리를 한 번씩만 건너서 처음의 위치로 돌아올 수 있도록 다리를 놓으려고 합니다. 새로운 다리를 최소한 몇 개를 놓아야 하고, 어느 지점에 놓아야 할까? 1736년 1875년 •1736년 오일러 쾨니스베르그의 일곱 개 다리를 정확하게 한 번씩만 지나서 전체 다리를 건넌다는 것이 불가능함을 증명하였다. 그로부터 139년 후인 여덟 번째 다리가 놓여져서 이 문제가 자동적으로 해결되었다. 한붓그리기 문제의 정리
1. 연결된 그래프가 오일러의 순환로를 가질 필요충분조건은 꼭지점의 차수가 모두 짝수일 때이다.
2.연결된 그래프가 닫혀있지 않은 오일러의 오솔길을 가질 필요충분조건은 홀수차수를 가지는 꼭지점이 꼭 2개 있을 때이다.
3.연결된 그래프의 한붓그리기가 가능할 필요충분조건은 꼭지점의 차수가 모두 짝수이거나 홀수차수를 가지는 꼭지점이 꼭 2개 있을 경우이다. 마.해밀턴 경로와 해밀턴 순환로 •해밀턴 경로:한 그래프의 모든 점을 다 포함하는 경로
•해밀턴 순환로(해밀턴 회로): 한 꼭지점에서 출발하여 모든 꼭지점을 한번씩만 지나고 다시 출발점으로 되돌아오는 경로 해밀턴 •수학자, 물리학자 및 천문학자로 광학, 동역학 및 대수학의 발전에 큰 공헌
•해밀턴 함수와 해밀턴-야코비 미분방정식과 해밀턴-캐일리 정리 등 많은 수학적 업적을 남김 해밀턴 회로와 경로 •해밀턴 경로:꼭짓점을 한 번씩 지나가되, 출발점으로 다시 돌아오지 않는 경로




•해밀턴 회로: 꼭짓점을 한 번씩 지나가되, 출발점으로 다시 돌아오는 경로 여러 가지 해밀턴 회로 1.정사면체 2.정육면체 3.정팔면체








4.정십이면체 5.정이십면체 느낀점
Full transcript