루프를 고려하지 않기로 하는 고교 과정의 그래프의 측면에서 벗어나면, 변의 개수가 대각선/2 이지는 않아요. 더구나 주어진 인접행렬은 M^2 예요. 그래서 석대님의 질문대로 루프를 고려해보면 다음과 같아요.
우선, 네 점을 a, b, c, d로 놓고, 인접행렬은 이 순서대로라고 가정. d에서 d로 2번만에 갈 수 있으려면 d에 루프가 있고 다른 점과는 연결이 되어있지 않거나, d에서 다른 점에 하나 연결이 되어 있는 경우. 그러나, 첫번째 경우는 d->b에 2번에 갈 수 없으므로, d에서는 다른 점에 하나 연결이 되어 있다.
첫댓글 .
답글 감사드립니다.^^
선생님 그려주신 그래프는 A→A로의 차수가 3이되는 데요. 문제에서는 2로 주어지고 있습니다.
다시 한번 설명 부탁드립니다 ^^; 감사합니다~
아 그러네요..잘안되네요...
네~ 감사합니다^^
이거 변의 갯수가 안 맞아서 저는 학생들한테 문제오류라고 했습니다. 변의 갯수가 대각선/2 인데 자연수값이 나오지 않더라구요
저도 그렇게생각했는데, 뭔가 있나 해서요~ 감사합니다^^
그래프에서 꼭지점의 차수의 합이 짝수가 나와야 하는 것 같은데요 ^^
감사합니다~ 그런데, 그래프에서 꼭지점D에서D로 가는 경로는 정의되지 않는건가요? 그렇게되면 차수의 합이 홀수가 되는데요.
@석대 일반적인 그래프에서 자기 자신으로 가는 경로는 정의하지 않는 것으로 기억하고 있는데, 맞는 지는 잘 모르겠네요.
@수학나라 루프를 생각하지 않기로 하는 고교 과정의 그래프가 일반적인 것이 아니라, 오히려 루프나 다중변 등이 존재하는 그래프가 일반적인 거예요.^^
루프를 고려하지 않기로 하는 고교 과정의 그래프의 측면에서 벗어나면, 변의 개수가 대각선/2 이지는 않아요.
더구나 주어진 인접행렬은 M^2 예요.
그래서 석대님의 질문대로 루프를 고려해보면 다음과 같아요.
우선, 네 점을 a, b, c, d로 놓고, 인접행렬은 이 순서대로라고 가정.
d에서 d로 2번만에 갈 수 있으려면 d에 루프가 있고 다른 점과는 연결이 되어있지 않거나,
d에서 다른 점에 하나 연결이 되어 있는 경우.
그러나, 첫번째 경우는 d->b에 2번에 갈 수 없으므로, d에서는 다른 점에 하나 연결이 되어 있다.
1) d-b 가 연결된 경우
d-b-b 여야만 d-b에 2번에 갈 수 있으므로, b에 루프 존재.
그런데, d-c도 2번에 갈 수 있으므로, d-b-c여야만 한다.
하지만, 이 경우 b-b로 2번에 갈 수 있는 경우가 3가지(모순)
2) d-c 가 연결된 경우 - 1)과 마찬가지
3) d-a 가 연결된 경우
d-b, d-c로 2번에 갈 수 있으므로, a-b, a-c에 연결.
하지면, 이 경우 a-a로 2번에 가는 경우가 3가지(모순)
그러므로, M^2의 인접행렬은 주어진 것과 같을 수 없어요.
@보이는것이전부는아냐 너무 잘배워 갑니다. 감사합니다 선생님 ^^