정규 그래프

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

1. 개요
2. 정의
3. 성질
- 3.1. 존재
- 3.2. 대수적 성질
4. 특수한 경우
5. 예
6. 역사
7. 생성
참조

1. 개요

정규 그래프는 모든 꼭짓점이 동일한 차수를 갖는 그래프를 의미한다. k-정규 그래프는 모든 꼭짓점의 차수가 k인 그래프를 지칭하며, 특히 3-정규 그래프는 삼차 그래프 또는 큐빅 그래프라고 불린다. 정규 그래프는 연결성, 해밀턴 순환, 고유값, 인접 행렬 등 다양한 수학적 성질을 가지며, 그래프 이론에서 중요한 연구 대상이다. n개의 꼭짓점을 갖는 k-정규 그래프가 존재하기 위한 필요충분조건은 n ≥ k+1이고 nk가 짝수이다.

더 읽어볼만한 페이지

정규 그래프 - 페일리 그래프
페일리 그래프는 유한체와 제곱수를 기반으로 구성되며, 강하게 정규적이고 자기 여 그래프이며 해밀턴 순환 그래프이다.
정규 그래프 - 완전 그래프
완전 그래프는 그래프 내 모든 꼭짓점 쌍이 변으로 연결된 그래프로, 꼭짓점 수 n에 따라 K_n으로 표기되며 n(n-1)/2개의 변을 가지고, 사회 연결망 분석 등 다양한 분야에 응용된다.
그래프족 - 척도 없는 네트워크
척도 없는 네트워크는 네트워크 과학에서 연결 정도 분포가 멱법칙을 따르는, 즉 일부 허브 노드가 압도적으로 많은 연결을 가지는 불균등한 연결 구조를 가진 네트워크를 의미하며, 바라바시-앨버트 모델로 설명된다.
그래프족 - 선 그래프
선 그래프는 주어진 그래프의 변을 정점으로, 원래 그래프에서 인접한 변들 사이의 관계를 변으로 나타내어 변들의 인접 관계를 정점 간의 관계로 표현한 그래프이다.

정규 그래프
그래프 이론
용어	그래프 이론
정의
종류	모든 꼭짓점의 차수가 동일한 그래프
차수	각 꼭짓점이 가지는 이웃의 수
특징
k-정규 그래프	모든 꼭짓점의 차수가 k인 그래프
0-정규 그래프	고립된 꼭짓점으로만 이루어진 그래프
1-정규 그래프	고립된 변으로만 이루어진 그래프
2-정규 그래프	사이클 그래프의 분리 합집합
3-정규 그래프	3-정규 그래프 또는 삼차 그래프라고도 불림
속성
정규성	그래프의 모든 꼭짓점의 차수가 동일함
대칭성	정규 그래프는 vertex-transitive 그래프이지만, vertex-transitive 그래프가 항상 정규 그래프인 것은 아님
강한 정규 그래프	강한 정규 그래프는 특정 파라미터를 만족하는 정규 그래프임
관련 개념
완전 그래프	모든 꼭짓점이 서로 인접한 그래프 (정규 그래프의 특수한 경우)
큐빅 그래프	각 꼭짓점이 3개의 이웃을 가지는 그래프
이분 그래프	꼭짓점 집합을 두 개의 분리된 집합으로 나눌 수 있는 그래프

2. 정의

주어진 자연수 $k$ 에 대해, 어떤 그래프에서 모든 꼭짓점의 차수(꼭짓점에 잇닿은 변의 수)가 $k$ 라면, 이 그래프를 ''' $k$ -정규 그래프'''( $k$ -regular graph^영어)라고 한다.

3-정규 그래프는 '''삼차 그래프'''(cubic graph|큐빅 그래프^영어)라고도 한다.

3. 성질

Nash-Williams theorem|내시윌리엄스 정리^영어에 따르면, 2k+1개의 꼭짓점을 갖는 k-정규 그래프는 항상 해밀턴 순환을 갖는다. 3-정규 그래프의 최소 교차점 개수를 찾는 문제는 NP-난해이다.^[8] 핸드셰이킹 보조정리에 따르면, 홀수 k를 갖는 k-정규 그래프는 짝수 개의 정점을 갖는다.

3. 1. 존재

두 자연수

n,k

에 대해, 다음 두 조건은 서로 동치이다.

$n$ 개의 꼭짓점을 갖는 $k$ -정규 그래프가 존재한다.
$n\ge k+1$ 이며 $nk$ 는 짝수이다.

이는

n

차 정규 그래프가 존재하기 위한 필요충분조건이

n \geq k+1

이고

nk

가 짝수인 것과 같다.

이에 대한 증명은 다음과 같다. 완전 그래프는 서로 다른 모든 정점 쌍이 고유한 변으로 연결되어 있으므로, 변의 수는 완전 그래프에서 최대가 되며, 그 수는

\binom{n}{2} = \dfrac{n(n-1)}{2}

이고, 차수는

n-1

이다. 따라서

k=n-1,n=k+1

이다. 이는 특정

k

에 대한 최소

n

이다. 또한, 정규 그래프가 차수

n

을 가지면 변의 수는

\dfrac{nk}{2}

이므로

nk

는 짝수여야 한다.

이 경우, 순환 그래프에 적절한 매개변수를 고려하여 정규 그래프를 쉽게 구성할 수 있다.

3. 2. 대수적 성질

그래프의 인접 행렬을 ''A''라고 할 때, 그래프가 정규 그래프인 것과

\textbf{j}=(1, \dots ,1)

이 ''A''의 고유벡터인 것은 동치이다.^[2] 이때 고유값은 그래프의 상수 차수가 된다. 다른 고유값에 해당하는 고유벡터는

\textbf{j}

에 직교하므로, 이러한 고유벡터

v=(v_1,\dots,v_n)

에 대해

\sum_{i=1}^n v_i = 0

이 성립한다.

차수가 ''k''인 정규 그래프가 연결되어 있는 것과 고유값 ''k''의 중복도가 1인 것은 동치이다.^[2]

그래프가 연결 그래프이고 정규 그래프일 필요충분조건은

J_{ij}=1

인 일 행렬 ''J''가 그래프의 인접 행렬 대수(즉, ''A''의 거듭제곱의 선형 결합)에 있는 것이다.^[3]

''G''를 지름이 ''D''이고 인접 행렬의 고유값이

k=\lambda_0 >\lambda_1\geq \cdots\geq\lambda_{n-1}

인 ''k''-정규 그래프라고 하자. ''G''가 2부 그래프가 아니면, 다음이 성립한다.

:

D\leq \frac{\log{(n-1)}}{\log(\lambda_0/\lambda_1)}+1.

^[4]

4. 특수한 경우

0-정규 그래프는 무변 그래프이다. 1-정규 그래프의 연결 성분은 경로 그래프 $K_2=P_2$ 이다. 2-정규 그래프의 연결 성분은 순환 그래프나 무한 경로 그래프이다.

$n$ 개의 꼭짓점을 갖는 완전 그래프 $K_n$ 은 $n-1$ -정규 그래프이다.

차수가 최대 2인 정규 그래프는 분류하기 쉽다. 0-정규 그래프는 연결되지 않은 정점으로 구성되고, 1-정규 그래프는 연결되지 않은 모서리로 구성되며, 2-정규 그래프는 분리합의 사이클과 무한 체인으로 구성된다.

3-정규 그래프는 입방 그래프라고도 한다.

강하게 정규 그래프는 인접한 꼭짓점 쌍이 공통으로 l개의 이웃을 가지고, 인접하지 않은 꼭짓점 쌍이 공통으로 n개의 이웃을 가지는 정규 그래프이다. 정규 그래프이지만 강하게 정규 그래프가 아닌 가장 작은 그래프는 6개의 꼭짓점을 갖는 사이클 그래프와 순환 그래프이다.

완전 그래프

K_m

은 모든 m에 대해 강하게 정규적이다.

5. 예

0-정규 그래프는 무변 그래프이다. 1-정규 그래프의 연결 성분은 경로 그래프 K₂=P₂이다. 2-정규 그래프의 연결 성분은 순환 그래프나 무한 경로 그래프이다.

n개의 꼭짓점을 갖는 완전 그래프 Kₙ은 n-1-정규 그래프이다.

차수가 최대 2인 정규 그래프는 분류하기 쉽다. 0-정규 그래프는 연결되지 않은 정점으로 구성되고, 1-정규 그래프는 연결되지 않은 모서리로 구성되며, 2-정규 그래프는 분리합의 사이클과 무한 체인으로 구성된다.

6. 역사

1880년에 피터 거스리 테이트는 모든 삼차 그래프는 해밀턴 경로를 가진다는 추측을 내놓았지만, 1946년에 윌리엄 토머스 텃이 46개 꼭짓점을 가진 반례를 찾았다.

1971년에 윌리엄 토머스 텃은 모든 이분 삼차 그래프는 해밀턴 회로가 있을 것이라고 추측했지만, 조지프 호턴(Joseph Horton^영어)이 96개 꼭짓점을 가진 반례를 찾아냈다.

모든 이분 삼차 그래프가 해밀턴 회로가 짝수개 존재한다는 것은 증명되어 있다.

내시윌리엄스 정리는 영국의 수학자 크리스핀 내시윌리엄스(Crispin Nash-Williams^영어)가 증명하였다.

7. 생성

동형 사상을 고려하여, 주어진 차수와 정점 개수를 갖는 모든 정규 그래프를 생성하는 빠른 알고리즘이 존재한다.^[5] GenReg는 정규 그래프를 생성하는 소프트웨어이다.^[7]

참조

_[1] 서적 Graph Theory and its Engineering Applications https://archive.org/[...] World Scientific
_[2] 서적 Spectra of Graphs: Theory and Applications Wiley
_[3] 논문 Algebraic characterizations of graph regularity conditions
_[4] 문서 http://personal.plat[...] 2020-03
_[5] 간행물 Fast generation of regular graphs and construction of cages http://www.mathe2.un[...]
_[6] 서적 Spectra of Graphs: Theory and Applications Wiley
_[7] 웹사이트 Regular Graphs http://www.mathe2.un[...]
_[8] 저널 Crossing number is hard for cubic graphs

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

문의하기 : help@durumis.com