문서의 임의 삭제는 제재 대상으로, 문서를 삭제하려면 삭제 토론을 진행해야 합니다. 문서 보기문서 삭제토론 인접행렬 (문단 편집) == 경로의 개수 == 인접행렬을 이용하여 정점의 개수가 [math(v)]개인 그래프의 어떤 정점 [math(a)]에서 다른 정점 [math(b)]로 이동하는 경로의 개수를 구할 수 있다. 인접행렬 [math(A)]에 대하여 [math(A^n)]은 어떤 정점에서 다른 정점으로 [math(n)] step을 거쳐서 이동하는 경로의 수를 나타낸다. 즉, [math(A^n_{ab})]는 그래프의 정점 [math(a)]에서 정점 [math(b)]로 [math(n)] step을 거쳐 이동하는 가능한 경로의 수이다. 증명은 [[수학적 귀납법]]을 사용하면 다음과 같다. * 먼저 [math(n=1)]일 때, 인접행렬 [math(A)]의 성분 [math(A_{ab})] 그 자체는 그래프의 정점 [math(a)]에서 [math(b)]로 직접 이동하는 경로가 있으면 1, 없으면 0이다. 즉 1 step을 거쳐 [math(a)]에서 [math(b)]로 이동하는 경로가 있는지를 나타내므로, 이러한 경로의 개수와 같다. * [math(n=k)]일 때 [math(A^k_{ab})] 성분을 그래프에서 정점 [math(a)]에서 [math(b)]로 [math(k)] step을 거쳐 이동하는 경로의 개수라고 하자. 이때 [math(A^{k+1}_{ab})]은 [math(A^{k+1}_{ab}=\sum_{i=1}^v A^k_{ai}A_{ib})]와 같이 구할 수 있다. 이때 [math(A^k_{ai})]는 정점 [math(a)]에서 [math(i)]로 [math(k)] step을 거쳐 이동하는 경로의 개수를, 그리고 [math(A_{ib})]는 정점 [math(i)]에서 [math(b)]로 직접 이동할 수 있는지를 나타낸다. 이 식의 각 항 [math(A^k_{ai}A_{ib})] (단, [math(i=1,2,...,v)])은 이 둘을 곱한 것과 같으므로, 정점 [math(i)]에서 [math(b)]로 직접 이동할 수 있으면 정점 [math(a)]에서 [math(i)]로 [math(k)] step을 거쳐 이동하는 경로의 개수가 되고, 이동할 수 없으면 그 경로의 개수와 상관없이 0이 된다. 따라서 정점 [math(a)]에서 [math(k)] step 만에 정점 [math(i)]를 거치고, 이후 1 step 만에 정점 [math(b)]에 도달하는 경우의 수와 같다. 따라서 그 합인 [math(A^{k+1}_{ab}=\sum_{i=1}^v A^k_{ai}A_{ib})]는 각 정점 [math(i=1,2,...,v)]에 대해 그 경우의 수를 모두 합한 것이므로, 정점 [math(a)]에서 정점 [math(b)]까지 [math(k+1)] step 만에 이동하는 경우의 수가 된다. 즉 [math(n=k)]일 때 [math(A^k_{ab})] 성분이 정점 [math(a)]에서 [math(b)]로 [math(k)] step 만에 이동하는 경우의 수이면, [math(n=k+1)]일 때 [math(A^{k+1}_{ab})] 성분은 [math(k+1)] step 만에 이동하는 경우의 수이다. * 따라서 수학적 귀납법에 의해 이것이 1 이상의 모든 자연수에 대해 성립한다. 무방향 그래프인 경우 인접행렬이 대칭행렬이므로 몇 제곱을 하든지 여전히 대칭행렬이다. 따라서 무방향 그래프에서 [math(A^n_{ab})], 즉 정점 [math(a)]에서 [math(b)]로 [math(n)] step 만에 이동하는 경로의 수는 [math(A^n_{ba})], 즉 정점 [math(b)]에서 [math(a)]로 [math(n)] step 만에 이동하는 경로의 수와 같음을 알 수 있다. 인접행렬 [math(A)]에 대해서 [math(A^2)]의 주대각선의 성분은 각 정점에서 출발하여 그 정점으로 2 step 만에 돌아오는 경우의 수를 의미하므로, 무방향 그래프에서는 해당 정점과 직접 연결된 다른 정점의 개수, 즉 간선의 개수를 나타내고, 방향 그래프에서는 해당 정점과 쌍방 직접 연결된 다른 정점의 개수를 나타낸다. sparse graph가 아닌 경우, 즉 각 정점들이 어느 정도 이상 연결되어 있는 경우 [math(A^n)]에서 [math(n)]이 커질수록 각 성분의 값, 즉 특정 정점에서 다른 정점으로 [math(n)] step 만에 이동하는 경로의 수도 늘어나는 추세를 보인다. 각 정점들 간에 상당수 연결되어 있는 경우에는 기하급수적으로 늘어나는 추세를 보인다. sparse한 무방향 그래프이거나, 방향 그래프이더라도 일부 정점들이 cycle 형태로 연결된 그래프의 경우에는 같은 이동 경로를 무한히 반복할 수 있기 때문에 [math(n)]의 값이 커져도 각 성분의 값이 0으로 수렴하지 않지만, cycle이 없는 방향 그래프의 경우 그래프 내에서 정점의 개수 이상의 횟수로 이동하는 것이 불가능하므로 [math(n)]이 커지면 각 성분의 값이 0으로 수렴하며, 정점의 수 이상으로 커지면 반드시 영행렬이 된다. 정확히는 순서대로 이동할 수 있는 정점의 chain의 최대 길이가 [math(l)]인 경우, [math(A^{l-1})]까지는 영행렬이 아니며 [math(A^l)]부터 영행렬이다.저장 버튼을 클릭하면 당신이 기여한 내용을 CC-BY-NC-SA 2.0 KR으로 배포하고,기여한 문서에 대한 하이퍼링크나 URL을 이용하여 저작자 표시를 하는 것으로 충분하다는 데 동의하는 것입니다.이 동의는 철회할 수 없습니다.캡챠저장미리보기