G·Graph Daily Lab
DAY 06 / 100
내 학습 기록
DAY 06개념·실험그래프를 담는 구조

인접 행렬로 적기

그림으로 본 그래프를 컴퓨터에 넣으려면 표로 바꿔야 합니다. 가장 직접적인 방법은 노드 수만큼의 가로세로 표입니다.

약 20분조작형 실험 확인 퀴즈
A SMALL DETOUR

이번 회차, 내 속도로.

기초를 더 짚거나 궁금한 주제로 잠깐 넓혀 보세요. 최대 3단계를 거쳐 DAY 6로 돌아옵니다.

난이도·관심 주제 고르기
이번 회차는 어느 속도로 볼까요?
더 살펴볼 주제 1~2개 선택

1/2개 선택 · 새 보충·심화 수업과 본과정 다시 읽기를 선택할 수 있어요.

이렇게 다녀와요 1단계 · 약 12분

  1. 출발 · DAY 6인접 행렬
  2. 1. 관심 주제CSR·행 포인터추가 03 · 새 추가 수업
  3. 복귀 · DAY 6원래 회차 이어가기
  • CSR·행 포인터 · 7회차에서 인접 리스트가 칸을 아낀다는 것을 본 뒤, 그 리스트를 메모리에 실제로 어떻게 늘어놓는지 확인합니다.

선택과 경로 기록은 이 브라우저에 저장됩니다. 본과정의 회차 완료와는 별도입니다.

복귀: DAY 6 → 본과정 다음 회차: DAY 7
01 / UNDERSTAND

핵심 개념

인접 행렬(adjacency matrix)은 노드 N개에 대해 N행 N열의 표를 만들고, i번째 노드에서 j번째 노드로 엣지가 있으면 (i, j) 칸에 1, 없으면 0을 적습니다. 행과 열은 같은 노드 목록 순서를 따릅니다. 두 노드가 이어졌는지는 칸 하나만 보면 되므로 바로 답할 수 있습니다.

무방향 그래프에서는 i–j 엣지가 (i, j)와 (j, i) 두 칸에 모두 1로 적혀, 표가 왼쪽 위에서 오른쪽 아래로 가는 대각선을 기준으로 대칭(symmetric)이 됩니다. 그래서 1의 개수는 엣지 수의 두 배입니다. 방향 그래프에서는 i→j만 있으면 (i, j)만 1이므로 대칭이 아닐 수 있고, 1의 개수가 곧 화살표 수입니다. 대각선 칸 (i, i)가 1이면 자기 루프입니다.

행 하나를 가로로 더하면 그 노드에서 나가는 엣지 수, 즉 진출 차수가 됩니다. 열 하나를 세로로 더하면 들어오는 엣지 수인 진입 차수입니다. 무방향 그래프는 대칭이라 행의 합과 열의 합이 같고 둘 다 차수입니다. 가중 그래프라면 1 대신 가중치를 칸에 적어 같은 표로 다룹니다.

단점은 크기입니다. 엣지가 몇 개 없어도 칸은 언제나 N²개가 필요합니다. 노드가 1만 개면 칸이 1억 개이고 대부분 0입니다. 다음 회차에서는 0을 적지 않는 인접 리스트로 이 문제를 줄입니다.

인접 행렬의 (i, j) 칸은 i에서 j로 가는 엣지를 뜻하고, 행의 합은 진출 차수, 무방향이면 표가 대칭입니다.
02 / WORKED EXAMPLE∑

작은 예제로 따라가기

01

동아리의 앞 5명(민수·지아·서준·하린·도윤) 사이 엣지는 민수–지아, 민수–서준, 지아–서준, 지아–하린, 서준–하린, 하린–도윤 6개입니다.

02

이 순서로 행렬을 만들면 민수 행은 [0,1,1,0,0], 하린 행은 [0,1,1,0,1]이고, 행의 합은 민수 2·지아 3·서준 3·하린 3·도윤 1입니다.

03

행의 합을 모두 더하면 12이고, 무방향이라 1의 개수 12는 엣지 수 6의 두 배입니다. (지아, 하린)과 (하린, 지아)가 모두 1이듯 표는 대칭입니다.

03 / EXPLORE

직접 실험해 보기

‘무방향’에서 칸 하나를 눌러 대칭 칸이 함께 바뀌는지 확인한 뒤 ‘방향’으로 바꿔 같은 칸을 누르고, footer의 1의 개수·엣지 수·행 합·대칭 여부를 비교하세요.

LIVE EXPERIMENT · ADJACENCY MATRIX

인접 행렬 칸을 눌러 엣지 만들기

무방향: (i, j)와 (j, i)가 함께 바뀌어 늘 대칭입니다.
행→열민수지아서준하린도윤행 합
민수02
지아03
서준03
하린03
도윤01
열 합2333112
민수행 합 2지아행 합 3서준행 합 3하린행 합 3도윤행 합 1

행 합 = 그 노드의 차수. 대각선 (i, i)는 자기 루프 자리라 0으로 둡니다.

1의 개수 12 · 엣지 6 (1의 개수 ÷ 2) · 대칭 예 · 행 합 [2, 3, 3, 3, 1]
04 / RECALL & PRACTICE

이번에는 직접 풀어 보세요

정답을 보기 전에 계산과 이유를 적어 보세요. 해설과 비교하고 확인 표시를 남기면 완료할 수 있습니다.

문제 1
힌트 보기

행은 출발, 열은 도착입니다. 가→나는 가 행·나 열의 칸이 1입니다.

풀이와 비교하기

가 [0,1,1,0], 나 [0,0,0,0], 다 [0,0,0,1], 라 [1,0,0,0]입니다. 행의 합(진출 차수)은 2, 0, 1, 1이고, 다 열의 합(진입 차수)은 가→다 하나로 1입니다. (가, 나)는 1인데 (나, 가)는 0이므로 대칭이 아닙니다.

풀이와 확인 표시는 이 브라우저에 저장됩니다.

YOUR NOTES

오늘 이해한 것과 다시 볼 것

계산이 달라진 이유, 헷갈린 개념, 다음에 확인할 질문을 남겨 보세요.

메모는 이 브라우저에 저장됩니다. 홈에서 전체 기록을 내려받을 수 있습니다.
05 / CHECK YOURSELF

오늘의 이해 확인

방향 그래프의 인접 행렬에서 한 노드의 진출 차수를 얻으려면?

완료 조건: 확인 퀴즈 정답 · / 직접 풀기 0/1

FURTHER READING

더 깊이 읽기

예제와 실험 데이터는 이 과정을 위해 만든 것입니다. 원문은 선택 자료이며, 강의와 직접 풀기만으로도 다음 회차를 이어갈 수 있습니다.

Network Science, Chapter 2: Graph TheoryBarabási (2016)NetworkX TutorialNetworkX

이 자료는 개념 학습용입니다. 실제 데이터베이스·라이브러리·플랫폼의 동작과 설정은 제품과 버전마다 다를 수 있습니다.