도전하는자 · 335028 · 11/07/30 02:51

변 : 15
꼭짓점 : 10
각 차수 : 3

equl.
-> 위 세가지 모두 같음. 증명끝

좋아요 0 답글 달기 신고
경한가요 · 374515 · 11/07/30 02:55 · MS 2011

거기에 n인경로의 유무도 넣어야하지 않나요?
저 3개가 성립해도 안되는경우많던데

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

n인 경로의 유무는 어떤걸 말씀하시는거죠?

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

변 꼭지점 차수만 비교해서 같아도 다른 그래프라고

기출문제에 나와있어요

추가로 더 비교해야되지 않나요?

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

회원에 의해 삭제된 댓글입니다.

좋아요 0
도전하는자 · 335028 · 11/07/30 02:59

네가지 정도를 주어준 이후에 같은 그래프를 구하라고 한다면,
변의갯수, 꼭짓점의갯수, 각 꼭짓점의차수, 연결상태 모두를 확인해야 맞습니다.
단, 지금처럼 위와같이 '두 그래프가 같다' 라고 이미 알려준 경우,
연결상태는 맞다고 가정하고 위 3가지 (변의갯수,꼭짓점의갯수,차수)만 확인한 것입니다.
연결상태도 확인해 본다면 동일하게 나올 것입니다.

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

아. 선택지 중 하나였어요
ㄷ.두그래프가 같다 (O/X)
이거를 결정하라는 문제상황이에요.

연결상태는 어떻게 확인하지요?

좋아요 0 답글 달기 신고
도전하는자 · 335028 · 11/07/30 03:09

음, 그렇다면 결과는 달라지겠군요.
'행렬의그래프' 라는 이산수학에서 넘어온 분량은
가장 어려운 문제가 그래프 비교 유형이고
그 중에서도 가장 어려운 것이 연결상태 확인입니다
변,꼭짓점,차수,연결상태 중에 마지막을 찾아내는것이 관건인데,
제가 간단히 해 본 바로는 연결상태에서 일치하지가 않습니다.
결론적으로 다른 그래프입니다.

확인법
-> 왼쪽에 있는 그래프에 a부터 j까지 알파벳을 지정
-> 오른쪽 그래프에 a부터 쓰고 a와 연결된 나머지 세 성분을 표기
-> 동일한 방식으로 모두 표기
-> 두 그래프 비교시 성분 일치가 불가능하면 서로 다른 그래프이다.

애초에 늘리고 줄이는 방식으로의 원시적인 비교는 불가능에 가깝습니다
수능에서는 제가 알려드린 방법을 쓰시면 되겠습니다

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

아 알려주셔서 감사합니당ㅠㅠ흑흑 이시간에..
그런데 '두 그래프가 같다'가 정답이어서 너무 심난해요ㅠㅠ

님이 알려주신대로 해봐서 다르다는건 확인했는뎅.흐음

좋아요 0 답글 달기 신고
sos440 · 104180 · 11/07/30 03:32 · MS 2005

오른쪽 그래프에서 오른쪽 아래의 5개의 점 (시계로 치면 1시~7시 위치의 점 5개) 이 이루는 D모양의 부분을 바깥 원으로 팽창시키고 나머지 5개를 안으로 잘 집어넣어 갈무리하면 왼쪽이 나옵니다.

뭐랄까, 직접 가상의 물체를 만들어서 이리저리 갖고 변형해볼 수 있으면 좋긴 한데, 종이와 펜밖에 없는 상태에서 확인하기엔 조금 힘든 감이 없잖아 있네요. 관련된 이론이 있긴 할 것 같은데... -ㅅ-;;

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

허그 sos님께서.......

이거를 어떻게 수식?적으로라도 확인할수있는법은 없을까요ㅠㅠ
도저히 입체적으로 생각하기 쉽지 않네요..

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

두 그래프는 같은 그래프가 맞습니다.

변의 개수와 차수,꼭짓점의 수가 일치하고 연결 상태도 일치합니다.

위와 같이 입체적으로 머릿속으로 상상하여 비교가 힘든 그래프는

각 꼭지점에 이름을 붙여서 연결 상태를 확인해주면 되요

전부다 차수가 3인데 이는 한 꼭짓점당 3개의 변이 이어져 있음을 의미하고요

각 꼭짓점당 대응되는 꼭짓점을 찾아서 비교해보면 됩니다.

총 꼭짓점이 10개이므로

저는 각 꼭짓점의 이름을

A,B,C,D,E,1,2,3,4,5로 붙여주었구요

실제로 두 그래프를 그려 본 후 비교해보면

두 그래프 모두 각 꼭짓점당 대응되는 꼭짓점이 같습니다.

따라서 연결상태도 같고 두 그래프는 같은 그래프입니다.

실제로 시험장에서 저런 복잡한 그래프를 가지고 입체적으로 생각하기가 쉽지 않지요.

그러니 꼭짓점에 이름을 붙여서 연결상태를 확인하는게 낫다는 것입니다.

아주 간단하게 생긴 그래프는 그런
고무줄방법(변길이를 늘리거나 줄이거나 꼭짓점의 위치를 바꿔보다 같아질 수 있는지 확인하는 방법)을
사용해도 되지만

저런 복잡해보이는 그래프는

입체적으로 머릿 속으로 생각해서 같다고 생각이 들어도

직접 입체 모형을 만들어서 확인하지 않는 이상 대부분의 사람들은 확신이 서지 않기 때문에

연결상태를 확인함으로써 확실하게 같다고 증명이 가능한 것입니다.

좋아요 0 답글 달기 신고
도전하는자 · 335028 · 11/07/30 09:55

그래프를 올려 드리겠습니다.

좋아요 0 답글 달기 신고
리히텐슈 · 380720 · 11/07/31 01:46 · MS 2011

차수가 가장 높은 점을 하나하나 지워보세요. 그게 가장 확실합니다.

좋아요 0 답글 달기 신고
Forever... · 204492 · 11/08/06 01:24 · MS 2007

애초에 두 그래프가 isomorphic한지 확인하는 좋은 방법은 없습니다. 그러한 효율적인 알고리즘도 없구요. 결국 노가다에 맡길 수 밖에...

다만 두 그래프가 isomorphic하지 않음을 보일 땐, 노가다에 들어가기 전에 차수를 비교해본다든지, 이런 식을 통해서 먼저 금방 알아챌 수 있는건 금방 해결하는 것이 빠르겠죠.

좋아요 0 답글 달기 신고