행렬과 그래프 고수신분(답변부탁드려요.ㅜㅜ)

Question

제가 반수생이라...행렬 그래프에서 경로 있잖아요.수능 특강을 풀어보니까, 문제에서 경로를 구하라 할때 직접 세서 구하는 경로(지나간 변을 다시 지나지 않는 경로)와꼭지점 2개를 지나는 지나는 경로 구하기 행렬의 제곱으로 구하는 경로와 약간 다른 의미 인거 같은데확실히 설명해주실 분 없나요?답변부탁드려요.

S.E김소프 · Accepted Answer

교과과정에서 '경로' 라는 뜻은 글쓴이님이 말하신 지나간 변을 다시 지나지 않은 이동방법 정도로 아시면 되고요

이때 시점과 종점이 같은 특수한 경우를 '회로'라고 하죠

그런데 수특에서 인접행렬문제에서 '경로'라는 말을 쓰고 위에서 정의한 '경로'와는 다른방법으로, 중복해서 변을 이동하는 방법도

고려했다면 그건 잘못된 문제에요. 아마 '단, 변을 중복해서 지나는것도 경로의 수를 세는데 포함한다' 라는 식에 전제조건이 들어가야 옳죠.

이런 전제조건을 쓰지 않았다면 잘못된거에요.

매니앜ㅋ · Answer

A^2의 대각성분은  X->ㅁ->X 꼴이 되기 때문에, 차수와 같습니다. 그리고 이는 같은 변을 반복하므로 경로가 될 수 없습니다.
다만, 문제에서 (단, 변을 중복해서 지나는것도 경로에 포함한다) 라는 조건을 준다면, 이는 방법의 수와 같게 되어 경로로 취급할 수 있게 됩니다.

행렬과 그래프 고수신분(답변부탁드려요.ㅜㅜ)

최근 게시글 · 더보기

댓글이 많은 글