행렬 그래프 단원 어떻게 공부해야하죠?ㅠㅠ 제발살려주세요
게시글 주소: https://orbi.kr/0001537513
행렬 그래프 단원 한석원t알텍꺼는 이해도 다하고 복습도 했거든요
근데 수능특강은 그렇다 치고
수능완성 행렬그래프 단원 진짜 못풀겠어요 ㅠㅠ
특히 경로 찾기 문제 ... 진짜 하나하나 다 찾아야하는지
무슨 노가다 문제같아요.
아님 그런풀이 말고 또다른풀이가 있는건가요?
아 그리고 경로찾기문제할때 똑같은 변만 안지나면 되는거에요 아님 똑같은 꼭지점도 안되는거에요?
0 XDK (+0)
유익한 글을 읽었다면 작성자에게 XDK를 선물하세요.
변 중복은 허용하지 않고, 꼭짓점 중복은 허용합니다.
발문을 보시면 '가는 방법의 수'를 묻는 문제가 있고 '경로'를 묻는 문제가 있습니다
방법의 수는 일반적으로 변의 중복도 허용을 하지요.. 심지어는 도착지점에 갔다가 다시 나와서 돌아가는 경우도 세야 합니다.
따라서 방법의 수를 물을 때는 간단한 경우 직접 세거나, 조금 복잡할 경우 인접행렬의 거듭제곱을 통해서 구합니다.
예를 들어서 꼭짓점1에서 세 개의 변을 거쳐서 꼭짓점3 으로 가는 경우를 구하고자 한다면 인접행렬을 세제곱하되 그걸 다하지 마시고
먼저 제곱의 1행 성분만 구합니다.. 그렇게 구한 1행과 3열 성분을 곱해서 최종적으로 1행3열 성분을 구하면 빠르게 풀 수 있습니다
단 여기서 구한 결과는 변의 중복까지도 허용한 결과값이기 때문에 경로를 구하는 풀이로는 적합하지 않습니다.