거리 정규 그래프

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

1. 개요
2. 교차 배열
3. 성질
- 3.1. 그래프 이론적 성질
- 3.2. 스펙트럼 성질
4. 예
5. 거리-정규 그래프의 분류
- 5.1. 3차 거리 정규 그래프
참조

1. 개요

거리 정규 그래프는 그래프 이론에서 사용되는 그래프의 한 종류이다. 그래프의 지름 d에 대해, 모든 거리 j (1 ≤ j ≤ d)에 있는 두 정점 u, v에 대해, v와의 거리가 j+1인 u의 이웃이 b_j개이고, v와의 거리가 j-1인 u의 이웃이 c_j개인 정수 배열 {b_0, b_1, ..., b_{d-1}; c_1, ..., c_d}가 존재하면, 해당 그래프는 거리 정규 그래프이다. 이 정수 배열을 교차 배열이라고 하며, 그래프의 교차수 a_j, b_j, c_j는 a_j + b_j + c_j = k를 만족한다. 거리 정규 그래프는 교차 배열을 가질 필요충분조건을 가지며, 완전 그래프, 순환 그래프, 홀 그래프 등이 예시로 존재한다. 3차 거리 정규 그래프는 완전히 분류되어 있으며, 13개의 고유한 그래프가 존재한다.

더 읽어볼만한 페이지

대수적 그래프 이론 - 중심성
중심성은 그래프 이론에서 네트워크 내 노드의 중요성을 평가하기 위한 지표로, 차수 중심성, 근접 중심성 등 다양한 종류가 있으며 네트워크 흐름, 워크 구조 등 다양한 특징에 따라 분류된다.
대수적 그래프 이론 - 대칭 그래프
대칭 그래프는 그래프 이론에서 그래프의 구조적 규칙성을 나타내는 개념으로, 정점과 간선의 연결 관계가 균일하며 사이클 그래프, 완전 그래프, 하이퍼큐브 그래프 등의 예시가 있고, 네트워크 분석, 암호학, 화학 등 다양한 분야에 응용된다.
정규 그래프 - 페일리 그래프
페일리 그래프는 유한체와 제곱수를 기반으로 구성되며, 강하게 정규적이고 자기 여 그래프이며 해밀턴 순환 그래프이다.
정규 그래프 - 완전 그래프
완전 그래프는 그래프 내 모든 꼭짓점 쌍이 변으로 연결된 그래프로, 꼭짓점 수 n에 따라 K_n으로 표기되며 n(n-1)/2개의 변을 가지고, 사회 연결망 분석 등 다양한 분야에 응용된다.
그래프족 - 척도 없는 네트워크
척도 없는 네트워크는 네트워크 과학에서 연결 정도 분포가 멱법칙을 따르는, 즉 일부 허브 노드가 압도적으로 많은 연결을 가지는 불균등한 연결 구조를 가진 네트워크를 의미하며, 바라바시-앨버트 모델로 설명된다.
그래프족 - 정규 그래프
정규 그래프는 그래프 이론에서 모든 꼭짓점의 차수가 동일한 그래프를 의미하며, 각 꼭짓점이 k개의 변에 잇닿아 있는 그래프를 k-정규 그래프라고 하고, 여러 성질 및 다양한 분야에 응용된다.

거리 정규 그래프

2. 교차 배열

거리 정규 그래프는 교차 배열이라는 정수 배열로 특징지어진다. 동일한 교차 배열을 갖는 두 연결 거리 정규 그래프는 코스펙트럴이다. 이는 두 그래프의 인접 행렬이 동일한 스펙트럼을 가질 때 성립한다.^[1]

거리 정규 그래프가 단절 그래프일 필요충분 조건은 코스펙트럴 거리 정규 그래프의 분리 합집합인 경우이다.^[1]

2. 1. 정의

직경

d

인 그래프

G

에 대해, 정수 배열

\{ b_0, b_1, \ldots, b_{d-1}; c_1, \ldots, c_d \}

이 존재하고, 모든

1 \leq j \leq d

와 거리가

j

인

G

의 꼭짓점 쌍

u

,

v

에 대해

v

와의 거리가

j+1

인

u

의 이웃이

b_j

개이고

v

와의 거리가

j - 1

인

u

의 이웃이

c_j

개일 때,

G

는 거리 정규 그래프이다. 거리 정규 그래프를 특징짓는 이 정수 배열을 '''교차 배열'''(intersection array)이라고 한다.

거리 정규 그래프의 '''교차 배열'''은

( b_0, b_1, \ldots, b_{d-1}; c_1, \ldots, c_d )

형태의 배열이다. 여기서

d

는 그래프의 지름이며, 각

1 \leq j \leq d

에 대해

b_j

는 거리

j+1

에 있는

v

의 이웃 중에서

u

의 이웃의 개수를,

c_j

는 거리

j - 1

에 있는

v

의 이웃 중에서

u

의 이웃의 개수를 나타낸다. 이는

u

와

v

가 거리

j

에 있는 임의의 두 정점 쌍에 대해 정의된다. 또한

a_j

는

v

로부터 거리

j

에 있는

u

의 이웃의 개수를 나타낸다.

a_j, b_j, c_j

는 그래프의 '''교차수'''라고 불린다. 이들은

a_j + b_j + c_j = k

라는 식을 만족하며, 여기서

k = b_0

는 임의의 정점의 차수, 즉 이웃의 개수이다.

지름이

d

인 그래프

G

가 거리 정규 그래프가 되는 필요충분조건은 위에 언급된 교차 배열을 갖는 것이다.

2. 2. 교차수

a_j, b_j, c_j

는 그래프의 교차수라고 불리며, 이들은

a_j + b_j + c_j = k

를 만족한다. 여기서

k = b_0

는 정점의 차수이다.^[1]

2. 3. 공스펙트럼 거리 정규 그래프

동일한 교차 배열을 갖는 두 연결 거리 정규 그래프는 공스펙트럼이다.^[1] 거리 정규 그래프의 연결은 공스펙트럼 거리 정규 그래프들의 서로소 합집합인 경우에만 끊어진다.^[1]

3. 성질

만약 $G$ 가 교차 배열 $( b_0, b_1, \ldots, b_{d-1}; c_1, \ldots, c_d )$ 를 갖는 차수 $k$ 의 연결된 거리 정규 그래프라고 가정하자. 각 $0 \leq j \leq d$ 에 대해, $k_j$ 를 주어진 정점으로부터 거리가 $k$ 인 정점의 개수로 하고, $G_{j}$ 를 $G$ 에서 거리가 $j$ 인 정점 쌍을 연결하여 형성된 인접 행렬 $A_j$ 를 갖는 $k_{j}$ -정규 그래프로 나타낸다.

3. 1. 그래프 이론적 성질

모든

0 \leq j < d

에 대해

\frac{k_{j+1}}{k_{j}} = \frac{b_{j}}{c_{j+1}}

이다. 여기서

k_j

는 주어진 정점으로부터 거리가

j

인 정점의 개수이다.^[1]

또한,

b_0 > b_1 \geq \cdots \geq b_{d-1} > 0

이고,

1 = c_1 \leq \cdots \leq c_d \leq b_0

이다.^[1]

3. 2. 스펙트럼 성질

$G$ 는 $d + 1$ 개의 서로 다른 고윳값을 갖는다.^[1]
$G$ 의 단순 고유값이 $\lambda$ 인 경우, $\lambda \in \{ \pm k \}$ 이다.^[1]
$G$ 가 완전 다분 그래프가 아닐 때, 모든 고윳값 중복도 $m > 1$ 에 대해 $k \leq \frac{1}{2} (m - 1)(m + 2)$ 이다.^[1]
$G$ 가 완전 다분 그래프가 아닐 때, 모든 고윳값 중복도 $m > 1$ 에 대해 $d \leq 3m - 4$ 이다.^[1]
$G$ 가 강한 정규 그래프인 경우, $n \leq 4m - 1$ 이고 $k \leq 2m - 1$ 이다.^[1]

4. 예

완전 그래프
순환 그래프
홀 그래프
무어 그래프
웰스 그래프와 실베스터 그래프
직경 2의 강한 정규 그래프

종수 3의 유향 표면에 포함된 7차 클라인 그래프 및 관련 지도. 이 그래프는 교차 배열 {7,4,1;1,2,7} 및 자기동형군 PGL(2,7)을 갖는 거리 정규 그래프이다.

5. 거리-정규 그래프의 분류

주어진 차수 k > 2에 대해, 서로 다른 연결된 거리 정규 그래프는 유한 개만 존재한다.^[3]^[1]

마찬가지로, 완전 다분 그래프를 제외하면 주어진 고유값 중복도 m > 2에 대해, 서로 다른 연결된 거리 정규 그래프는 유한 개만 존재한다.^[4]^[2]

5. 1. 3차 거리 정규 그래프

3차 거리 정규 그래프는 완전히 분류되었다.

13개의 고유한 3차 거리 정규 그래프는 다음과 같다. K₄ (또는 사면체 그래프), K_3,3, 페테르센 그래프, 정육면체 그래프, 헤우드 그래프, 파푸스 그래프, 콕서터 그래프, 텃-콕서터 그래프, 정십이면체 그래프, 데자르그 그래프, 텃 12-케이지, 빅스–스미스 그래프, 포스터 그래프.

참조

_[1] 논문 There are only finitely many distance-regular graphs of fixed valency greater than two 2015-01-10
_[2] 논문 Bounding the diameter of distance-regular graphs 1988-12-01
_[3] 논문 There are only finitely many distance-regular graphs of fixed valency greater than two
_[4] 논문 Bounding the diameter of distance-regular graphs

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

문의하기 : help@durumis.com