이런 풀이는 어떻습니까

Question

답변 정말 감사합니다. 이렇게 성심성의껏 답변 달아주실줄 몰랐는데ㅠㅠ다만 제 의문점이 이건데. 이것만 어떻게 해결해주세요..연결관계를 알아보기 위해서 지금부터 점을 설정할거에요 
왼쪽 4개의점에 A,B,C,D를 놓구요오른쪽도 역시 동일하게 A,B,C,D를 놓습니다. 공통적으로 C는 A와 연결이 되게 배치했네요 
이제 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점은 연결관계가 왼쪽,오른쪽이 다르게되었어요이래서 두 그래프는 다르다. 이렇게 생각했는데 어디가 잘못된건가요?혹시라도 점을 배치해서 같은게 하나라도 나오면 같은 그래프라고 할 수 있는건가요?저는 일종의 반례하나가 나오면 그래프가 같지않다.다를수있기 때문에 같지않다고 생각했거든요

Rune · Accepted Answer

우선 이 문제를 풀 수 있는 좋은 방법 중 하나는 다음 명제를 외워버리면 됩니다.

"꼭짓점의 갯수가 2n개 (짝수)인 두 그래프의 차수가 모두 K개로 동일하다면(K≥2) 두 그래프는 항상 같은 그래프 이다."
이 명제는 수학적 귀납법으로 증명이 됩니다. 조금 길지만.



또 다른 현실적인 풀이는 다른 분들이 설명하신대로 꼭지점과 연결상태를 대응 시켜가면서 그래프를 비교하시면 됩니다.
이 두 그래프는 연결상태가 같은 녀석이므로 하나씩 대응 시키면 같은 녀석임이 증명이 됩니다.


세번째로 직접 변을 늘리고 줄여서 같은 그래프로 만드는 방법이 있습니다만.
이 방법은 대부분 강사들도 못하던데.. 뭐 가능합니다. 언제 시간나면 올리죠 ㅋ

Rune · Answer

그리고 꼭짓점 잡는 방법(로랑이님 방법) 으로 푸는 방법은 어떤 동일한 그래프라도 맞지 않는 예를 만들 수 있습니다.

꼭짓점으로 반례를 찾겠다고 하시면 두 그래프가 맞는 그래프인지를 알 수가 없지요.
문제에서 직접 꼭짓점을 주고, :다음이 같은 그래프 인지를 판정하라" 가 아니라면, 

본인이 직접 꼭짓점을 임의로 잡는 방법은(그것도 연결상태 무시하고 마음대로) 매우 위험한 방법 입니다.

로랑이 · Answer

방금은 제가 반례를 찾으려고 일부러 연결상태가 일치하지 않은 것을 찾았는데
모든 그래프가 항상 맞지 않은 예를 만들 수 있다면..

꼭짓점의 연결상태를 하나라도 동일하게 만들수있으면 같은 그래프고
어떻게 배치해도 연결상태가 다르면, 다른 그래프라고 생각해도 될까요?

Rune · Answer

음.. 그렇게는 생각해보지 않았는데;;

 [ 꼭짓점의 연결상태를 하나라도 동일하게 만들수있으면 같은 그래프고, 
  어떻게 배치해도 연결상태가 다르면, 다른 그래프 이다.]

이렇게 명제를 만들어도 큰 오류는 없어 보입니다.
단지, 문제에서 꼭짓점 이름을 부여하지 않은 경우에 사용하능 하겠네요.

김다람쥐 · Answer

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

이런 풀이는 어떻습니까

최근 게시글 · 더보기

댓글이 많은 글