수리 질문이요ㅠㅠ
게시글 주소: https://iu.orbi.kr/0001525266
이게 같은 그래프라는데.
그래프가 같으려면 변의개수,꼭지점의차수 뿐만 아니라
변의 연결상태도 같아야되지않나요?
이 두개는 다른것같은데 왜 같은거죠ㅠ
0 XDK (+0)
유익한 글을 읽었다면 작성자에게 XDK를 선물하세요.
-
과탐이든 사탐이든 암거나 좋으니까
-
기본으로 알고 있나요? 그 막 빙빙 돌리는거 N제에 혹시 많이 나오나요
-
군필 집합. 1
저만 전역하고 멍청해진 느낌 듦?
-
2번 13번은 진짜 어렵게 잘낸거같고 도표문제들도 내용은 안어려운데 포장을 신선하게...
-
가능한가요? 동네 학원을 다니는데 블랙라벨만 완벽하게 하고 기출은 끝나고 하거나...
-
반팔에 추리닝으로 때울수있는 여름이 최고다
-
좋을까? 아니면 써킷만 매일풀어볼까...
-
앙넝 2
어넝어ㅓㅇ
-
부탁
-
우우
-
문해전 시즌1 다 끝나가는데 뭔가 이창무쌤 풀이 너무 맘에들고 문제풀면서...
-
본인 47점 (분류에서 지네랑 거머리 칸을 바꿔써서 틀려버림 ㅋㅋ) 1.우선 가장...
-
팔리긴하나
-
부산대경북대 전남대충남대 충북대 전북대 경상대
-
내일도 안씻을거임
-
정공 말고...... 아시는분 있으심?
-
수능은 아니고 그냥 중요한 시험인데 아무튼 뭐 추천하심? 개인적으로는 금딸이 크게...
-
7모 후기 3
국어: 쉬웠음. 엄청 쉬웠던 5모보단 살짝 어렵긴 했는데 그럼에도 너무나 쉬웠음....
-
웅웅웅 1
앙♡
-
이번 실모가 내 약점만 후두려 팬건지 아니면 내 깨달음이 헛된 것이었거나
-
기말 끝나서 자습시간이 앞으로 많다 달려보자잇
-
현장에서 풀이 떠올리는 사람들이 신기하다 진짜 해설강의 들으면서 풀어도 에러난것마냥...
-
AI랑 고도의 자동화시스템이 발달해서 수요 노동인구가 현재보다 확줄어들면 저출산이...
-
4규 공통 2회독씩 했고 드릴5랑 문해전1중에 하려고 하는데 항상 76-80점대를...
-
머릿속으로 그녀와의 가계도를 그려본다
-
프로필눌러보면 구석에 모셔두고있는 사람들이좀있네 이게 일년만에 바뀐 오르빈가
-
자꾸 방문을 벌컥벌컥벌컥 열어댐 할맣 잇음 할말만 하든가 자꾸 너머로 방을 훑어봄......
-
콘서타 약효가 딱 떨어지는 시기이기는한데 아무튼 집중을 못하겠어요 너무...
-
해명 7
달암 ㅋㅋㅋㅋㅋ
-
폭로하나할게요 5
샤이<이분 카리나닮은몸매에 얼굴은 한소희인 s급여붕이입니다.
-
사문개념책 보기보단 기출선지정리해서 그거 외우는식으로 하는데 괜찮나유? 그리고...
-
논란 해명합니다 29
사실 논란은 없구 잘자용
-
이거 에피 댐? 15
허접이라 교육청 에피 아니면 에피 손도 못대는데 교육청 이제 1번 남앗단 말이에요
-
대성패스인증 1
-
도형에서 말려버리는..
-
나나밤 근황모름 의사 —> 이사람이 ㅈㄴ 웃겼음 ㅋㅋㅋㅋㅋ 조시우 수복수전공의머생...
-
외울 시간이 없네…
-
폰이 갤럭쉬입니다
-
내일 아침이면 올라옴?
-
과외하는데 14
화상과외가 더 떨리노..
-
12번 수2에서 치환적분을 이용한 나 13번 그림이 기괴하게 생겼지만, 각 ACD...
-
피드 내리다보면 지혼자 릴스로 넘어가버리네 개무섭다…
-
근데 기분탓인가 2
작년 이맘때오르비하고 화력차이웰케나는거같지 오르비아하고디시 오래해서그런가
-
수특에서 굉장히 비슷한 상황을 본거같은 느낌적인 느낌이.. 지수로그함수 스텝2...
-
지로함 삼각함수 아직 ㅄ인거같음
-
집학원밖이면 너무 참피임 방학맞아 애들이랑 여행가니까 반년밖에 안지난는데 핀트...
-
[권희승] 가계도변이 맞추면 스벅2 (+지난문제 해설) 49
안녕하세요! 생1 강사 권희승T입니다. 지난 게시글의 반응이 너무 좋아서 기분 좋게...
-
6모 통통 2등급이고 확통 좀 약한데 드릴 확통 해설 없이 풀어도 괜찮을까요?...
-
공통 영역에서는 변별 문항으로는 잘 이용되지 않던 소재들 (22번 곱의 연속성)과...
변 : 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하지 않음을 보일 땐, 노가다에 들어가기 전에 차수를 비교해본다든지, 이런 식을 통해서 먼저 금방 알아챌 수 있는건 금방 해결하는 것이 빠르겠죠.