기초수학인접행렬#356

인접행렬

Adjacency Matrices

인접행렬은 정한 꼭짓점 순서에 따라 두 꼭짓점이 인접하면 1, 아니면 0을 적은 정사각행렬이다. 단순 무방향그래프에서는 대칭이고 대각성분이 0이며 행의 합이 차수다. 행렬에서 그래프를 다시 그리고, 제곱의 성분이 길이 2인 보행의 수임을 확인한다.

읽는 시간
약 7분
선수 개념
그래프의 뜻행렬 곱셈의 기초

직관 — 연결 여부를 칸에 저장한다

직관

전시실마다 이름을 붙이고, 출발할 방과 도착할 방을 표의 행과 열에 적자. 두 방 사이에 문이 있으면 1, 없으면 0을 기록한다. 그림의 선을 따라가지 않고도 연결을 읽고 여러 단계의 이동을 셀 수 있다.

앞 글의 그래프를 행렬로 바꾸는 방법이다. 행과 열의 순서를 먼저 고정해야 각 칸이 어느 두 꼭짓점을 뜻하는지 알 수 있다. 꼭짓점이 수백 개인 노선도나 친구 관계도 이렇게 표로 저장하면, 두 대상의 연결을 칸 하나로 확인할 수 있다.

인접행렬은 두 꼭짓점의 연결을 0과 1로 나타낸다

꼭짓점이 nn개인 단순 무방향그래프의 인접행렬은, 두 꼭짓점이 인접하면 1이고 아니면 0인 n×nn\times n 행렬이다. 꼭짓점 순서를 v1,…,vnv_1,\ldots,v_n으로 정하면 다음과 같다.

A=(aij),aij={1vi와 vj가 인접할 때,0그 밖의 경우.(1)\mathbf A=(a_{ij}),\qquad a_{ij}=\begin{cases}1&v_i\text{와 }v_j\text{가 인접할 때},\\0&\text{그 밖의 경우}.\end{cases} \tag{1}
정의
기호이름원어뜻
A\mathbf A인접행렬adjacency matrix순서를 정한 꼭짓점들의 연결 표
vi,vjv_i,v_j행·열의 꼭짓점vertexii번째와 jj번째 꼭짓점
aija_{ij}행렬 성분entryii행 jj열의 연결 여부
nn꼭짓점 수number of vertices행과 열의 개수
A2\mathbf A^2인접행렬의 제곱square of the adjacency matrixAA\mathbf A\mathbf A라는 행렬곱

교과서와 행렬 곱셈의 기초는 행렬을 보통 글씨 AA로 쓴다. 이 글에서는 꼭짓점 이름 AA와 구별하려고 인접행렬만 굵은 A\mathbf A로 쓴다. 그림 1의 순서를 A,B,C,D,EA,B,C,D,E로 정하면 다음 행렬을 얻는다.

A=(0110010100110100010100010).(2)\mathbf A=\begin{pmatrix} 0&1&1&0&0\\1&0&1&0&0\\1&1&0&1&0\\0&0&1&0&1\\0&0&0&1&0 \end{pmatrix}. \tag{2}

행렬은 식 (1)의 규칙에 따라 한 행씩 채운다. AA와 인접한 꼭짓점은 B,CB,C뿐이므로 첫 행은 0,1,1,0,00,1,1,0,0이다. 세 번째 행의 1은 CC에서 A,B,DA,B,D로 직접 갈 수 있음을 나타낸다. 나머지 행도 같은 방법으로 채운다.

위는 식 (2)의 그래프이고 아래는 같은 순서 A, B, C, D, E의 인접행렬이다. 행은 출발점, 열은 도착점으로 읽으며, 1인 칸은 실제 변과 대응한다.
그림 1 위는 식 (2)의 그래프이고 아래는 같은 순서 A, B, C, D, E의 인접행렬이다. 행은 출발점, 열은 도착점으로 읽으며, 1인 칸은 실제 변과 대응한다. figures/graph_matrix.py

행렬의 뜻에서는 두 마을 사이의 도로 수를 세어 성분에 2도 적었다. 단순 그래프에는 중복 변이 없으므로 인접행렬은 연결이 있는지만 적고, 성분은 0 또는 1뿐이다.

인접행렬에서 0은 거리가 0이라는 뜻인가요?

아니다. 인접행렬의 0은 두 꼭짓점을 직접 잇는 변이 없다는 뜻이다. 식 (2)에서 A,DA,D의 칸은 0이지만 길이 2인 A,C,DA,C,D로 이동할 수 있다. 실제 거리 정보는 이 행렬에 담지 않았다.

인접행렬의 네 가지 성질은 그래프의 어떤 사실에서 나올까?

네 성질은 각각 자기 연결이 없다는 것, 변에 방향이 없다는 것, 차수의 정의, 악수 정리에서 나온다. 우리교과서가 정리한 순서대로 이유를 붙이면 다음과 같다.

  1. 대각성분은 모두 0이다. 자기 자신으로 돌아오는 변이 없으므로 aii=0a_{ii}=0이다.
  2. 대각선을 기준으로 대칭이다. 변 vivjv_iv_j와 vjviv_jv_i는 같은 변이므로 aij=ajia_{ij}=a_{ji}다.
  3. ii행의 합은 viv_i의 차수다. ii행의 1은 viv_i와 인접한 꼭짓점마다 하나씩 있다.
  4. 모든 성분의 합은 변 수의 두 배다. 행의 합을 모두 더하면 차수의 합이기 때문이다.
∑j=1naij=deg⁡(vi),(3)\sum_{j=1}^{n}a_{ij}=\deg(v_i), \tag{3} ∑i=1n∑j=1naij=∑i=1ndeg⁡(vi)=2m.(4)\sum_{i=1}^{n}\sum_{j=1}^{n}a_{ij}=\sum_{i=1}^{n}\deg(v_i)=2m. \tag{4}

식 (2)의 행의 합은 차례로 2,2,3,2,12,2,3,2,1이고, 식 (3)에 따라 각 꼭짓점의 차수다. 모두 더한 성분 합은 1010이어서 식 (4)로 변은 55개다. 이것은 차수 합 정리를 표로 읽은 것이다. 대칭이라 같은 변이 대각선 위아래에 한 번씩 적히므로, 대각선 위쪽의 1만 세어도 변 5개를 바로 얻는다.

반대로 같은 꼭짓점 순서를 행과 열에 사용한 0·1 정사각행렬이 대칭이고 대각성분이 모두 0이면, 1인 칸의 두 꼭짓점을 이어 단순 무방향그래프를 만들 수 있다. 순서를 바꿀 때는 행과 열을 함께 같은 순서로 바꿔야 한다. 행 두 개만 맞바꾸면 대개 대칭이 깨져 인접행렬이 아니게 된다.

꼭짓점 순서가 다르면 서로 다른 그래프인가요?

아니다. 같은 그래프라도 꼭짓점 순서를 바꾸면 행과 열이 함께 재배열된 다른 모양의 인접행렬이 나온다. 식 (2)의 순서를 E,D,C,B,AE,D,C,B,A로 뒤집으면 첫 행은 EE의 연결인 0,1,0,0,00,1,0,0,0이 된다. 그래서 두 행렬을 비교할 때는 각 행과 열이 어느 꼭짓점인지 함께 적어야 한다.

인접행렬을 보고 그래프를 어떻게 그릴까?

대각선 위쪽에서 1인 칸마다 그 행과 열의 두 꼭짓점을 변으로 잇는다. 아래쪽은 같은 변을 대칭 위치에 한 번 더 적은 것이라 다시 긋지 않는다.

그리기 전에 성분이 0·1뿐인지, 대각성분이 0인지, 대칭인지부터 확인한다. 하나라도 어긋나면 단순 무방향그래프의 인접행렬이 아니다. 다음 행렬의 꼭짓점 순서를 v1,…,v5v_1,\ldots,v_5라 하자.

M=(0101110100010101010110010).(5)\mathbf M=\begin{pmatrix} 0&1&0&1&1\\1&0&1&0&0\\0&1&0&1&0\\1&0&1&0&1\\1&0&0&1&0 \end{pmatrix}. \tag{5}

식 (5)는 세 조건을 모두 만족한다. 1행의 위쪽 1은 2·4·5열에 있으므로 v1v2v_1v_2, v1v4v_1v_4, v1v5v_1v_5를 긋는다. 2행은 3열, 3행은 4열, 4행은 5열에 위쪽 1이 있어 v2v3v_2v_3, v3v4v_3v_4, v4v5v_4v_5를 얻는다.

식 (5)의 행렬에서 대각선 위쪽의 1인 여섯 칸을 굵게 표시했다. 아래는 그 여섯 칸마다 행과 열의 두 꼭짓점을 이어 그린 그래프로, 오각형에 대각선 하나가 더해진 모양이다.
그림 2 식 (5)의 행렬에서 대각선 위쪽의 1인 여섯 칸을 굵게 표시했다. 아래는 그 여섯 칸마다 행과 열의 두 꼭짓점을 이어 그린 그래프로, 오각형에 대각선 하나가 더해진 모양이다. figures/matrix_to_graph.py

그림 2의 변은 6개이고, 식 (4)로 계산한 전체 성분 합 12의 절반과 같다. 행의 합 3,2,2,3,23,2,2,3,2는 그대로 v1,…,v5v_1,\ldots,v_5의 차수다. 다 그린 뒤 차수를 그림에서 다시 세어 행의 합과 비교하면 빠뜨린 변을 찾을 수 있다.

행렬 제곱은 길이 2인 보행을 어떻게 셀까?

행렬 곱셈의 기초에서는 2×2 이하로 연습했지만, 5×5에서도 규칙은 같다. 한 행과 한 열의 대응 성분 다섯 쌍을 곱해 더한다. 식 (2)에서 AA는 첫 번째, DD는 네 번째이므로 다음처럼 계산한다.

(A2)14=0⋅0+1⋅0+1⋅1+0⋅0+0⋅1=1.(6)(\mathbf A^2)_{14} =0\cdot0+1\cdot0+1\cdot1+0\cdot0+0\cdot1=1. \tag{6}

중간 꼭짓점을 A,B,C,D,EA,B,C,D,E 순서로 시험한 결과다. 그림 3처럼 AA에서 CC로 가고 다시 DD로 가는 두 변이 모두 있을 때만 곱이 1이 된다. 나머지 중간점에서는 둘 중 하나의 연결이 없다. 따라서 길이 2의 보행은 A,C,DA,C,D 하나다.

위는 mathbf A의 1행(A의 연결), 4열(D의 연결)과 두 수의 곱을 중간 꼭짓점 A~E 순서로 늘어놓은 것이다. 곱이 1인 자리는 C 하나이고 합은 1이다. 아래 그래프의 굵은 두 변이 그 보행 A, C, D다.
그림 3 위는 A\mathbf A의 1행(A의 연결), 4열(D의 연결)과 두 수의 곱을 중간 꼭짓점 A~E 순서로 늘어놓은 것이다. 곱이 1인 자리는 C 하나이고 합은 1이다. 아래 그래프의 굵은 두 변이 그 보행 A, C, D다. figures/square_entry_products.py

일반적으로 중간 꼭짓점을 vkv_k라 하면 첫 연결과 둘째 연결이 모두 있어야 하므로 aikakja_{ik}a_{kj}를 센다. 서로 다른 중간점의 선택은 서로 다른 보행이어서 모두 더한다.

(A2)ij=∑k=1naikakj.(7)(\mathbf A^2)_{ij}=\sum_{k=1}^{n}a_{ik}a_{kj}. \tag{7}

식 (7)이 세는 보행은 꼭짓점과 변을 다시 지나도 되는 이동이다. 예를 들어 첫 대각성분은 A,B,AA,B,A와 A,C,AA,C,A를 세어 2다. 두 이동은 변을 왕복하므로 앞 글의 경로(trail)나 단순경로(path)가 아니다. 일반 단순 무방향그래프에서도 viv_i의 이웃마다 왕복 보행이 하나씩 있으므로 (A2)ii=deg⁡(vi)(\mathbf A^2)_{ii}=\deg(v_i)다.

인접행렬의 제곱은 각 칸을 제곱하나요?

아니다. 인접행렬의 제곱은 행렬곱 AA\mathbf A\mathbf A이므로 식 (6)처럼 행과 열을 곱해 더한다. 각 칸의 0·1만 제곱하면 원래 행렬과 같아져, 중간점을 거치는 이동을 셀 수 없다.

인접행렬의 제곱 전체에서는 무엇을 읽을까?

대각성분은 차수이고, 대각선 밖의 (i,j)(i,j) 성분은 viv_i와 vjv_j에 모두 인접한 꼭짓점, 곧 공통 이웃의 수다. 중간점 vkv_k가 양쪽과 모두 인접할 때만 식 (7)의 곱이 1이 되기 때문이다.

식 (2)의 인접행렬을 제곱한 전체다. 굵은 대각성분 2, 2, 3, 2, 1은 차수와 같다. C행 D열과 D행 C열은 C와 D가 인접하는데도 0이다.
그림 4 식 (2)의 인접행렬을 제곱한 전체다. 굵은 대각성분 2, 2, 3, 2, 1은 차수와 같다. C행 D열과 D행 C열은 C와 D가 인접하는데도 0이다. figures/square_matrix.py

그림 4의 A행 B열 1은 AA와 BB의 공통 이웃이 CC 하나라는 뜻이다. 친구 관계 그래프라면 두 사람의 공통 친구 수가 된다. 제곱도 대칭이므로 위쪽 절반만 읽으면 된다.

제곱은 길이 2인 보행만 센다. CC와 DD는 변으로 직접 이어져 있지만 공통 이웃이 없어 그 칸이 0이다. AA와 EE는 A,C,D,EA,C,D,E로 이어지지만 길이가 3이라 A행 E열도 0이다. 연결 여부 자체는 원래 행렬과 더 긴 이동까지 함께 보아야 한다.

핵심

인접행렬은 꼭짓점 순서에 따라 연결을 0과 1로 적은 행렬이다. 단순 무방향그래프에서는 대칭·대각성분 0이고 행의 합이 차수이며, 제곱의 (i,j)(i,j) 성분은 viv_i에서 vjv_j로 가는 길이 2인 보행의 수다.

인접행렬의 흔한 오해

  • 제곱의 성분이 2이면 직접 잇는 변이 두 개다. — 직접 연결은 원래 행렬에서 읽는다. 그림 4의 A행 A열 2는 A,B,AA,B,A와 A,C,AA,C,A라는 두 보행이다.
  • 대칭인 행렬이면 모두 이 단원의 인접행렬이다. — 성분이 0 또는 1이어야 하고 대각성분도 0이어야 한다. 도로 수를 센 행렬처럼 2 이상의 성분이 있으면 단순 그래프의 인접행렬이 아니다.
  • 제곱의 성분이 0이면 두 꼭짓점은 연결되지 않는다. — 그림 4에서 CC와 DD는 인접하지만 제곱의 그 칸은 0이다. 제곱은 길이 2인 보행만 센다.

직접 해보기

새 그래프는 꼭짓점 순서가 P,Q,R,SP,Q,R,S이고 변이 PQ,QR,RSPQ,QR,RS이다.

  1. 인접행렬을 쓰고 각 행의 합을 구하시오.
  2. 인접행렬의 제곱에서 (1,3)(1,3) 성분을 직접 계산하고 보행을 쓰시오.
  3. 같은 제곱의 (2,2)(2,2) 성분을 구하고 이 값이 단순경로의 수인지 설명하시오.
  4. 첫째와 넷째 행만 바꾸면 같은 꼭짓점 순서의 인접행렬로 사용할 수 있는지 판단하시오.
  5. 다음 두 행렬이 단순 무방향그래프의 인접행렬인지 판단하고, 맞는 것은 변의 개수와 각 꼭짓점의 차수를 구하시오. (가) (0111101111011110)\begin{pmatrix}0&1&1&1\\1&0&1&1\\1&1&0&1\\1&1&1&0\end{pmatrix} (나) (0110101110010110)\begin{pmatrix}0&1&1&0\\1&0&1&1\\1&0&0&1\\0&1&1&0\end{pmatrix}
답과 풀이
  1. 행렬은 (0100101001010010)\begin{pmatrix}0&1&0&0\\1&0&1&0\\0&1&0&1\\0&0&1&0\end{pmatrix}이고 행합은 1,2,2,11,2,2,1이다. 합은 6으로 변 3개의 두 배다.
  2. 첫 행과 셋째 열을 곱하면 0⋅0+1⋅1+0⋅0+0⋅1=10\cdot0+1\cdot1+0\cdot0+0\cdot1=1이다. 보행은 P,Q,RP,Q,R 하나다.
  3. 1⋅1+0⋅0+1⋅1+0⋅0=21\cdot1+0\cdot0+1\cdot1+0\cdot0=2다. Q,P,QQ,P,Q와 Q,R,QQ,R,Q는 출발 꼭짓점을 다시 만나고 같은 변을 왕복하므로 단순경로가 아니다.
  4. 사용할 수 없다. 바꾼 행렬의 (1,3)(1,3) 성분은 1인데 (3,1)(3,1) 성분은 0이 되어 대칭성이 깨진다. 꼭짓점 이름을 바꾸려면 열도 함께 바꿔야 한다.
  5. (가)는 0·1뿐이고 대각성분이 0이며 대칭이므로 인접행렬이다. 대각선 위쪽의 1이 6개라 변은 6개이고, 행의 합이 모두 3이라 네 꼭짓점의 차수는 모두 3이다. 네 점의 완전그래프다. (나)는 2행 3열이 1인데 3행 2열이 0이어서 대칭이 아니므로 인접행렬이 아니다.

더 읽기

  • 교육부 2022 개정 교육과정 고시 — 별책20 [12이수04-03]의 인접행렬 범위.
  • 우리교과서 이산 수학 공개본 — 인쇄131~133쪽의 인접행렬 정의, 행렬에서 그래프 그리기, 성질 ①~④를 대조했다. ‘인접행렬의 네 가지 성질’ 절의 순서가 여기에 기댄다. 본문의 행렬과 연습은 별도로 구성했다.
  • Buckingham, Graph Theory — 「Adjacency and incidence」의 정의와 「Walks and the adjacency matrix」 Proposition 2.5의 보행 수 논증. 원자료는 더 넓은 그래프도 다루지만 이 글은 단순 무방향그래프로 제한했다.
  • Levin, Graph Theory Introduction — 행렬이 저장하는 대상인 꼭짓점·변의 정의를 다시 읽는다.

영상 노트

영상 노트
  • 00:00 그림 1의 순서를 정하고 연결 표를 한 행씩 채우기
  • 00:45 식 (2)에서 성질 넷 읽기 — 대각선 0, 대칭, 행합 = 차수, 전체 합 = 변 수의 두 배
  • 01:50 식 (5)의 위쪽 1 여섯 칸으로 그림 2의 그래프 다시 그리기
  • 02:50 그림 3의 다섯 곱을 다섯 중간점 선택에 대응해 식 (6) 계산하기
  • 03:50 그림 4의 제곱 전체에서 대각 = 차수, 공통 이웃, C와 D의 0 읽기

지도에서의 위치

이 페이지의 기록
  1. 2026-11-16 · 에이전트 초안
  2. 2026-11-17 · 전수 검수 반영 — 인접행렬의 성질 넷을 이유와 함께 정리, 행렬에서 그래프를 그리는 절, 제곱 전체와 공통 이웃 해석, 굵은 글씨 표기 설명을 다른 행렬 글과 맞게 바로잡기, 꼭짓점 순서 질문 답 보강, 흔한 오해·해보기 5문항 (에이전트 수정, 그림 1→4)
  3. 2026-11-17 · 전수 검수(에이전트 편집·독립 검증) 통과 — 주인 요청으로 완성으로 올림