문서의 임의 삭제는 제재 대상으로, 문서를 삭제하려면 삭제 토론을 진행해야 합니다. 문서 보기문서 삭제토론 인접행렬 (문단 편집) == 특수한 인접행렬 == * [[단위행렬]] 어떤 그래프의 인접행렬이 단위행렬이라면 각 정점에 대해 자기 자신과 연결되는 간선만 존재하는 그래프이다. 이때 몇 step이든 간에 자기 자신으로만 이동할 수 있고 그 경우의 수는 자기 자신으로만 계속해서 이동하는 경우 1가지뿐이므로 인접행렬의 몇 제곱이든 간에 주대각선의 성분만 1이고 나머지 성분은 모두 0인 단위행렬이 된다. * [[영행렬]] 인접행렬이 영행렬이라는 것은 그래프의 간선이 하나도 없다는 뜻이다. 즉, 어떤 정점에서 자기 자신이든 다른 정점으로든 이동이 전혀 불가능하다는 것을 의미한다. 따라서 몇 step이든 간에 이동 자체가 불가능하므로 인접행렬의 몇 제곱이든 간에 똑같이 영행렬이다. * 주대각선의 성분은 모두 0이고 나머지 성분은 모두 1인 경우 각 정점에서 모든 다른 각 정점으로의 쌍방으로 연결하는 간선이 존재하는 그래프의 인접행렬이다. 정점의 개수가 [math(v)]개일 때 간선의 개수는 [math(\displaystyle\frac{v(v+1)}{2})]개, 모든 성분의 합은 [math(v(v+1))]이다. 인접행렬을 [math(A)]라 하면 [math(A^n)]은 다음과 같다. [math(A^n=\begin{pmatrix}\displaystyle\frac{(v-1)^n+v-1}{v} & \displaystyle\frac{(v-1)^n-1}{v} & \cdots & \displaystyle\frac{(v-1)^n-1}{v} \\ \displaystyle\frac{(v-1)^n-1}{v} & \displaystyle\frac{(v-1)^n+v-1}{v} & \cdots & \displaystyle\frac{(v-1)^n-1}{v} \\ \vdots & \vdots & \ddots & \vdots \\ \displaystyle\frac{(v-1)^n-1}{v} & \displaystyle\frac{(v-1)^n-1}{v} & \cdots & \displaystyle\frac{(v-1)^n+v-1}{v}\end{pmatrix})] (단, [math(n)]은 짝수) [math(A^n=\begin{pmatrix}\displaystyle\frac{(v-1)^n+1-v}{v} & \displaystyle\frac{(v-1)^n+1}{v} & \cdots & \displaystyle\frac{(v-1)^n+1}{v} \\ \displaystyle\frac{(v-1)^n+1}{v} & \displaystyle\frac{(v-1)^n+1-v}{v} & \cdots & \displaystyle\frac{(v-1)^n+1}{v} \\ \vdots & \vdots & \ddots & \vdots \\ \displaystyle\frac{(v-1)^n+1}{v} & \displaystyle\frac{(v-1)^n+1}{v} & \cdots & \displaystyle\frac{(v-1)^n+1-v}{v}\end{pmatrix})] (단, [math(n)]은 홀수) 따라서 서로 다른 정점 간에 항상 간선이 있는 그래프에서 같은/다른 정점으로 [math(n)] step 만에 이동하는 경우의 수는 다음과 같다. * n이 짝수, 같은 정점 : [math(\displaystyle\frac{(v-1)^n+v-1}{v})]가지 * n이 짝수, 다른 정점 : [math(\displaystyle\frac{(v-1)^n-1}{v})]가지 * n이 홀수, 같은 정점 : [math(\displaystyle\frac{(v-1)^n+1-v}{v})]가지 * n이 홀수, 다른 정점 : [math(\displaystyle\frac{(v-1)^n+1}{v})]가지 * 주대각선을 포함한 모든 성분이 1인 경우 모든 정점에서 자기 자신을 포함한 모든 정점으로 직접 연결되는 간선이 있는 그래프의 경우이다. 이때의 인접행렬을 [math(A)]라 하고, 정점의 개수를 [math(v)]라고 하면 [math(A^n)]은 모든 성분이 [math(v^{n-1})]인 행렬이다. 따라서 이 그래프에서 어떤 정점이든 한 정점에서 다른 정점으로 [math(n)] step 만에 이동하는 방법의 수는 [math(v^{n-1})]이다. 이것은 [[중복순열]]을 이용해서도 쉽게 알 수 있는데, [math(n)] step 동안 중간에 지나는 정점의 개수가 [math(n-1)]이고 자기 자신을 포함한 총 [math(v)]개의 정점 중 아무 것이나 선택할 수 있기 때문이다. * 방향 그래프의 사이클 방향 그래프의 정점 [math(v_1, v_2, ..., v_p)]에 대해서 정점 [math((v_1, v_2), (v_2, v_3), ..., (v_{p-1}, v_p), (v_p, v_1))]이 그 순서대로만 연결된 사이클 형태인 경우 그 인접행렬 [math(A)]는 다음과 같다. (단, [math(v_1, v_2, ..., v_p)] 순서) [math(A=\begin{pmatrix}0 & 1 & 0 & 0 & \cdots & 0 & 0 \\ 0 & 0 & 1 & 0 & \cdots & 0 & 0 \\ 0 & 0 & 0 & 1 & \cdots & 0 & 0 \\ 0 & 0 & 0 & 0 & \cdots & 0 & 0 \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & 0 & 0 & \cdots & 0 & 1 \\ 1 & 0 & 0 & 0 & \cdots & 0 & 0\end{pmatrix})] 위와 같이 주대각선의 바로 오른쪽 성분만 1이고 나머지 성분은 모두 0인 것을 알 수 있다. 이때 [math(A^n)]은 이 그래프에서 [math(n)] step만큼 이동한 것을 나타내는데, 그 경우의 수는 각 정점 [math(v_i)]에서 [math(v_{i+n})]으로 이동하는 경우 하나뿐이다. 따라서 [math(A_{1,1+n}, A_{2,2+n}, ..., A_{p-1,n-1}, A_{p,n})] 성분의 값만 1이 되고 나머지는 모두 0이 된다. 정점의 개수인 [math(p)] step만큼 이동하는 경우는 각 정점에 대해서 다시 제자리로 돌아오는 한 가지 경우밖에 없으므로 [math(A^p=I)]가 된다. 예를 들어 [math(p=3)]인 경우 인접행렬은 다음과 같다. [math(A=\begin{pmatrix}0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0\end{pmatrix})] 또한 인접행렬의 제곱, 세제곱은 차례로 다음과 같다. 이때 [math(A^3=I)]이다. [math(A^2=\begin{pmatrix}0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0\end{pmatrix}, A^3=\begin{pmatrix}1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1\end{pmatrix})] * 방향 그래프에서 사이클이 없는 경우 방향 그래프의 정점 [math(v_1, v_2, ..., v_p)]에 대해서 정점 [math((v_1, v_2), (v_2, v_3), ..., (v_{p-1}, v_p))]가 그 순서대로만 연결된 사이클 형태인 경우 그 인접행렬 [math(A)]는 다음과 같다. 사이클인 경우에서 [math((v_p, v_1))]의 간선만 제외한 경우이다. (단, [math(v_1, v_2, ..., v_p)] 순서) [math(A=\begin{pmatrix}0 & 1 & 0 & 0 & \cdots & 0 & 0 \\ 0 & 0 & 1 & 0 & \cdots & 0 & 0 \\ 0 & 0 & 0 & 1 & \cdots & 0 & 0 \\ 0 & 0 & 0 & 0 & \cdots & 0 & 0 \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & 0 & 0 & \cdots & 0 & 1 \\ 0 & 0 & 0 & 0 & \cdots & 0 & 0\end{pmatrix})] 단지 성분 하나만 1에서 0이 되었을 뿐인데 계속 제곱했을 때의 결과는 천지 차이이다. 이때는 [math(v_p)]에서 [math(v_1)]로 이동할 수 없으므로 [math(A^n)]은 [math(A_{1,1+n}, A_{2,2+n}, ..., A_{p-n-1,p-1}, A_{p-n,p})] 성분의 값만 1이 되고 나머지는 모두 0이 된다. step 수가 가장 큰 경우는 [math(v_1)]에서 [math(v_p)]로 이동하는 경우이고 이때의 step 수는 [math(p-1)]이므로, [math(A^p)]부터는 반드시 영행렬이다. 예를 들어 [math(p=3)]인 경우 [math(A, A^2, A^3)]은 각각 다음과 같고, [math(A^3)]부터 영행렬이 된다. [math(A=\begin{pmatrix}0 & 1 & 0 \\ 0 & 0 & 1 \\ 0 & 0 & 0\end{pmatrix}, A^2=\begin{pmatrix}0 & 0 & 1 \\ 0 & 0 & 0 \\ 0 & 0 & 0\end{pmatrix}, A^3=\begin{pmatrix}0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0\end{pmatrix})]저장 버튼을 클릭하면 당신이 기여한 내용을 CC-BY-NC-SA 2.0 KR으로 배포하고,기여한 문서에 대한 하이퍼링크나 URL을 이용하여 저작자 표시를 하는 것으로 충분하다는 데 동의하는 것입니다.이 동의는 철회할 수 없습니다.캡챠저장미리보기