수리 질문이요ㅠㅠ
이게 같은 그래프라는데.
그래프가 같으려면 변의개수,꼭지점의차수 뿐만 아니라
변의 연결상태도 같아야되지않나요?
이 두개는 다른것같은데 왜 같은거죠ㅠ
0 XDK (+0)
유익한 글을 읽었다면 작성자에게 XDK를 선물하세요.
-
갑자기생각나서궁금해짐
-
붙으면 원서의 신인데
-
해주라
-
친구들은 아깝다고 대학급간 조금만더 올리는게 낫다하고 고민이 되는군요
-
작년에 16번,재작년에 19번까지 빠짐 앵간하면 붙을거같은데 몇차때 빠질까
-
난 이미 긁은 복권인데 넌 아직 안긁었잖아 난 꽝이야
-
아사람들 왜 질문과 관계 없는 댓글 다는 데 열중하나요 7
아사람들은 지금 수학노베를 뭘로 보는건가요
-
탈릅해야지
-
누가 더 유리할거같아요?
-
프사추천 0
주인없어짐
-
밥도잘먹지못해니가생각날까봐니생각에체할까봐니가떠난후로오늘도눈물로하루를먹고살아버스도타지못...
-
모솔특 9
사랑 부르짖는 발라드 공감 1도 안됨
-
그렇지않아도 200 따리 지옥불 인생 이제 도감청 걱정까지 해야한다며 의원면직 +...
-
어피니티 정체 알아냄
-
이별의 아픔을 0
느낄 날이 올까
-
수학커리추천좀 0
현우진만 듣고 엔제 박치기 했었는데 백분위 기준 6모 97(84점) 9모...
-
26년 입시 0
수시 성적이 입결찾아보니 한곳은 평균과 최저 사이이고 한곳은 평균 성적인데 26년...
-
-
복전을 해야되나 2
하고싶다고 되는게 아니긴한데
-
엄청 치열하겠죠....?ㅜㅜ
-
심심하네 11
(1,0)이 아닌 원과 x축의 교점을 P라 하자,그럼 할선정리에 의해...
-
프사바꾸고싶은데 2
움짤올리면다용량이너무크대
-
드릴 2
드릴도 N제인가요? 아님 드릴드만 N제인가요?
-
프리미엄 장사 오지네
-
왜 아직도 연락이 안 올까요 3합7인데 영어 2를 1로 쳐준다고 해서 기준도...
-
문과도수학30퍼는보는기울어진운동장
-
계속 앉아있으니 장이 활동을 안해서 소화가 안되고 아직도 더부룩해..ㅠㅠ
-
드릴, 드릴드 대신 4규,지인선,이해원같은 n제 풀어도 될까요?
-
오후 6시까지 오르비 댓글 글 쓰면 1.4만덕 다 드릴게요
-
전체 다오는 새터는 좀 헤비한데 흠..
-
수학을 4로 잘못 써서 재업 언확경제사문일때여 국어 경제 사문 다 높1일 때 수학은 3등급 중간
-
컨디션 망 2
-
24244는 7
이화여대감
-
반 모의고사 수학은 항상 1~2등이었어서 애들이 질문하러 왔었는데...
-
무물보 0
심심해요 학원에서 할 게 없어요
-
교주빈 1
사형좀
-
제발
-
실패시 만덕 나눔
-
현역때 6모 수학 백분위 96이였는데 전교 20등대였음 응시자 270명
-
키 2등급 7
굿
-
명지대 미디어 vs 가톨릭대 인공지능 미디어 쪽 전공을 좀 더 선호하지만, 미래를...
-
어나클사서 종이책으로 제본하려는데 어디서 많이들하시나요???
-
쉽지않음
-
고1수학 쎈 5
하루에 10문제정도 매일 꾸준히 푸는거 어떻게 생각함?
-
평백 그래도 87정도 되는데 의외로 친구들한테 공부좀 치는데? 이소리 들음 ㅋㅋㅋㅋ...
-
수분감 스텝3 하는데 한 문제에 40분~ 1시간 걸리는데 꾸역꾸역 푸는게...
-
키 메타를 열어보자 30
키 적고 가라잇
-
-
반대로 사수 중경외시라인은 어떰? 나이 디메리트 말하는거
-
발저려 0
으악
변 : 15
꼭짓점 : 10
각 차수 : 3
equl.
-> 위 세가지 모두 같음. 증명끝
거기에 n인경로의 유무도 넣어야하지 않나요?
저 3개가 성립해도 안되는경우많던데
n인 경로의 유무는 어떤걸 말씀하시는거죠?
변 꼭지점 차수만 비교해서 같아도 다른 그래프라고
기출문제에 나와있어요
추가로 더 비교해야되지 않나요?
네가지 정도를 주어준 이후에 같은 그래프를 구하라고 한다면,
변의갯수, 꼭짓점의갯수, 각 꼭짓점의차수, 연결상태 모두를 확인해야 맞습니다.
단, 지금처럼 위와같이 '두 그래프가 같다' 라고 이미 알려준 경우,
연결상태는 맞다고 가정하고 위 3가지 (변의갯수,꼭짓점의갯수,차수)만 확인한 것입니다.
연결상태도 확인해 본다면 동일하게 나올 것입니다.
아. 선택지 중 하나였어요
ㄷ.두그래프가 같다 (O/X)
이거를 결정하라는 문제상황이에요.
연결상태는 어떻게 확인하지요?
음, 그렇다면 결과는 달라지겠군요.
'행렬의그래프' 라는 이산수학에서 넘어온 분량은
가장 어려운 문제가 그래프 비교 유형이고
그 중에서도 가장 어려운 것이 연결상태 확인입니다
변,꼭짓점,차수,연결상태 중에 마지막을 찾아내는것이 관건인데,
제가 간단히 해 본 바로는 연결상태에서 일치하지가 않습니다.
결론적으로 다른 그래프입니다.
확인법
-> 왼쪽에 있는 그래프에 a부터 j까지 알파벳을 지정
-> 오른쪽 그래프에 a부터 쓰고 a와 연결된 나머지 세 성분을 표기
-> 동일한 방식으로 모두 표기
-> 두 그래프 비교시 성분 일치가 불가능하면 서로 다른 그래프이다.
애초에 늘리고 줄이는 방식으로의 원시적인 비교는 불가능에 가깝습니다
수능에서는 제가 알려드린 방법을 쓰시면 되겠습니다
아 알려주셔서 감사합니당ㅠㅠ흑흑 이시간에..
그런데 '두 그래프가 같다'가 정답이어서 너무 심난해요ㅠㅠ
님이 알려주신대로 해봐서 다르다는건 확인했는뎅.흐음
오른쪽 그래프에서 오른쪽 아래의 5개의 점 (시계로 치면 1시~7시 위치의 점 5개) 이 이루는 D모양의 부분을 바깥 원으로 팽창시키고 나머지 5개를 안으로 잘 집어넣어 갈무리하면 왼쪽이 나옵니다.
뭐랄까, 직접 가상의 물체를 만들어서 이리저리 갖고 변형해볼 수 있으면 좋긴 한데, 종이와 펜밖에 없는 상태에서 확인하기엔 조금 힘든 감이 없잖아 있네요. 관련된 이론이 있긴 할 것 같은데... -ㅅ-;;
허그 sos님께서.......
이거를 어떻게 수식?적으로라도 확인할수있는법은 없을까요ㅠㅠ
도저히 입체적으로 생각하기 쉽지 않네요..
두 그래프는 같은 그래프가 맞습니다.
변의 개수와 차수,꼭짓점의 수가 일치하고 연결 상태도 일치합니다.
위와 같이 입체적으로 머릿속으로 상상하여 비교가 힘든 그래프는
각 꼭지점에 이름을 붙여서 연결 상태를 확인해주면 되요
전부다 차수가 3인데 이는 한 꼭짓점당 3개의 변이 이어져 있음을 의미하고요
각 꼭짓점당 대응되는 꼭짓점을 찾아서 비교해보면 됩니다.
총 꼭짓점이 10개이므로
저는 각 꼭짓점의 이름을
A,B,C,D,E,1,2,3,4,5로 붙여주었구요
실제로 두 그래프를 그려 본 후 비교해보면
두 그래프 모두 각 꼭짓점당 대응되는 꼭짓점이 같습니다.
따라서 연결상태도 같고 두 그래프는 같은 그래프입니다.
실제로 시험장에서 저런 복잡한 그래프를 가지고 입체적으로 생각하기가 쉽지 않지요.
그러니 꼭짓점에 이름을 붙여서 연결상태를 확인하는게 낫다는 것입니다.
아주 간단하게 생긴 그래프는 그런
고무줄방법(변길이를 늘리거나 줄이거나 꼭짓점의 위치를 바꿔보다 같아질 수 있는지 확인하는 방법)을
사용해도 되지만
저런 복잡해보이는 그래프는
입체적으로 머릿 속으로 생각해서 같다고 생각이 들어도
직접 입체 모형을 만들어서 확인하지 않는 이상 대부분의 사람들은 확신이 서지 않기 때문에
연결상태를 확인함으로써 확실하게 같다고 증명이 가능한 것입니다.
그래프를 올려 드리겠습니다.
차수가 가장 높은 점을 하나하나 지워보세요. 그게 가장 확실합니다.
애초에 두 그래프가 isomorphic한지 확인하는 좋은 방법은 없습니다. 그러한 효율적인 알고리즘도 없구요. 결국 노가다에 맡길 수 밖에...
다만 두 그래프가 isomorphic하지 않음을 보일 땐, 노가다에 들어가기 전에 차수를 비교해본다든지, 이런 식을 통해서 먼저 금방 알아챌 수 있는건 금방 해결하는 것이 빠르겠죠.