그래프와 행렬 질문좀 할게요

Question

교과서에서 그래프와 행렬에서 활용하는 부분 즉 행렬로 나타낸것을 n제곱하는 부분에서 예를 들어 제곱했을때 1행1열 성분이 꼭짓점A에서 A로 변 2개를 겨쳐 가는 경로의 수라고 하면서 ABA ,ACA등이 나오므로 2가지로 나오고 행렬의 1행1열도 2이다라고 나와있는데요.  경로의 정의에 의하면 같은 변을 중복하지 않고 다른 꼭짓점으로 간다고 되어있는데 ABA와 ACA의 경우에는 각각 변AB ,AC를 중복하게 되므로 경로라는 단어를 쓰면 안되는것 아닌가요? 
제가 언어에 약해서 그런지 헷갈리네요.

inthecastle · Accepted Answer

경로 정의에 중복되지 않는 다는 성질은 없어요 .  

경로 = 거쳐온 길

단순경로 = 변이 중복되지 않는  경로

Winters1 · Answer

개정수1 교과서에는 경로를 같은변을 반복하지않는다고 되어있네요. 제가 반복을 중복으로 오독했네요. 근데 반복을 하지않아도 ABA에서 AB랑 BA는 같은변 아닌가요?

Kid. · Answer

경로: '그래프에서 한 꼭짓점에서 다른 꼭짓점으로 이동할 때, 이동한 순서대로 꼭짓점을 나열한 것을 경로라 한다'(꼮지점은 여러번 지나도 된다)

Loz. · Answer

원래는 같은 변을 반복하면 안되는게 맞다고 교과서나 각종 자습서에도 나와있는데요

그래서 기출에서는 경로라고 할때 밑에 주석 달아주던거같더군요

단, 같은 변을 반복해도 된다 였나 뭐였던가..

그래프와 행렬 질문좀 할게요

최근 게시글 · 더보기

오르비 캐스트