수리 질문이요ㅠㅠ
게시글 주소: https://orbi.kr/0001525266
이게 같은 그래프라는데.
그래프가 같으려면 변의개수,꼭지점의차수 뿐만 아니라
변의 연결상태도 같아야되지않나요?
이 두개는 다른것같은데 왜 같은거죠ㅠ
0 XDK (+0)
유익한 글을 읽었다면 작성자에게 XDK를 선물하세요.
-
반수생인데 현재 확통 5~6등급입니당ㅠㅠ… 김기현T 파데 끝냈고 아이디어랑 너기출...
-
반려동물 시장이 키운 '수의대 열풍'…1등급 아니면 못 간다 1
반려동물시장 급성장과 맞물려 수의대 입결(입시 결과)이 수직 상승세를 보이고 있다....
-
나머지는 쉬운 거 같은데 13번 ㄹㅇ 이렇게 풀라고 낸 건가 뭘 놓친 거지 ㅅㅂㅋㅋ
-
[단독] 검찰, 구제역 “방송인 마약 후 집단난교했다” 가짜뉴스에 기소 1
유튜버 구제역(이준희)이 다른 유튜버 주작감별사(전국진), 카라큘라(이세욱) 등과...
-
"When you get older your wild heart will live...
-
"학교는 쉬는 시간이라도"…학원 뺑뺑이에 "방학 때가 더 힘들다" 1
(서울=뉴스1) 윤주현 기자 = "공부 스트레스 때문에 정신과 약을 먹는 친구도…"...
-
17일 예정이던데 저때 칼같이 나오나? 아니면 좀 바뀌기도 하나 시간은 몇시쯤함 보통?
-
사문 올해 처음 하는 거라 들을 때 조금 과장해서 쌤이 강의에서 하시는 모든 말을...
-
강민철은 0
강민철이다
-
군수는 안된다
-
수탐 유기하고 일주일간 국어만 할 것. 깨달음 올때까지 국어만 팔 것. 너랑나랑 맞다이다 국어3꺄
-
몇 권 쳐내고 책장 빈자리 보면서 캬 여백의 미 하고 있는데 갑자기 조교가 책...
-
이미지 솔직히 4
40대치고 이쁜데 헤응,,,
-
내 자존감 돌려내 서바색기야
-
생기부에 철학관련 내용 없어도 갈 수 있나요??
-
오랜 생각이다
-
라이브반은 택배올 때 서바노트는 같이 안오나요? 답지라 안오는거 같긴 한데 담주라도...
-
ㅠㅠ
-
전형태 독서 0
전형태 독서는 어떤가요? 들어보신분들 없나요??
-
목감기 걸린듯 0
ㅅㅃ이 목 따끔하구만 다들 감기 조심하시길
-
올해도 기출이나 깍아야지.. 거지 수험생한테 시대자료 중고가격 개 비싸
-
작년(현역때) 예체능햇었어서 올해 4월부터 공부 시작했는데 모고볼 때 수학 시간관리...
-
안녕하세요 설인문지망입니다. 작년에는 이런저런 글을 쓰곤 했는데 올해는 장문글을...
-
ㄹㅇㄹㅇ
-
운동하니까 더 더워
-
국어 : 일레이나 수학 : 아야노코지 영어: 아야노코지 지구: 미사카 미코토 물2: 미사카 미코토
-
풀까말까 고민되네
-
지금하면 걍 올해는 포기한거라고 보는게 맞는건가요?
-
나를 위해서
-
국어 이정수 수학 김범준 영어 ? 물리 방인혁 지구 오지훈
-
강대x vs 7모 하나만 골라주세요
-
정석킥은 ㄹㅇ 신임 ㅇㅇ 문상추, 실모해설은 한번이라도 들어봐야한다고 생각함
-
언제까지나 복습을미룰순없는걸
-
아우졸려뒤지것네 14
오늘토익시험이라고12시에잤는데도졸리다...에효
-
버스타고 이태원 거쳐서 조기풋살 하러가는데 이태원에서 게이커플이 탔음 내 앞자리에...
-
언제 나오는지 아시는 분??
-
인강민철 앞에거 안풀고 6,7,8호 먼저 풀어도 됨요? 0
주말이라 qna 답 안해줄거 같아서 여기에 올림요 ㅠㅠ
-
수능 임박하면 2
이렇게 애니보는 대신 Ebs강의 같은거 보고 있겠지
-
얼버기 4
-
얼버기 0
-
나랑 같은때 태어났으면 서연고 갔다고 그러는데 어케 생각함? 본인은 건대24공대임...
-
재채기 잘못했더니 갑자기 뇌줄기가 끊어질듯이 아프길래 머리뒷쪽 잡고 소리지르면서...
-
헬스장 키 두고 와서 다시 집가는중
-
러셀 1
벌점 10점 이상이면 부모님한테 연락 간다는데 딱 10점 받으면 바로 가나 정석민...
-
이벙도면 n제 양치기 해서 수능날 백분위 98까지 올릴 수 있으려나 수학 진짜하
변 : 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하지 않음을 보일 땐, 노가다에 들어가기 전에 차수를 비교해본다든지, 이런 식을 통해서 먼저 금방 알아챌 수 있는건 금방 해결하는 것이 빠르겠죠.