인접 행렬 계산기

인접 행렬, 간선 리스트, 인접 리스트 간의 변환을 수행합니다. 유향/무향 그래프 자동 감지, 차수 수열, 밀도, 연결 요소, 행렬 거듭제곱 계산 및 대화형 SVG 그래프 시각화 기능을 제공합니다.

인접 행렬 계산기

빠른 예시:

무향 삼각형+꼬리 유향 사이클 K4 (인접 리스트) 4×4 행렬 숫자 라벨

↔ 에지 리스트 ☰ 인접 리스트 ▦ 인접 행렬

그래프 데이터

A-B, A->B, A B, A,B 또는 0 1 1 0과 같은 행렬 행을 입력할 수 있습니다. 정점 라벨에는 문자, 숫자 또는 언더바(_)를 사용하세요.

행렬 라벨 (선택 사항)

쉼표 또는 공백으로 구분된 라벨을 행렬 행당 하나씩 입력하세요. 생략 시 기본값은 A, B, C…입니다.

그래프 유형

Embed 인접 행렬 계산기 Widget

인접 행렬 계산기 정보

인접 행렬 계산기는 인접 행렬, 에지 리스트, 인접 리스트라는 세 가지 표준 그래프 표현 방식 간의 변환을 돕고, 차수 시퀀스, 그래프 밀도, 연결된 컴포넌트, 행렬 거듭제곱 등의 구조적 분석 결과를 제공하는 그래프 이론 유틸리티입니다. 입력된 데이터가 유향인지 무향인지 자동으로 감지하며 모든 결과와 함께 실시간 SVG 시각화를 렌더링합니다.

인접 행렬이란 무엇인가요?

n개의 정점을 가진 그래프 G = (V, E)가 주어졌을 때, 인접 행렬은 정점 i에서 정점 j로의 에지가 있으면 성분 A[i][j]가 1이고 그렇지 않으면 0인 n × n 정사각 행렬 A입니다.

A[i][j] = 1 만약 (v_i, v_j) ∈ E , 그외 0

무향 그래프의 경우 인접 행렬은 항상 대칭입니다. 모든 에지 {u, v}는 A[u][v] = 1과 A[v][u] = 1을 모두 생성합니다. 유향 그래프(디그래프)의 경우 행렬은 각 아크의 방향을 반영하여 비대칭일 수 있습니다.

세 가지 표현 방식 — 문제에 적합한 방식 선택

표현 방식	공간	에지 조회	이웃 리스트	최적 용도
인접 행렬	Θ(n²)	O(1)	Θ(n)	밀집 그래프; 행렬 대수(거듭제곱, 고윳값)
인접 리스트	Θ(n + m)	O(deg v)	Θ(deg v)	희소 그래프; BFS/DFS 및 최단 경로 알고리즘
에지 리스트	Θ(m)	Θ(m)	Θ(m)	입력/출력, Kruskal의 MST, 에지 중심 알고리즘

계산된 주요 지표

차수 시퀀스

무향 그래프의 경우, 정점의 차수는 해당 정점에 부착된 에지의 수입니다(루프는 두 번 계산). 유향 그래프의 경우 각 정점은 진입 차수(들어오는 아크)와 진출 차수(나가는 아크)를 가집니다. 정렬된 차수 목록은 동형 검사 및 Erdős–Gallai 실현 가능성 정리에서 사용되는 고전적인 그래프 불변량입니다.

악수 정리(Handshaking Lemma): Σ deg(v) = 2m (무향) Σ in-deg(v) = Σ out-deg(v) = m (유향)

그래프 밀도

밀도는 n개의 정점에서 가능한 최대 에지 수 대비 그래프가 얼마나 "가득 차" 있는지를 측정합니다.

무향: D = 2m / (n(n−1)) 유향: D = m / (n(n−1))

밀도가 0이면 에지가 없음을, 1이면 그래프가 완전함을 의미하며, 0.1 미만의 값은 일반적으로 인접 행렬보다 인접 리스트가 공간 효율적인 희소 그래프를 나타냅니다.

연결된 컴포넌트

연결된 컴포넌트는 모든 정점 쌍이 경로로 연결된 최대 정점 집합입니다. 유향 그래프의 경우, 이 계산기는 방향을 무시했을 때의 약하게 연결된 컴포넌트를 보고합니다. 이는 각 아크를 무향 에지로 취급했을 때 얻을 수 있는 부분 집합과 같습니다.

행렬 거듭제곱 (A², A³ ... )

대수적 그래프 이론의 기본 정리에 따르면, A^k의 (i, j) 성분은 정점 i에서 정점 j까지의 길이가 정확히 k인 경로(walk)의 수와 같습니다. 따라서:

A²[i][i]는 무향 그래프에서 정점 i의 차수와 같습니다. i에서 자기 자신으로의 2단계 경로는 "이웃으로 갔다가 돌아오는 것"이기 때문입니다.
무향 그래프에서 A³의 대각합(trace)을 6으로 나누면 삼각형의 개수가 됩니다.
Aⁿ⁻¹에 0인 성분이 있는지 여부로 그래프의 연결 여부를 알 수 있습니다.

허용되는 입력 형식

1. 에지 리스트

한 줄에 하나씩 또는 쉼표로 구분하여 에지를 입력합니다. A-B, A B, A,B, A->B, A--B 등의 구분자를 모두 사용할 수 있습니다. 유향으로 강제 해석하려면 ->를 사용하세요.

A-B, B-C, C-A, C-D (꼬리가 있는 무향 4-사이클) A->B, B->C, C->D, D->A (길이 4의 유향 사이클)

2. 인접 리스트

정점: 이웃1, 이웃2, ... 형식으로 한 줄에 한 정점씩 입력합니다. 순서는 중요하지 않으며, 누락된 정점은 이웃 목록에서 자동으로 추가됩니다.

A: B, C, D B: A, C C: A, B, D D: A, C

3. 인접 행렬

공백 또는 쉼표로 구분된 0/1 값을 한 줄에 한 행씩 입력합니다. 행렬은 반드시 정사각 행렬이어야 합니다. 행렬 라벨 필드에 사용자 지정 라벨을 입력할 수 있습니다(입력하지 않으면 A, B, C…가 사용됨).

0 1 1 0 1 0 1 1 1 1 0 1 0 1 1 0

이 계산기 사용 방법

탭 선택기에서 에지 리스트, 인접 리스트, 인접 행렬 중 입력 형식을 선택합니다.
텍스트 영역에 그래프를 입력하거나 붙여넣습니다. 행렬 입력의 경우 행렬 라벨 필드에 선택적 라벨을 추가합니다.
그래프 유형을 선택합니다. '자동 감지'로 두면 화살표(->)나 행렬의 대칭성을 통해 계산기가 방향성을 추론합니다. 수동으로 지정하려면 유향 또는 무향을 선택하세요.
그래프 변환 및 분석을 클릭합니다. 결과 페이지에는 인접 행렬, 대화형 SVG 렌더링, 다른 두 가지 텍스트 표현, 차수 통계, 연결된 컴포넌트, 그래프가 충분히 작을 경우 경로 수 행렬 A² 및 A³가 표시됩니다.
행렬 행이나 그래프 노드에 마우스를 올리면 일치하는 행/열과 인접 에지가 강조 표시됩니다. 이는 각 형식이 동일한 정보를 인코딩하고 있음을 시각적으로 증명합니다.

실행 예시

정점 {A, B, C, D}와 에지 AB, BC, CA, CD를 가진 무향 그래프를 생각해 봅시다. 인접 행렬은 다음과 같습니다.

A B C D A [ 0 1 1 0 ] B [ 1 0 1 0 ] C [ 1 1 0 1 ] D [ 0 0 1 0 ]

계산기가 도출하는 주요 사실:

대칭인가요? 예 — 무향임을 확인합니다.
차수 시퀀스: (3, 2, 2, 1) — 정점 C가 중심 노드(hub)입니다.
밀도: 2·4 / (4·3) = 0.667 — 적당히 조밀한 그래프입니다.
연결됨? 예, 단일 컴포넌트입니다.
삼각형: tr(A³) = 6으로 확인되듯이 정확히 하나(A–B–C)가 존재합니다.

일반적인 응용 분야

소셜 네트워크 분석 — 친구 관계 / 팔로워 그래프, 중앙성 분석.
웹 및 인용 그래프 — PageRank 및 HITS 알고리즘은 A와 A^T를 직접 사용합니다.
라우팅 및 네트워크 — 최단 경로, 최소 컷, 최대 유량 분석.
화학 — 원자를 정점으로, 결합을 에지로 하는 분자 그래프.
일정 계획 및 의존성 해결 — 빌드 시스템의 유향 비사이클 그래프(DAG).
마르코프 체인 — 그래프에서 파생된 행-확률 행렬은 전이 확률을 인코딩합니다.

자주 묻는 질문

인접 행렬이란 무엇인가요?

인접 행렬은 유한 그래프를 나타내는 데 사용되는 n × n 정사각 행렬입니다. 정점 i에서 정점 j로의 에지가 있으면 각 셀 A[i][j]는 1이고 그렇지 않으면 0입니다. 무향 그래프의 경우 행렬은 대칭이므로 A[i][j] = A[j][i]입니다. 행렬을 사용하면 두 정점이 연결되어 있는지 상수 시간 내에 쉽게 확인할 수 있으며, 행렬 거듭제곱은 정점 간의 경로 수를 인코딩합니다.

인접 행렬에서 그래프가 유향인지 어떻게 알 수 있나요?

모든 인덱스 쌍에 대해 A[i][j]가 A[j][i]와 같은 대칭 행렬이면 무향 그래프입니다. A[i][j]가 A[j][i]와 다른 쌍이 하나라도 있으면 유향 그래프입니다. 이 계산기는 '자동 감지' 옵션을 선택했을 때 이 대칭성 검사를 자동으로 수행합니다.

인접 행렬의 k번째 거듭제곱은 무엇을 나타내나요?

A^k의 성분 (i, j)는 정점 i에서 정점 j까지의 길이가 정확히 k인 경로(walk)의 수를 나타냅니다. 예를 들어 A²[i][j]는 2단계 경로의 수이며, 이는 무향 그래프에서 i와 j 사이의 공통 이웃 수와 같습니다. 이 속성은 삼각형 계산, 도달 가능성 및 PageRank 스타일의 계산 알고리즘에 사용됩니다.

그래프 밀도란 무엇인가요?

그래프 밀도는 실제 존재하는 에지 수와 가능한 최대 에지 수의 비율입니다. n개의 정점을 가진 무향 단순 그래프의 경우 밀도 = 2m / (n(n-1))입니다. 유향 그래프의 경우 밀도 = m / (n(n-1))입니다. 밀도가 0에 가까우면 희소 그래프, 1이면 완전 그래프를 의미합니다.

인접 행렬과 인접 리스트의 차이점은 무엇인가요?

인접 행렬은 n² 비트를 사용하여 모든 정점 쌍의 연결성을 저장하므로 이웃 조회는 O(1)이지만 메모리 사용량은 O(n²)입니다. 인접 리스트는 각 정점의 실제 이웃만 저장하므로 희소 그래프에서 훨씬 적은 O(n + m) 메모리를 사용하지만, 이웃 조회에는 선형 탐색이 필요합니다. 행렬은 밀집 그래프 및 행렬 대수 연산에 더 적합하고, 리스트는 희소 그래프 및 BFS/DFS와 같은 순회 알고리즘에 더 적합합니다.

이 도구로 가중치 그래프를 처리할 수 있나요?

현재 계산기는 0/1 항목이 있는 비가중치 인접 행렬에 집중되어 있습니다. 0이 아닌 숫자 가중치가 있는 행렬을 붙여넣으면 구조 분석을 위해 모든 0이 아닌 셀이 1로 처리됩니다. 최단 경로와 같은 가중치 그래프 계산의 경우 전용 가중치 그래프 도구를 고려해 보시기 바랍니다.