이런 풀이는 어떻습니까
답변 정말 감사합니다. 이렇게 성심성의껏 답변 달아주실줄 몰랐는데ㅠㅠ
다만 제 의문점이 이건데. 이것만 어떻게 해결해주세요..
연결관계를 알아보기 위해서 지금부터 점을 설정할거에요
왼쪽 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점은 연결관계가 왼쪽,오른쪽이 다르게되었어요
이래서 두 그래프는 다르다. 이렇게 생각했는데 어디가 잘못된건가요?
혹시라도 점을 배치해서 같은게 하나라도 나오면 같은 그래프라고 할 수 있는건가요?
저는 일종의 반례하나가 나오면 그래프가 같지않다.다를수있기 때문에 같지않다고 생각했거든요
0 XDK (+0)
유익한 글을 읽었다면 작성자에게 XDK를 선물하세요.
-
ㅌㅇㄷㄹ ㅎㅇㅌ
-
-
후방주의 10
푸앙대 가고싶어 우럭따
-
허리가 아우성을 지르는데
-
맞팔 받습니다 2
요새 바빠서 좀 못 왔더니 팔로워가 5명이나 줄었네요 이러다 똥테 될까봐 무서워서 우렀어...
-
뭔가 기분이 몽글몽글해요 잠이나 자야죠..
-
진짜 잔다 2트 6
안자면 200만덕 뿌림
-
2022 6월 모평 국어 비문학이 몇 번이예요...? 4
선생님이 2022 6월 모평 비문학 지문 분석해오라는데 비문학이 몇 번부터 몇...
-
캬 배부르다 1
도시락 먹길 잘했어
-
수1 사인법칙 코사인법칙 도형문제
-
-
배성민 드리블 김범준 카이스 아나토미 이창무 문해전 시즌1 3개 다 하려는데...
-
올해 챙길 것 0
공부투자운동 이 세가지는 진짜 모두 다 챙겨가야 됨
-
덕코주고가 4
-
하지만난널영원히사랑할거야물1아언제나함께하자너가멸망하더라도같이가는거야마치타이타닉
-
김범준 1
김범준 카이스 아나토미가 현우진 수분감이랑 같은 과죠?
-
제발
-
어어...
-
이중에서 골라주세여
-
영하 10도 아래로 내려갔네,..
-
전한길 유튜브에 '폭탄 테러' 암시 댓글 작성자 자수(종합) 3
[의정부=뉴시스] 김도희 기자 = 한국사 강사 전한길씨의 윤석열 대통령 탄핵 반대...
-
걍 개같음
-
초성게임 스타트 15
제시어 : ㅇㅎ
-
[단독] "민생 예산삭감 진실 알리자"면서…이재명, 증액된 예산도 삭감 '허위 정보' 공유 4
[앵커] 민주당이 허위정보 신고를 받겠다며 이른바 '민주 파출소'란 이름의 온라인...
-
이미지 써드립니다 16
섯골 먹히고 진 맨시티 장난이구 수요조사합니다
-
나무가원숭이위에올라타 1억원 정신의벽 1000만원 로우숍 1000만원 낙지러버...
-
-
충원률 보는법 0
30명 모집에 충원률이 200퍼면 90등까지 합격했다는 뜻인가요??
-
사진 맘에 안들어서 나중에 신청하고싶은데
-
ㅅㅂ 아퍼
-
현재 수1 시발점 쎈 하고 수분감을 하는 중입니다. 수분감이 복습까지 해서 1~2주...
-
尹측 ‘부정선거론’ 증인·사실조회 신청, 대부분 기각 1
윤석열 대통령 탄핵심판 5차 변론이 열린 4일 서울 종로구 헌법재판소 대심판정에 윤...
-
나도 방금 전에 앎
-
만드는 방법줌. . .
-
내가 힘돈이란 말이야
-
진심갓곡
-
그럼 나도 줘요
-
벡터로 직선표현 <------이게 ㅈㄴ 어렵네;;;;
-
여가부에서 여성형 안드로이드의 인권 보호를 위해 주인과 안드로이드의 성적인 행위...
-
시우 : (그에게 무한정 쏟아지는 종신 댓글) 종신 종신...오키..! 일단 제가...
-
2025 서울대 정시 지원자/예비 합격자를 위한 정보글 27
글 특성상 상당한 장문입니다. 여러 개의 문서에 흩어져 있던 정보들을 취합하여...
-
7만덬 주실 분 15
9만덬으로 갚아드림 언젠가
-
감상평) 이번 문제들은 전반적으로 난이도가 상당히 높으며, 단순한 어휘력이나 직관적...
-
참아야지
-
술먹고노래방특) 2
자기차례아닐때 술 점점 깸 ㅌ
-
빠워빠워
-
역시 난 설뱃이 맞아 10
이게 훨씬 어울려
-
인싸 따라하기다 돈낭비다 오명 개많음 돈값만큼 이뿐거 많은데 ㅠㅠ
-
아직안끝났다구요
-
답은 안드려요
우선 이 문제를 풀 수 있는 좋은 방법 중 하나는 다음 명제를 외워버리면 됩니다.
"꼭짓점의 갯수가 2n개 (짝수)인 두 그래프의 차수가 모두 K개로 동일하다면(K≥2) 두 그래프는 항상 같은 그래프 이다."
이 명제는 수학적 귀납법으로 증명이 됩니다. 조금 길지만.
또 다른 현실적인 풀이는 다른 분들이 설명하신대로 꼭지점과 연결상태를 대응 시켜가면서 그래프를 비교하시면 됩니다.
이 두 그래프는 연결상태가 같은 녀석이므로 하나씩 대응 시키면 같은 녀석임이 증명이 됩니다.
세번째로 직접 변을 늘리고 줄여서 같은 그래프로 만드는 방법이 있습니다만.
이 방법은 대부분 강사들도 못하던데.. 뭐 가능합니다. 언제 시간나면 올리죠 ㅋ
그리고 꼭짓점 잡는 방법(로랑이님 방법) 으로 푸는 방법은 어떤 동일한 그래프라도 맞지 않는 예를 만들 수 있습니다.
꼭짓점으로 반례를 찾겠다고 하시면 두 그래프가 맞는 그래프인지를 알 수가 없지요.
문제에서 직접 꼭짓점을 주고, :다음이 같은 그래프 인지를 판정하라" 가 아니라면,
본인이 직접 꼭짓점을 임의로 잡는 방법은(그것도 연결상태 무시하고 마음대로) 매우 위험한 방법 입니다.
방금은 제가 반례를 찾으려고 일부러 연결상태가 일치하지 않은 것을 찾았는데
모든 그래프가 항상 맞지 않은 예를 만들 수 있다면..
꼭짓점의 연결상태를 하나라도 동일하게 만들수있으면 같은 그래프고
어떻게 배치해도 연결상태가 다르면, 다른 그래프라고 생각해도 될까요?
음.. 그렇게는 생각해보지 않았는데;;
[ 꼭짓점의 연결상태를 하나라도 동일하게 만들수있으면 같은 그래프고,
어떻게 배치해도 연결상태가 다르면, 다른 그래프 이다.]
이렇게 명제를 만들어도 큰 오류는 없어 보입니다.
단지, 문제에서 꼭짓점 이름을 부여하지 않은 경우에 사용하능 하겠네요.
꼭짓점의 이름이 주어진 경우라면 함부로 꼭짓점 이름을 부여해선 안되고 그 자체로
확인해야하지만 주어지지 않은 경우라면
임의로 꼭짓점의 이름을 부여하여 rune님이 말씀하신것 처럼 연결상태 확인이 가능합니다.