직관 — 연결 여부를 칸에 저장한다
전시실마다 이름을 붙이고, 출발할 방과 도착할 방을 표의 행과 열에 적자. 두 방 사이에 문이 있으면 1, 없으면 0을 기록한다. 그림의 선을 따라가지 않고도 연결을 읽고 여러 단계의 이동을 셀 수 있다.
앞 글의 그래프를 행렬로 바꾸는 방법이다. 행과 열의 순서를 먼저 고정해야 각 칸이 어느 두 꼭짓점을 뜻하는지 알 수 있다. 꼭짓점이 수백 개인 노선도나 친구 관계도 이렇게 표로 저장하면, 두 대상의 연결을 칸 하나로 확인할 수 있다.
인접행렬은 두 꼭짓점의 연결을 0과 1로 나타낸다
꼭짓점이 개인 단순 무방향그래프의 인접행렬은, 두 꼭짓점이 인접하면 1이고 아니면 0인 행렬이다. 꼭짓점 순서를 으로 정하면 다음과 같다.
| 기호 | 이름 | 원어 | 뜻 |
|---|---|---|---|
| 인접행렬 | adjacency matrix | 순서를 정한 꼭짓점들의 연결 표 | |
| 행·열의 꼭짓점 | vertex | 번째와 번째 꼭짓점 | |
| 행렬 성분 | entry | 행 열의 연결 여부 | |
| 꼭짓점 수 | number of vertices | 행과 열의 개수 | |
| 인접행렬의 제곱 | square of the adjacency matrix | 라는 행렬곱 |
교과서와 행렬 곱셈의 기초는 행렬을 보통 글씨 로 쓴다. 이 글에서는 꼭짓점 이름 와 구별하려고 인접행렬만 굵은 로 쓴다. 그림 1의 순서를 로 정하면 다음 행렬을 얻는다.
행렬은 식 (1)의 규칙에 따라 한 행씩 채운다. 와 인접한 꼭짓점은 뿐이므로 첫 행은 이다. 세 번째 행의 1은 에서 로 직접 갈 수 있음을 나타낸다. 나머지 행도 같은 방법으로 채운다.
figures/graph_matrix.py행렬의 뜻에서는 두 마을 사이의 도로 수를 세어 성분에 2도 적었다. 단순 그래프에는 중복 변이 없으므로 인접행렬은 연결이 있는지만 적고, 성분은 0 또는 1뿐이다.
인접행렬에서 0은 거리가 0이라는 뜻인가요?
아니다. 인접행렬의 0은 두 꼭짓점을 직접 잇는 변이 없다는 뜻이다. 식 (2)에서 의 칸은 0이지만 길이 2인 로 이동할 수 있다. 실제 거리 정보는 이 행렬에 담지 않았다.
인접행렬의 네 가지 성질은 그래프의 어떤 사실에서 나올까?
네 성질은 각각 자기 연결이 없다는 것, 변에 방향이 없다는 것, 차수의 정의, 악수 정리에서 나온다. 우리교과서가 정리한 순서대로 이유를 붙이면 다음과 같다.
- 대각성분은 모두 0이다. 자기 자신으로 돌아오는 변이 없으므로 이다.
- 대각선을 기준으로 대칭이다. 변 와 는 같은 변이므로 다.
- 행의 합은 의 차수다. 행의 1은 와 인접한 꼭짓점마다 하나씩 있다.
- 모든 성분의 합은 변 수의 두 배다. 행의 합을 모두 더하면 차수의 합이기 때문이다.
식 (2)의 행의 합은 차례로 이고, 식 (3)에 따라 각 꼭짓점의 차수다. 모두 더한 성분 합은 이어서 식 (4)로 변은 개다. 이것은 차수 합 정리를 표로 읽은 것이다. 대칭이라 같은 변이 대각선 위아래에 한 번씩 적히므로, 대각선 위쪽의 1만 세어도 변 5개를 바로 얻는다.
반대로 같은 꼭짓점 순서를 행과 열에 사용한 0·1 정사각행렬이 대칭이고 대각성분이 모두 0이면, 1인 칸의 두 꼭짓점을 이어 단순 무방향그래프를 만들 수 있다. 순서를 바꿀 때는 행과 열을 함께 같은 순서로 바꿔야 한다. 행 두 개만 맞바꾸면 대개 대칭이 깨져 인접행렬이 아니게 된다.
꼭짓점 순서가 다르면 서로 다른 그래프인가요?
아니다. 같은 그래프라도 꼭짓점 순서를 바꾸면 행과 열이 함께 재배열된 다른 모양의 인접행렬이 나온다. 식 (2)의 순서를 로 뒤집으면 첫 행은 의 연결인 이 된다. 그래서 두 행렬을 비교할 때는 각 행과 열이 어느 꼭짓점인지 함께 적어야 한다.
인접행렬을 보고 그래프를 어떻게 그릴까?
대각선 위쪽에서 1인 칸마다 그 행과 열의 두 꼭짓점을 변으로 잇는다. 아래쪽은 같은 변을 대칭 위치에 한 번 더 적은 것이라 다시 긋지 않는다.
그리기 전에 성분이 0·1뿐인지, 대각성분이 0인지, 대칭인지부터 확인한다. 하나라도 어긋나면 단순 무방향그래프의 인접행렬이 아니다. 다음 행렬의 꼭짓점 순서를 라 하자.
식 (5)는 세 조건을 모두 만족한다. 1행의 위쪽 1은 2·4·5열에 있으므로 , , 를 긋는다. 2행은 3열, 3행은 4열, 4행은 5열에 위쪽 1이 있어 , , 를 얻는다.
figures/matrix_to_graph.py그림 2의 변은 6개이고, 식 (4)로 계산한 전체 성분 합 12의 절반과 같다. 행의 합 는 그대로 의 차수다. 다 그린 뒤 차수를 그림에서 다시 세어 행의 합과 비교하면 빠뜨린 변을 찾을 수 있다.
행렬 제곱은 길이 2인 보행을 어떻게 셀까?
행렬 곱셈의 기초에서는 2×2 이하로 연습했지만, 5×5에서도 규칙은 같다. 한 행과 한 열의 대응 성분 다섯 쌍을 곱해 더한다. 식 (2)에서 는 첫 번째, 는 네 번째이므로 다음처럼 계산한다.
중간 꼭짓점을 순서로 시험한 결과다. 그림 3처럼 에서 로 가고 다시 로 가는 두 변이 모두 있을 때만 곱이 1이 된다. 나머지 중간점에서는 둘 중 하나의 연결이 없다. 따라서 길이 2의 보행은 하나다.
figures/square_entry_products.py일반적으로 중간 꼭짓점을 라 하면 첫 연결과 둘째 연결이 모두 있어야 하므로 를 센다. 서로 다른 중간점의 선택은 서로 다른 보행이어서 모두 더한다.
식 (7)이 세는 보행은 꼭짓점과 변을 다시 지나도 되는 이동이다. 예를 들어 첫 대각성분은 와 를 세어 2다. 두 이동은 변을 왕복하므로 앞 글의 경로(trail)나 단순경로(path)가 아니다. 일반 단순 무방향그래프에서도 의 이웃마다 왕복 보행이 하나씩 있으므로 다.
인접행렬의 제곱은 각 칸을 제곱하나요?
아니다. 인접행렬의 제곱은 행렬곱 이므로 식 (6)처럼 행과 열을 곱해 더한다. 각 칸의 0·1만 제곱하면 원래 행렬과 같아져, 중간점을 거치는 이동을 셀 수 없다.
인접행렬의 제곱 전체에서는 무엇을 읽을까?
대각성분은 차수이고, 대각선 밖의 성분은 와 에 모두 인접한 꼭짓점, 곧 공통 이웃의 수다. 중간점 가 양쪽과 모두 인접할 때만 식 (7)의 곱이 1이 되기 때문이다.
figures/square_matrix.py그림 4의 A행 B열 1은 와 의 공통 이웃이 하나라는 뜻이다. 친구 관계 그래프라면 두 사람의 공통 친구 수가 된다. 제곱도 대칭이므로 위쪽 절반만 읽으면 된다.
제곱은 길이 2인 보행만 센다. 와 는 변으로 직접 이어져 있지만 공통 이웃이 없어 그 칸이 0이다. 와 는 로 이어지지만 길이가 3이라 A행 E열도 0이다. 연결 여부 자체는 원래 행렬과 더 긴 이동까지 함께 보아야 한다.
인접행렬은 꼭짓점 순서에 따라 연결을 0과 1로 적은 행렬이다. 단순 무방향그래프에서는 대칭·대각성분 0이고 행의 합이 차수이며, 제곱의 성분은 에서 로 가는 길이 2인 보행의 수다.
인접행렬의 흔한 오해
- 제곱의 성분이 2이면 직접 잇는 변이 두 개다. — 직접 연결은 원래 행렬에서 읽는다. 그림 4의 A행 A열 2는 와 라는 두 보행이다.
- 대칭인 행렬이면 모두 이 단원의 인접행렬이다. — 성분이 0 또는 1이어야 하고 대각성분도 0이어야 한다. 도로 수를 센 행렬처럼 2 이상의 성분이 있으면 단순 그래프의 인접행렬이 아니다.
- 제곱의 성분이 0이면 두 꼭짓점은 연결되지 않는다. — 그림 4에서 와 는 인접하지만 제곱의 그 칸은 0이다. 제곱은 길이 2인 보행만 센다.
직접 해보기
새 그래프는 꼭짓점 순서가 이고 변이 이다.
- 인접행렬을 쓰고 각 행의 합을 구하시오.
- 인접행렬의 제곱에서 성분을 직접 계산하고 보행을 쓰시오.
- 같은 제곱의 성분을 구하고 이 값이 단순경로의 수인지 설명하시오.
- 첫째와 넷째 행만 바꾸면 같은 꼭짓점 순서의 인접행렬로 사용할 수 있는지 판단하시오.
- 다음 두 행렬이 단순 무방향그래프의 인접행렬인지 판단하고, 맞는 것은 변의 개수와 각 꼭짓점의 차수를 구하시오. (가) (나)
답과 풀이
- 행렬은 이고 행합은 이다. 합은 6으로 변 3개의 두 배다.
- 첫 행과 셋째 열을 곱하면 이다. 보행은 하나다.
- 다. 와 는 출발 꼭짓점을 다시 만나고 같은 변을 왕복하므로 단순경로가 아니다.
- 사용할 수 없다. 바꾼 행렬의 성분은 1인데 성분은 0이 되어 대칭성이 깨진다. 꼭짓점 이름을 바꾸려면 열도 함께 바꿔야 한다.
- (가)는 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 읽기
지도에서의 위치
- 2026-11-16 · 에이전트 초안
- 2026-11-17 · 전수 검수 반영 — 인접행렬의 성질 넷을 이유와 함께 정리, 행렬에서 그래프를 그리는 절, 제곱 전체와 공통 이웃 해석, 굵은 글씨 표기 설명을 다른 행렬 글과 맞게 바로잡기, 꼭짓점 순서 질문 답 보강, 흔한 오해·해보기 5문항 (에이전트 수정, 그림 1→4)
- 2026-11-17 · 전수 검수(에이전트 편집·독립 검증) 통과 — 주인 요청으로 완성으로 올림