이제 E,F를 놓습니다.
왼쪽그래프에서 E는B와 F는D와 연결되게 배치합니다.
오른쪽 그래프에서는 이제 같은 그래프가 아닐수있다는것을 보여주려고 (일종의 반례?)
D를 9시방향 점이 아니라 5시방향에 놓고 (그래도 B와는 연결되있으므로 무방)
F는 D아래 연결되게 놓습니다.

다시 왼쪽그래프에서 G,H,I,J를 설정합니다.
G는 B와 H는 D와 연결되게 설정하였고 I,J는 각각 CGF , CEH 와 연결이되었네요
이제 오른쪽 그래프에서 문제가 생깁니다.
최대한 연결관계가 비슷하게 점을 설정했는데 (G,H까지는 B,D와 연결되게 설정)
I,J를 마땅히 설정할 곳이 없고. 모든 꼭지점에 각각 3개의 변이 연결되있으므로 그것을 모두 고려해보면
G,H,I,J점은 연결관계가 왼쪽,오른쪽이 다르게되었어요

이래서 두 그래프는 다르다. 이렇게 생각했는데 어디가 잘못된건가요?
혹시라도 점을 배치해서 같은게 하나라도 나오면 같은 그래프라고 할 수 있는건가요?
저는 일종의 반례하나가 나오면 그래프가 같지않다.다를수있기 때문에 같지않다고 생각했거든요

팔로우 0

[ 대성학력개발연구소 ] ★대성모의고사 공모전★ (12/2~2/2)

[ 노크 ] 22개 대학합격인증자를 위한 안전하고 클린한 커뮤니티, 노크

[ 수학의 단권화 ]　9종 교과서 수능 전 범위를 10일 만에?

0 XDK (+0)

유익한 글을 읽었다면 작성자에게 XDK를 선물하세요.

로랑이 [211070]

쪽지 보내기

알림
스크랩
신고

Rune · 370907 · 11/07/30 08:23 · MS 2011

우선 이 문제를 풀 수 있는 좋은 방법 중 하나는 다음 명제를 외워버리면 됩니다.

"꼭짓점의 갯수가 2n개 (짝수)인 두 그래프의 차수가 모두 K개로 동일하다면(K≥2) 두 그래프는 항상 같은 그래프 이다."
이 명제는 수학적 귀납법으로 증명이 됩니다. 조금 길지만.

또 다른 현실적인 풀이는 다른 분들이 설명하신대로 꼭지점과 연결상태를 대응 시켜가면서 그래프를 비교하시면 됩니다.
이 두 그래프는 연결상태가 같은 녀석이므로 하나씩 대응 시키면 같은 녀석임이 증명이 됩니다.

세번째로 직접 변을 늘리고 줄여서 같은 그래프로 만드는 방법이 있습니다만.
이 방법은 대부분 강사들도 못하던데.. 뭐 가능합니다. 언제 시간나면 올리죠 ㅋ

좋아요 0 답글 달기 신고
Rune · 370907 · 11/07/30 08:26 · MS 2011

그리고 꼭짓점 잡는 방법(로랑이님 방법) 으로 푸는 방법은 어떤 동일한 그래프라도 맞지 않는 예를 만들 수 있습니다.

꼭짓점으로 반례를 찾겠다고 하시면 두 그래프가 맞는 그래프인지를 알 수가 없지요.
문제에서 직접 꼭짓점을 주고, :다음이 같은 그래프 인지를 판정하라" 가 아니라면,

본인이 직접 꼭짓점을 임의로 잡는 방법은(그것도 연결상태 무시하고 마음대로) 매우 위험한 방법 입니다.

좋아요 0 답글 달기 신고
로랑이 · 211070 · 11/07/30 09:17 · MS 2007

방금은 제가 반례를 찾으려고 일부러 연결상태가 일치하지 않은 것을 찾았는데
모든 그래프가 항상 맞지 않은 예를 만들 수 있다면..

꼭짓점의 연결상태를 하나라도 동일하게 만들수있으면 같은 그래프고
어떻게 배치해도 연결상태가 다르면, 다른 그래프라고 생각해도 될까요?

좋아요 0 답글 달기 신고
Rune · 370907 · 11/07/30 09:21 · MS 2011

음.. 그렇게는 생각해보지 않았는데;;

[ 꼭짓점의 연결상태를 하나라도 동일하게 만들수있으면 같은 그래프고,
어떻게 배치해도 연결상태가 다르면, 다른 그래프 이다.]

이렇게 명제를 만들어도 큰 오류는 없어 보입니다.
단지, 문제에서 꼭짓점 이름을 부여하지 않은 경우에 사용하능 하겠네요.

좋아요 0 답글 달기 신고
김다람쥐 · 337401 · 11/07/30 14:05 · MS 2010

꼭짓점의 이름이 주어진 경우라면 함부로 꼭짓점 이름을 부여해선 안되고 그 자체로
확인해야하지만 주어지지 않은 경우라면
임의로 꼭짓점의 이름을 부여하여 rune님이 말씀하신것 처럼 연결상태 확인이 가능합니다.

좋아요 0 답글 달기 신고