경로 그래프

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

1. 개요
2. 정의
- 2.1. 유한 경로 그래프
- 2.2. 무한 경로 그래프
3. 성질
4. 대수학적 표현
- 4.1. 딘킨 다이어그램
- 4.2. 근계 및 바일 군
참조

1. 개요

경로 그래프는 n개의 꼭짓점을 갖는 그래프이며, 무한 개의 꼭짓점을 갖는 무한 경로 그래프도 존재한다. 경로 그래프는 n개의 꼭짓점과 n-1개의 변을 가지며, 선 그래프는 크기가 1 작은 선 그래프이다. 경로 그래프의 색칠수는 꼭짓점의 개수에 따라 다르며, 나무를 이루므로 연결 그래프이다. 경로 그래프는 대수학에서 A형의 딘킨 다이어그램으로 표현되며, A형의 근계와 바일 군을 분류한다.

더 읽어볼만한 페이지

그래프 - 매케이 화살집
매케이 화살집은 유한군 G의 기약 표현을 꼭짓점으로, 텐서곱 분해를 통해 변을 정의하여 군의 표현론적 구조를 시각적으로 나타내는 도구이다.
그래프 - 완전 그래프
완전 그래프는 그래프 내 모든 꼭짓점 쌍이 변으로 연결된 그래프로, 꼭짓점 수 n에 따라 K_n으로 표기되며 n(n-1)/2개의 변을 가지고, 사회 연결망 분석 등 다양한 분야에 응용된다.

경로 그래프
그래프 정보
6개의 정점으로 이루어진 경로 그래프
정점 수	n
변 수	n − 1
자기 동형 사상 군 크기	2
지름	n − 1
반지름	⌊n/2⌋
색칠수	2
채색 지수	2
스펙트럼	{2cos(kπ/(n+1)); k=1,…,n}
속성
속성	단위 거리 그래프 이분 그래프 트리
표기법	Pn

2. 정의

'''경로 그래프''' $P_n$ 은 $n$ 개의 꼭짓점을 가지는 그래프이다.

: $V(P_n)=\{v_1,\dots,v_n\}$

경로 그래프의 변들은 다음과 같다.

: $v_iv_j\in E(P_n)\iff i=j\pm1\qquad(i,j=1,\dots,n)$

무한 경로 그래프 $P_\infty$ 는 가산 무한 개의 꼭짓점을 갖는다. 이를 편의상 정수의 집합으로 나타내면, 그 변들은 다음과 같다.

: $V(P_\infty)=\mathbb Z$

: $mn\in E(P_\infty)\iff m-n=\pm1\qquad(m,n\in\mathbb Z)$

2. 1. 유한 경로 그래프

'''경로 그래프'''

P_n

은

n

개의 꼭짓점을 가지는 그래프이다.

:

V(P_n)=\{v_1,\dots,v_n\}

경로 그래프의 변들은 다음과 같다.

:

v_iv_j\in E(P_n)\iff i=j\pm1\qquad(i,j=1,\dots,n)

2. 2. 무한 경로 그래프

무한 경로 그래프

P_\infty

는 가산 무한 개의 꼭짓점을 갖는다. 이를 편의상 정수의 집합으로 나타내면, 그 변들은 다음과 같다.

:

V(P_\infty)=\mathbb Z

:

mn\in E(P_\infty)\iff m-n=\pm1\qquad(m,n\in\mathbb Z)

3. 성질

경로 그래프 $P_n$ 은 $n$ 개의 꼭짓점과 $n-1$ 개의 변을 갖는다. 경로 그래프의 선 그래프는 크기가 1 작은 선 그래프이다.

: $L(P_n)=P_{n-1}\qquad(n>0)$

경로 그래프의 색칠수는 다음과 같다.

: $\chi(P_n)=\min\{2,n\}$

경로 그래프는 나무를 이루며, 따라서 연결 그래프이다.

3. 1. 기본 성질

경로 그래프

P_n

은

n

개의 꼭짓점과

n-1

개의 변을 갖는다. 경로 그래프의 선 그래프는 크기가 1 작은 선 그래프이다.

:

L(P_n)=P_{n-1}\qquad(n>0)

경로 그래프의 색칠수는 다음과 같다.

:

\chi(P_n)=\min\{2,n\}

경로 그래프는 나무를 이루며, 따라서 연결 그래프이다.

3. 2. 선 그래프

경로 그래프

P_n

은

n

개의 꼭짓점과

n-1

개의 변을 갖는다. 경로 그래프의 선 그래프는 크기가 1 작은 선 그래프이다.

:

L(P_n)=P_{n-1}\qquad(n>0)

3. 3. 색칠수

경로 그래프

P_n

의 색칠수는 다음과 같다.

:

\chi(P_n)=\min\{2,n\}

3. 4. 연결성

경로 그래프

P_n

은

n

개의 꼭짓점과

n-1

개의 변을 갖는다. 경로 그래프는 나무를 이루며, 따라서 연결 그래프이다. 경로 그래프의 색칠수는 다음과 같다.

:

\chi(P_n)=\min\{2,n\}

4. 대수학적 표현

4. 1. 딘킨 다이어그램

대수학에서, 경로 그래프는 A형의 Dyn킨 다이어그램으로 나타난다. 이처럼, 이들은 A형의 근계와, 대칭군인 A형의 바일 군을 분류한다.

4. 2. 근계 및 바일 군

대수학에서, 경로 그래프는 A형의 Dyn킨 다이어그램으로 나타난다. 이처럼, 이들은 A형의 근계와, 대칭군인 A형의 바일 군을 분류한다.

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

문의하기 : help@durumis.com