중 2 유수정 최영인 오일러 회로와 헤밀턴 회로.

Presentation on theme: "중 2 유수정 최영인 오일러 회로와 헤밀턴 회로."— Presentation transcript:

1 중 2 유수정 최영인 오일러 회로와 헤밀턴 회로

2 목차 오일러 회로에 대해 알아본다. 헤밀턴 회로에 대해 알아본다. 주제문 해결 활용분야 및 example

3 해밀턴 납치사건 천재 수학자 오일러씨가 역시 수학자인 해밀턴씨를 납치했습니다!
천재 수학자 오일러씨가 역시 수학자인 해밀턴씨를 납치했습니다! 해밀턴을 되찾고 싶으면 팀가이스트를 없애라! 빨리 응답하지 않으면 해밀턴을 삼분안에 죽일 수 있는 독가스와 함께 무인도의 오일러회로에 던져버리겠다!

4 해밀턴 납치사건 이런! 팀가이스트는 월드컵에 쓰인 우수한 축구공인데 오일러의 법칙을 따르지 않는다고 합니다. 그런데, 오일러회로가 뭐죠? 그거라면 제가 알려드리죠. 아, 참고로 전 명탐정 겸 수학자 고난 입니다. 오일러회로는…

5 오일러 회로 * 정의 - 연결된 그래프에서 꼭지점은 여러 번 지날 수 있지만 모든 변은 한번만 지나는 회로를 오일러 회로라 한다. 이는 한 꼭지점에서 시작해서 다시 그 점으로 돌아온다. 조건 - 모든 점이 짝수 점이거나, 두 개의 점만 짝수 점이여야 한다

6 오일러 회로 이해하기 홀수점 – 어떤 한 꼭지점에 대하여 그 꼭지점에 이어진 선분이 홀수인 점
짝수점 - 어떤 한 꼭지점에 대하여 그 꼭지점에 이어진 선분이 짝수인 점

7 오일러 회로 example 쾨니히스부르크의 다리
오른쪽 그림은 왼쪽 다리그림을 간단히 한 것이다. 이와 같이 1번 도시에 도달하는 다리는 3개, 2번도시도 3개, 3번도시도 3개, 4번도시는 5개 이므로 오일러의 공식에 따르면 성립 불가이다.

8 해밀턴 납치사건 그렇군요. 그런데 왜 하필이면 해밀턴씨를 납치했을까요?
범인 오일러는 아마도 자기와 비슷한 회로를 갖고 있는 해밀턴씨가 얄미웠던 거겠죠. 그럼 해밀턴 회로도 한 번 보시죠.

9 해밀턴 회로 정의 -그래프에서 모든 꼭지점을 한번만 지나고 시작점으로 돌아오는 회로
조건 - 해밀턴 회로는 꼭지점의 수가 n개 이고 각 꼭지점의 차수가 n/2 이상인 연결그래프이면 해밀턴 회로를 가집니다.

10 해밀턴회로 example(1) 이 그래프는 해밀턴 그래프로써 해밀턴은 12면체모양의 수수께끼를 하나내고 출발지점에서 다시 그 출발지점으로 한 도시를 한번만 지나는 방법을 제시 한적이 있다. (성립)

11 해밀턴회로 example(2) 왼쪽 그래프를 풀기 쉽게 직선화 시키면 오른쪽의 그래프가 된다. 여기서 꼭지점의 개수는 여덟 개, 꼭지점의 차수는 8/2 인 4 이상이므로 위 그래프는 해밀턴 회로이다.

12 해밀턴 납치사건 잘 알겠습니다. 그런데 이제 어떻하죠? 역시 오일러씨가 해밀턴씨를 무인도에 내려놓으면 찾으러 가야하나요?
아니죠. 물론. 오일러가 해밀턴씨를 내려놓을 장소에 미리 가있는 겁니다. 삼분은 너무 짧으니까요. 그럼, 연습좀 해볼까요?

13 무슨 그래프? [정답] 해밀턴 그래프

14 문제풀기 ←가중치 그래프 오늘따라 할 일이 없던 해밀턴은 친구 a,b,c,d의 집에 놀러가기로 생각하고 드는 시간을 고려하여 친구들의 집을 간략한 그래프로 나타내 보았다. 여기서, 모든길을 다 지나가지 않아도 된다고 할 때, 가장 효율적이게 움직일 수 있는 방법을 생각해보자.

15 해설 a b c d의 집에 모두 들리는 것은 꼭 a-b-c-d가 아니여도 갈 수 있지만, 이 그래프는 가중치 그래프로써 가장 효율적인 길인 a-b-c-d 길이 가장 효율적임을 알 수 있다.

16 +!오일러의 오솔길   한붓그리기는 점과 선으로 이루어진 도형을 펜을 떼지 않고 선을 한번만 지나면서 그릴 수 있느냐는 문제이므로 결국 선형그래프에서 그 그래프의 모든 모서리를 다 포함하면서 모서리가 각각 다른 연결된 길을 찾을 수 있는가의 문제가 된다. 이와 같이, 한 그래프의 모든 모서리를 다 포함하는 오솔길을 오일러의 오솔길이라 한다. 또, 닫혀있는 오일러의 오솔길을 오일러의 순환로라 한다.

17 해밀턴 납치사건 다음은 무인도의 길들입니다. 하나하나 살펴보죠.이 중 오일러회로는 어떤 걸까요?
다음은 무인도의 길들입니다. 하나하나 살펴보죠.이 중 오일러회로는 어떤 걸까요? 옆에 주제문넣자. 아래 해밀턴 하나 넣고.주제문은 쉬는 시간에 넣자.

18 해밀턴 납치사건 여기는 주제문

19 범인을잡아라 오일러회로인가요 해밀턴회로인가요? 답:오일러

20 범인을잡아라 이 그래프는 점들이 모두

21 해밀턴 납치사건 해밀턴 넌 이제 끝이야. 아무도 응답을 안하더군. 앗! 아니? 어떻게 알고 왔지?
오일러, 당신은 너무 많은 단서를 흘렸어. 오일러씨, 같이 경찰서로 가주시죠.

22 해밀턴 납치사건 네. 이번 사건은 해밀턴씨의 무사귀환과 오일러씨의 구속으로 막을 내렸습니다. 고난씨와 함께해주신 여러분, 모두 감사합니다. 앗? 해밀턴씨! 허허.. 모두 정말 고맙네. 앞으로 오일러회로와 해밀턴 회로를 잊지말도록~!

23 끝