인접행렬

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

인접 행렬은 그래프를 나타내는 데 사용되는 정사각 행렬로, 그래프의 꼭짓점 간의 연결 관계를 표현한다. 인접 행렬은 그래프 이론에서 널리 사용되며, 그래프의 속성을 분석하고 다양한 알고리즘을 구현하는 데 중요한 역할을 한다. 무향 그래프의 경우 인접 행렬은 대칭 행렬이며, 유향 그래프의 경우 비대칭 행렬이 될 수 있다. 인접 행렬의 스펙트럼은 그래프의 중요한 속성을 나타내며, 그래프의 동형 여부를 판단하는 데 사용될 수 있다. 인접 행렬은 컴퓨터 프로그램에서 그래프를 표현하고 조작하기 위한 자료 구조로 사용되며, 인접 리스트와 함께 그래프 표현의 주요 방식으로 활용된다.

더 읽어볼만한 페이지

그래프 자료 구조 - 노드 (컴퓨터 과학)
노드는 컴퓨터 과학에서 트리 구조를 이루는 구성 요소로, 자료 구조 내 정보를 표현하며, 값, 조건, 다른 자료 구조를 포함하고 부모 노드에 의해 표현되며, 웹 페이지 구조를 표현하는 데 사용된다.
그래프 자료 구조 - 그래프 (자료 구조)
그래프는 정점과 간선으로 구성되어 정점 간의 관계를 표현하는 비선형 자료 구조로, 방향, 무방향, 가중치 그래프 등 다양한 형태로 존재하며, 인접 리스트, 인접 행렬 등으로 표현되고, DFS, BFS, 다익스트라, 플로이드-워셜 알고리즘 등을 통해 탐색 및 문제 해결에 활용된다.
대수적 그래프 이론 - 중심성
중심성은 그래프 이론에서 네트워크 내 노드의 중요성을 평가하기 위한 지표로, 차수 중심성, 근접 중심성 등 다양한 종류가 있으며 네트워크 흐름, 워크 구조 등 다양한 특징에 따라 분류된다.
대수적 그래프 이론 - 거리 정규 그래프
거리 정규 그래프는 지름이 d일 때 특정 조건을 만족하며 교차 배열로 특징지어지는 그래프로, 완전 그래프, 순환 그래프, 홀수 그래프 등이 그 예시이다.
그래프 이론 - 다이어그램
다이어그램은 2차원 기하학적 기호를 사용하여 정보를 시각적으로 표현하는 기술로, 과학, 공학, IT, 비즈니스 등 다양한 분야에서 활용되며 정보를 간략하게 나타내고 시각적 사고를 돕는다.
그래프 이론 - 쾨니히스베르크의 다리 문제
쾨니히스베르크의 다리 문제는 프레겔 강에 놓인 7개의 다리를 한 번씩만 건너 출발점으로 되돌아올 수 있는지 묻는 문제로, 오일러에 의해 그래프 이론적으로 분석되어 해결되었으며 그래프 이론의 탄생에 기여했다.

인접행렬
개요
유형	정사각행렬
용도	그래프 표현
정의
정의	그래프의 정점 간의 인접 관계를 나타내는 행렬
(i, j) 원소	정점 i와 정점 j가 인접하면 1, 그렇지 않으면 0
특징
무향 그래프	대칭 행렬
가중 그래프	가중치를 원소로 가짐
활용
경로 찾기	행렬 곱셈을 통해 특정 길이의 경로 존재 여부 확인 가능
연결 요소 찾기	행렬 연산을 통해 그래프의 연결 요소 파악 가능
클러스터링 계수 계산	그래프의 밀집도 측정
예시
그래프	(그래프 이미지 또는 그래프 설명)
인접 행렬	(인접 행렬 예시)

2. 정의

}}을 갖는 단순 그래프의 경우, 인접 행렬은 요소 가 꼭짓점 에서 꼭짓점 로 가는 변이 있을 때 1이고, 변이 없을 때 0인 정사각 행렬 이다.^[1] 행렬의 대각선 요소는 모두 0인데, 단순 그래프에서는 꼭짓점 자체로 가는 변( 루프)을 허용하지 않기 때문이다. 또한, 대수적 그래프 이론에서는 0이 아닌 요소를 대수 변수로 대체하는 것이 유용할 때도 있다.^[2]

같은 개념은 두 꼭짓점 사이의 변의 수를 해당하는 행렬 요소에 저장하거나 비 제로 대각 요소를 허용함으로써 다중 그래프나 루프를 가진 그래프로 확장할 수 있다. 루프는 일관된 관습에 따르는 한, 1회 (단일 변)로 세거나 2회 (2개의 꼭짓점-변 연결로)로 세어도 된다. 무방향 그래프는 루프를 2회 세는 후자의 관습을 사용하는 경우가 많지만, 방향 그래프는 일반적으로 전자의 관습을 사용한다.

2. 1. 무향 그래프

무향 그래프에서 인접행렬은 각 변이 행렬의 해당 셀에 1을 더하고, 각 루프(정점에서 자기 자신으로 가는 변)가 행렬의 대각선에 있는 해당 셀에 2를 더하는 방식으로 표현된다.^[4] 이를 통해 인접 행렬에서 해당 행이나 열의 값의 합을 구하여 정점의 차수를 쉽게 찾을 수 있다.^[4]

라벨링된 그래프	인접 행렬
6n-graph2
나우루 그래프	나우루 그래프의 인접행렬

2. 2. 유향 그래프

방향 그래프의 인접 행렬은 비대칭적일 수 있다.^[5] 인접 행렬에서 정점의 진입 차수는 해당 열의 항목을 합산하여 계산할 수 있고, 정점의 진출 차수는 해당 행의 항목을 합산하여 계산할 수 있다.^[6]

라벨링된 그래프	인접 행렬
250px	250px

2. 3. 이분 그래프

이분 그래프는 두 부분으로 나뉘며, 각 부분에 ''r''개와 ''s''개의 정점이 있는 경우, 인접 행렬 ''A''는 다음과 같은 특수한 형태로 표현할 수 있다.

:

A = \begin{pmatrix} 0_{r,r} & B \\ B^\mathsf{T} & 0_{s,s} \end{pmatrix},

여기서 ''B''는 ''r'' × ''s'' 행렬이고, 0_''r'',''r''와 0_''s'',''s''는 각각 ''r'' × ''r''와 ''s'' × ''s'' 영행렬을 나타낸다. 이 때, 작은 행렬 ''B''가 그래프를 고유하게 나타내며, ''A''의 나머지 부분은 중복 정보로 간주하여 생략할 수 있다. ''B''는 "이중 인접 행렬"이라고도 불린다.

형식적으로, ''G'' = (''U'', ''V'', ''E'')를 두 부분 ''U'' = {''u''₁, ..., ''u''_''r''}, ''V'' = {''v''₁, ..., ''v''_''s''}와 변 ''E''를 가진 이분 그래프라고 할 때, 이중 인접 행렬은(''u''_''i'', ''v''_''j'') ∈ ''E''일 때에만 ''b''_''i'',''j'' = 1인 ''r'' × ''s'' 0-1 행렬 ''B''이다.

만약 ''G''가 이분 멀티 그래프 또는 가중 그래프라면, 원소 ''b_i,j''는 정점 사이의 변의 개수 또는 변 (''u''_''i'', ''v''_''j'')의 가중치로 간주된다.

2. 4. 가중 그래프

변에 가중치가 있는 가중 그래프의 경우, 인접 행렬의 원소는 해당 변의 가중치를 나타낸다. 단순 그래프의 (''a'', ''b'', ''c'') - "인접 행렬"은, (''i'', ''j'')가 변이라면 ''A''_''i'',''j'' = ''a'', 변이 아니라면 ''b'', 대각선상에 ''c''를 가진다. 세이델 인접 행렬(Seidel adjacency matrix)은 (−1, 1, 0) - "인접 행렬"이다. 이 행렬은 강정칙 그래프와 투 그래프(Two-graph) 연구에 사용된다.^[3]^[18] 거리 행렬은 위치 (''i'', ''j'')에 정점 ''v_i''와 ''v_j'' 사이의 거리를 갖는다. 이 거리는 정점을 연결하는 최단 경로의 길이이다. 변의 길이가 명시적으로 주어지지 않는 한, 경로의 길이는 경로 상의 변의 수이다. 거리 행렬은 인접 행렬의 고차 거듭제곱과 유사하지만, 두 정점이 연결되어 있는지 여부만 알려주는 대신 정점 간의 정확한 거리를 제공한다.

2. 5. 화살집의 인접 행렬

국소 유한 화살집

Q

의 '''인접 행렬'''은 실수 선형 변환

\mathsf A_Q \colon \mathbb R^{\operatorname V(Q)} \to \mathbb R^{\operatorname V(Q)}

이며, 그 성분은

\langle j|\mathsf A_Q|i\rangle = |\hom_Q(i,j)|

이다. 즉,

A_{ij}

는

v_i

에서 시작하고

v_j

에서 끝나는 변의 수이다. 만약 이러한 변이 없다면

A_{ij}=0

이다. 특히,

A_{ii}

는 꼭짓점

v_i

에서 스스로로 가는 변의 수이다.^[3] 이는 일반적으로 대칭 연산자가 아니다.

이에 따라, 화살집

Q

에 대하여,

\langle j|\mathsf A_Q^n|i\rangle \in\mathbb N

은 꼭짓점

i\in\operatorname V(\Gamma)

에서 꼭짓점

j\in\operatorname V(\Gamma)

로 가는, 길이

n

의 보행의 수이다. 마찬가지로, 대각합

\operatorname{tr}\mathsf A_Q^n

은 길이

n

의 순환의 수이다.

3. 성질

유한 그래프 $\Gamma$ 의 인접 행렬의 고윳값의 집합을 $\Gamma$ 의 '''스펙트럼'''(spectrum^영어)이라고 하고, $\operatorname{Spec}\Gamma$ 로 표기한다.

그래프는 자기 고리를 가질 수 없으므로, 그래프의 인접 행렬의 대각 성분들은 모두 0이다. 이에 따라, 그 대각합은 항상 0이다. 즉, 스펙트럼의 원소들의 (중복수를 고려한) 합은 0이다.

$\Gamma$ 의 스펙트럼의 최댓값 $\lambda_1(\Gamma)$ 은 $\Gamma$ 의 최대 차수(한 꼭짓점에 연결된 변의 수의 최댓값)보다 같거나 작다.

: $\max\operatorname{Spec}(\Gamma) \le \max\deg_\Gamma = \max_{i\in\operatorname V(\Gamma)}\deg_\Gamma i$

또한, 유한 정규 그래프 $\Gamma$ 에 대하여, 이 부등식이 포화된다.

: $\max\operatorname{Spec}(\Gamma) = \max\deg_\Gamma = \max_{i\in\operatorname V(\Gamma)}\deg_\Gamma i$

정규 그래프의 경우 이 고윳값 $\max\deg_\Gamma$ 의 중복수는 $\Gamma$ 의 연결 성분의 수와 같다. 각 연결 성분 $C\subseteq\Gamma$ 에 대응하는 고유 벡터 $|\psi_C\rangle$ 는 각 연결 성분 $C$ 에 대하여

: $\langle i|\psi_C\rangle = \begin{cases}1 & i \in C \\0 & i \not\in C\end{cases}$

의 꼴이다. 특히,

: $(1,1,\dotsc,1)$

는 항상 고윳값 $\max\deg_\Gamma$ 의 고유 벡터를 이룬다.

3. 1. 스펙트럼

무방향 단순 그래프의 인접 행렬은 대칭 행렬이므로, 실수 고유값과 직교하는 고유 벡터 기저를 갖는다. 그래프의 고유값 집합은 그래프의 '''스펙트럼'''이다.^[7] 고유값은

\lambda_1\geq \lambda_2\geq \cdots \geq \lambda_n.

으로 표시하는 것이 일반적이다.

최대 고유값

\lambda_1

은 최대 차수보다 크지 않다. 이는 페론-프로베니우스 정리의 결과로 볼 수 있지만, 쉽게 증명할 수 있다.

\lambda_1

에 관련된 고유 벡터를 라고 하고, 가 최대 절대값을 갖는 항목을 라고 하자. 일반성을 잃지 않고 가 양수라고 가정하자. 그렇지 않으면 단순히 고유 벡터 -를 사용하면 되며, 이는 또한

\lambda_1

과 관련이 있다. 그러면

:

\lambda_1 v_x = (Av)_x = \sum_{y=1}^n A_{x,y}v_y \leq \sum_{y=1}^n A_{x,y} v_x = v_x \deg(x).

정규 그래프의 경우, (1, …, 1)}}}} 벡터에 대한 의 첫 번째 고유값은 이다(고유값인지 확인하는 것은 쉬우며, 위에서 언급한 경계 때문에 최대값이다). 이 고유값의 중복성은 의 연결 요소의 수이며, 특히 연결 그래프의 경우 $\lambda_1>\lambda_2$ 이다. 각 고유값 $\lambda_i$ 에 대해 가 이분 그래프인 경우 그 반대 $-\lambda_i = \lambda_{n+1-i}$ 도 의 고유값임을 나타낼 수 있다.^[8] 특히 −는 모든 -정규 이분 그래프의 고유값이다.

차이

\lambda_1 - \lambda_2

는 스펙트럼 갭이라고 하며 의 익스팬더 그래프와 관련이 있다.

A

의 스펙트럼 반경을

\lambda(G) = \max_{\left|\lambda_i\right| < d} |\lambda_i|

로 표시하는 것도 유용하다. 이 숫자는

\lambda(G) \geq 2\sqrt{d-1} - o(1)

로 제한된다. 이 경계는 여러 분야에 적용되는 라마누잔 그래프에서 정확하다.

3. 2. 연산과의 호환성

임의의 두 그래프

\Gamma

,

\Gamma'

에 대하여, 그래프의 분리합집합

\operatorname{Spec} (\Gamma\sqcup \Gamma')

은 중복집합의 분리합집합

\operatorname{Spec} \Gamma \sqcup \operatorname{Spec}\Gamma'

이다. 또한, 임의의 두 그래프

\Gamma

,

\Gamma'

에 대하여, 그래프 데카르트 곱

\operatorname{Spec} (\Gamma\square \Gamma')

은

\lambda + \lambda' \colon \lambda \in \operatorname{Spec} \Gamma , \;\lambda'\in \operatorname{Spec}\Gamma'

이다.

3. 3. 그래프 동형

같은 수의 꼭짓점을 갖는 임의의 두 유한 그래프

\Gamma

,

\Gamma'

에 대하여, 두 그래프가 동형일 필요 충분 조건은

:

P\mathsf A_\Gamma = \mathsf A_{\Gamma'}P

인 치환행렬

:

P \colon \mathbb R^{\operatorname V(\Gamma)} \to \mathbb R^{\operatorname V(\Gamma')}

가 존재하는 것이다.^[9]^[21]

반면, 서로 동형이 아니지만, 스펙트럼이 같은 그래프들이 알려져 있다. 인접 행렬 '''A'''₁ 및 '''A'''₂를 갖는 두 개의 유향 또는 무향 그래프 '''G'''₁ 및 '''G'''₂가 주어졌다고 가정한다. '''G'''₁ 및 '''G'''₂는,

:

P A_1 P^{-1} = A_2

와 같은 치환 행렬 '''P'''가 존재할 때, 그리고 그 때에만 동형이다.

구체적으로, '''A'''₁ 및 '''A'''₂는 닮음이며, 따라서 동일한 최소 다항식, 고유 다항식, 고유값, 행렬식, 대각합을 갖는다. 따라서 이들은 그래프의 동형 불변량으로 기능한다. 그러나 두 그래프가 동일한 고유값 집합을 가질 수 있지만, 동형이 아닐 수 있다. 이러한 선형 작용소는 등 스펙트럼/isospectral^영어적이라고 한다.

3. 4. 행렬의 거듭제곱

인접 행렬의 거듭제곱은 그래프 내에서 특정 길이의 보행의 개수를 나타낸다. 그래프 ''G''의 인접 행렬이 ''A''라면, ''A''^''n'' (''A''의 ''n''개의 행렬 곱)의 원소 (''i'', ''j'')는 정점 ''i''에서 정점 ''j''까지의 길이가 ''n''인 보행의 수를 나타낸다.^[10] 만약 ''n''이 어떤 ''i'', ''j''에 대해 ''A''^''n''의 원소 (''i'', ''j'')가 양수가 되도록 하는 가장 작은 음이 아닌 정수라면, ''n''은 정점 ''i''와 정점 ''j'' 사이의 거리이다.^[10]

예를 들어, 무방향 그래프 ''G''에서 삼각형의 수는 ''A''³의 대각합을 6으로 나눈 값과 같다.^[10] 이는 각 삼각형이 시계 방향 또는 시계 반대 방향으로 두 번 계산되기 때문이다.^[10] 인접 행렬은 그래프의 연결 여부를 판단하는 데에도 사용될 수 있다.

4. 응용

인접 행렬은 그래프 표현을 위한 자료 구조로 컴퓨터 프로그램에서 그래프를 조작하는 데 사용될 수 있다. 인접 행렬의 주요 대안 자료 구조는 인접 리스트이다.^[11]^[12]

인접 행렬을 표현하는 데 필요한 공간과 연산 수행 시간은 선택된 행렬 표현에 따라 달라진다. 희소 행렬 표현은 0이 아닌 항목만 저장하고 0 항목은 암시적으로 나타내므로, 희소 그래프의 인접 행렬 표현에 사용되어 공간 오버헤드를 줄일 수 있다. 일반적으로 인접 행렬은 배열 자료 구조로 표현되어 0과 0이 아닌 항목이 모두 저장소에 직접 표시된다.

인접 행렬의 각 항목은 1비트만으로 표현 가능하여 매우 압축적이다. 방향 그래프는 |''V'' |² / 8 바이트, 무방향 그래프는 |''V'' |² / 16 바이트로 표현 가능하다. 이는 정보 이론적 하한에 근접한 값이다.^[13] 텍스트 파일에 그래프를 저장할 때는 Base64 표현 등을 사용하여 바이트당 더 적은 비트를 사용할 수 있다.^[14] 이러한 압축성은 공간 절약 외에도 참조 지역성을 장려한다. 그러나 큰 희소 그래프의 경우, 인접 리스트가 존재하지 않는 간선을 표현하는 공간을 낭비하지 않으므로 더 적은 저장 공간을 필요로 한다.^[12]^[15]

인접 행렬의 대안적인 형태는 행렬의 각 요소의 숫자를 간선 객체에 대한 포인터(간선이 있는 경우) 또는 null 포인터(간선이 없는 경우)로 대체하는 것이다.^[15] 가중 그래프의 경우 간선 가중치를 인접 행렬의 요소에 직접 저장할 수 있다.^[12]

공간 효율성 외에도, 자료 구조에 따라 서로 다른 연산이 용이해진다. 인접 리스트에서 주어진 정점에 인접한 모든 정점을 찾는 것은 리스트를 읽는 것만큼 간단하며 이웃 수에 비례하는 시간이 걸린다. 반면, 인접 행렬에서는 전체 행을 스캔해야 하므로 전체 그래프의 정점 수에 비례하는 더 많은 시간이 걸린다. 두 정점 사이에 간선이 있는지 여부는 인접 행렬을 사용하면 즉시 결정 가능하지만, 인접 리스트를 사용하면 두 정점의 최소 차수에 비례하는 시간이 필요하다.^[12]^[15]

4. 1. 자료 구조

인접 행렬은 그래프 표현을 위한 자료 구조로 컴퓨터 프로그램에서 그래프를 조작하는 데 사용될 수 있다. 인접 행렬의 주요 대안 자료 구조는 인접 리스트이다.^[11]^[12]

인접 행렬을 표현하는 데 필요한 공간과 연산 수행 시간은 선택된 행렬 표현에 따라 달라진다. 희소 행렬 표현은 0이 아닌 항목만 저장하고 0 항목은 암시적으로 나타내므로, 희소 그래프의 인접 행렬 표현에 사용되어 공간 오버헤드를 줄일 수 있다. 일반적으로 인접 행렬은 배열 자료 구조로 표현되어 0과 0이 아닌 항목이 모두 저장소에 직접 표시된다.

인접 행렬의 각 항목은 1비트만으로 표현 가능하여 매우 압축적이다. 방향 그래프는 |''V'' |² / 8 바이트, 무방향 그래프는 |''V'' |² / 16 바이트로 표현 가능하다. 이는 정보 이론적 하한에 근접한 값이다.^[13] 텍스트 파일에 그래프를 저장할 때는 Base64 표현 등을 사용하여 바이트당 더 적은 비트를 사용할 수 있다.^[14] 이러한 압축성은 공간 절약 외에도 참조 지역성을 장려한다. 그러나 큰 희소 그래프의 경우, 인접 리스트가 존재하지 않는 간선을 표현하는 공간을 낭비하지 않으므로 더 적은 저장 공간을 필요로 한다.^[12]^[15]

인접 행렬의 대안적인 형태는 행렬의 각 요소의 숫자를 간선 객체에 대한 포인터(간선이 있는 경우) 또는 null 포인터(간선이 없는 경우)로 대체하는 것이다.^[15] 가중 그래프의 경우 간선 가중치를 인접 행렬의 요소에 직접 저장할 수 있다.^[12]

공간 효율성 외에도, 자료 구조에 따라 서로 다른 연산이 용이해진다. 인접 리스트에서 주어진 정점에 인접한 모든 정점을 찾는 것은 리스트를 읽는 것만큼 간단하며 이웃 수에 비례하는 시간이 걸린다. 반면, 인접 행렬에서는 전체 행을 스캔해야 하므로 전체 그래프의 정점 수에 비례하는 더 많은 시간이 걸린다. 두 정점 사이에 간선이 있는지 여부는 인접 행렬을 사용하면 즉시 결정 가능하지만, 인접 리스트를 사용하면 두 정점의 최소 차수에 비례하는 시간이 필요하다.^[12]^[15]

4. 2. 알고리즘

5. 예시

다음과 같은 유한 그래프를 생각하자.

이 그래프의 인접 행렬은 다음과 같은 대칭 행렬이다.

:

A=\begin{pmatrix}0 & 1 & 0 & 0 & 1 & 0\\1 & 0 & 1 & 0 & 1 & 0\\0 & 1 & 0 & 1 & 0 & 0\\0 & 0 & 1 & 0 & 1 & 1\\1 & 1 & 0 & 1 & 0 & 0\\0 & 0 & 0 & 1 & 0 & 0\\\end{pmatrix}

이 그래프의 스펙트럼은 다음과 같다.

:

\{2.54, 1.08, 0.26, -0.54, -1.21, -2.14 \}

이들의 합은 0이며, 그 최댓값 2.54는 그래프의 최대 차수 3보다 작다.

5. 1. 무변 그래프

무변 그래프

\bar\mathsf K_n

의 인접 행렬은 영행렬이다.

:

\mathsf A_{\bar\mathsf K_n} = 0

그 스펙트럼의 유일한 원소는 0이며, 그 중복수는

n

이다. 완전 그래프의 인접 행렬은 대각선을 제외한 모든 요소가 1이고, 빈 그래프의 인접 행렬은 영 행렬이다.

5. 2. 완전 그래프

완전 그래프

\mathsf K_n

의 인접 행렬은 다음과 같은 꼴이다.

:

\mathsf A_{\mathsf K_n} = \mu_{n\times n} - 1_{n\times n}

여기서

\mu

는 모든 성분이 1인 행렬이다.

그 스펙트럼은 다음과 같다.

:

\operatorname{Spec}\mathsf A_{\mathsf K_n} = \{n-1, \underbrace{-1, -1,\dotsc,-1}_{n-1} \}

완전 그래프의 인접 행렬은 성분이 0인 대각 요소를 제외하고는 모두 1을 포함한다. 빈 그래프의 인접 행렬은 영행렬이다.

5. 3. 완전 이분 그래프

완전 이분 그래프

\mathsf K_{m,n}

의 인접 행렬은 다음과 같은 꼴이다.

:

\mathsf A_{\mathsf K_{m,n}} = \begin{pmatrix}0_{m\times m}& \mu_{m\times n} \\\mu_{n\times m}&0_{n\times n}\end{pmatrix}

여기서

\mu

는 모든 성분이 1인 행렬이다.

완전 이분 그래프

\mathsf K_{m,n}

의 스펙트럼은 다음과 같다.

:

\operatorname{Spec}\mathsf K_{m,n} = \{+ \sqrt{mn}, -\sqrt{mn},\underbrace{ 0,0,\dotsc,0}_{m+n-2}\}

고윳값

\pm\sqrt{mn}

의 고유 벡터는

:

\sqrt n\sum_{i\in C_m} |i\rangle \pm \sqrt m\sum_{j\in C_n} |j\rangle

이다. (여기서

C_m, C_n \subseteq \operatorname V(\Gamma)

는 완전 이분 그래프의 꼭짓점 집합의 분할이다.)

5. 4. 순환 그래프

순환 그래프

\mathsf C_n

의 인접 행렬은 다음과 같다.

:

\mathsf C_n = \sum_{i = 0}^{n-1} (|i\rangle\langle i+1|+|i+1\rangle\langle i|)

(여기서

i \in \mathbb Z/(n)

으로 여긴다. 즉,

n\equiv 0

이다.)

그 스펙트럼은 다음과 같다.

:

\operatorname{Spec}\mathsf C_n = \left\{2 \cos \frac{2\pi i}n \colon i \in \{0,1,\dotsc,n-1\} \right\}

특히,

\pm2

가 아닌 모든 고윳값들의 중복수는 2이다. (

\pm2

의 중복수는 1이다.)

5. 5. 경로 그래프

''n''개의 꼭짓점을 갖는 경로 그래프

\mathsf P_n

의 인접 행렬은 다음과 같다.

:

\mathsf P_n = \sum_{i=1}^{n-1} (|i\rangle \langle i+1| + |i+1\rangle \langle i|)

그 스펙트럼은 다음과 같다.

:

\operatorname{Spec}\mathsf P_n = \left\{2 \cos \frac{\pi i}{n+1} \colon i \in \{1,\dotsc,n\}\right\}

특히, 만약

\lambda

가 스펙트럼에 속한다면

-\lambda

도 스펙트럼에 속한다. 모든 고윳값의 중복수는 1이다.

5. 6. 딘킨 도표

ADE형의 단순 리 대수

\mathfrak g

의 딘킨 도표는 그래프로 표현된다. 이 그래프의 인접행렬의 스펙트럼은 다음과 같은 형태를 가진다.

:

\left\{2 \cos \frac{(d_i-1)\pi}{\mathsf h(\mathfrak g)} \colon i\in\{1,\dotsc,\operatorname{rank}\mathfrak g\}\right\}

여기서

$\operatorname{rank}\mathfrak g$ 는 $\mathfrak g$ 의 계수( $\mathfrak g$ 의 최대 아벨 부분 리 대수의 차원 = 딘킨 도표의 꼭짓점의 수)이다.
$\mathsf h(\mathfrak g)$ 는 $\mathfrak g$ 의 콕서터 수이다.
$d_i$ 는 $\mathfrak g$ 의 딘킨 도표의 각 꼭짓점에 대응되는 차수들이다. 예를 들어, 리 대수 $\mathfrak d_n$ 의 경우 $d_i = 2,4,6,\dotsc,2n-2$ 이다.

참조

_[1] 서적 Algebraic Graph Theory Cambridge University Press
_[2] 논문 The determinant of the adjacency matrix of a graph
_[3] 논문 Strongly Regular Graphs with (−1, 1, 0) Adjacency Matrix Having Eigenvalue 3
_[4] 간행물 Expander graphs and codes https://books.google[...] American Mathematical Society 2003-12-18
_[5] 서적 Analyzing Social Networks SAGE
_[6] 서적 Networks Oxford University Press
_[7] 문서 Biggs
_[8] 서적 Spectra of Graphs Springer
_[9] 서적 Algebraic Graph Theory Springer
_[10] 논문 Matrices with Permanent Equal to One https://core.ac.uk/d[...]
_[11] 문서 Goodrich, Tamassia
_[12] 서적 Introduction to Algorithms MIT Press and McGraw-Hill
_[13] 논문 On the succinct representation of graphs
_[14] 웹사이트 Description of graph6 and sparse6 encodings http://cs.anu.edu.au[...] 2012-02-10
_[15] 서적 Algorithm Design and Applications Wiley
_[16] 서적 Algebraic Graph Theory Cambridge University Press
_[17] 논문 The determinant of the adjacency matrix of a graph
_[18] 논문 Strongly Regular Graphs with (−1, 1, 0) Adjacency Matrix Having Eigenvalue 3
_[19] 간행물 Expander graphs and codes https://books.google[...] American Mathematical Society 2003-12-18
_[20] 문서 Biggs
_[21] 서적 Algebraic Graph Theory Springer
_[22] 문서 Goodrich, Tamassia
_[23] 서적 Introduction to Algorithms MIT Press and McGraw-Hill
_[24] 논문 On the succinct representation of graphs
_[25] 웹사이트 Description of graph6 and sparse6 encodings http://cs.anu.edu.au[...]
_[26] 서적 Algorithm Design and Applications Wiley

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com