문서의 임의 삭제는 제재 대상으로, 문서를 삭제하려면 삭제 토론을 진행해야 합니다. 문서 보기문서 삭제토론 인접행렬 (문단 편집) == 표현 방법 == 정점이 n개인 그래프의 각 정점에 대해 순서대로 [math(1, 2, ..., n)]으로 번호를 매길 때, 이 그래프에 대한 인접행렬을 [math(A)]라고 하면 다음과 같은 규칙을 따른다. (단, [math(a, b=1, 2, ..., n)]) * [math(A_{ab})] 성분의 값은 정점 [math(a)]에서 [math(b)]로 이동하는 간선이 있을 때 1, 없을 때 0이다. * 무방향 그래프일 때는 [math(a)]와 [math(b)]를 연결하는 간선이 있으면 1, 그렇지 않으면 0이다. * [math(A_{aa})] 성분, 즉 주대각선상의 성분의 값은 항상 0이다. * 단 자기 자신으로 연결되는 간선이 있으면 1이다. [[파일:인접행렬_그래프.png|width=400]] 예를 들어 위 그림에서 정점 A, B, C, D, E를 각각 숫자 1, 2, 3, 4, 5로 번호를 매기면 (가)는 무방향 그래프이므로 인접행렬은 다음과 같이 대칭행렬이다. [math(A_{가}=\begin{pmatrix}0 & 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0\end{pmatrix})] (나)는 방향 그래프이고, 그 인접행렬은 다음과 같다. [math(A_{나}=\begin{pmatrix}0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0\end{pmatrix})] (다)는 무방향 간선이 존재하는 방향 그래프이고, 그 인접행렬은 다음과 같다. [math(A_{다}=\begin{pmatrix}0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0\end{pmatrix})] (가), (나), (다) 모두 자기 자신으로 이동하는 간선은 존재하지 않으므로 주대각선상의 성분의 값은 항상 0이 된다.저장 버튼을 클릭하면 당신이 기여한 내용을 CC-BY-NC-SA 2.0 KR으로 배포하고,기여한 문서에 대한 하이퍼링크나 URL을 이용하여 저작자 표시를 하는 것으로 충분하다는 데 동의하는 것입니다.이 동의는 철회할 수 없습니다.캡챠저장미리보기