래더 그래프

래더 그래프
사다리 그래프 L8.
정점	2n
가장자리	3n-2
색수	2
색도 지수	3 for n>2 2 for n=2 n=1에 1
특성.	단위 거리 해밀턴어 플라나르 양립자
표기법	Ln
그래프 및 모수 표

그래프 이론의 수학적 분야에서 래더 그래프_n L은 2n 정점과 3n-2 가장자리를 가진 평면형 비방향 그래프다.^[1]

래더 그래프는 두 개의 경로 그래프의 데카르트 산물로 얻을 수 있으며, 그 중 하나는 하나의 에지만 있다.L_n,1 = P_n × P₂.^[2][3]

특성.

시공으로 보면, 사다리 그래프 L은_n 격자 그래프 G와_2,n 이형성이며, nrungs가 있는 사다리처럼 보인다.둘레 4(만약 n>1)와 색지수 3(만약 n>2)의 해밀턴식이다.

래더 그래프의 색수는 ${\displaystyle 2}$이고 ${\displaystyle {}^{}}$도 다항식은 (${\displaystyle x}$- 1${\displaystyle }$) x${\displaystyle }$( ${\displaystyle x^{}{}^{}}$- ${\displaystyle 3}$ ${\displaystyle x}$+ ${\displaystyle 3{}^{}}$)${\displaystyle {}^{}}$( ${\displaystyle {\mathrm{n}}^{}}$- 1${\displaystyle {}^{}}$) ${\$2}-3x+3)^{{$n-1$)}}}}}}}}{(n-1$)\}\}\}\}\}\}.$

• 

  사다리 그래프의 색수는 2이다.

래더 렁 그래프

때때로 "사다리 그래프"라는 용어는 n × P₂ 래더 렁 그래프에 사용되는데, 이것은 경로 그래프 P의₂ n개의 복사본의 그래프 조합이다.

원형 래더 그래프

원형 래더 그래프 CL은_n 4개의 2도 정점을 직선으로 연결하거나 길이 n³과 가장자리 주기의 데카르트 제품으로 구성할 수 있다.^[4]기호에서는 CL_n = C_n × P₂. 2n 노드와 3n 에지를 가지고 있다.사다리 그래프처럼 연결돼 있고 평면과 해밀턴이 있지만, n이 짝수일 경우에만 초당적이다.

원형 사다리 그래프는 프리즘의 다면형 그래프여서 더 흔히 프리즘 그래프라고 부른다.

원형 래더 그래프:

CL3

CL4

CL5

CL6

CL7

CL8

뫼비우스 사다리

2도 정점 4개를 교차하여 연결하면 뫼비우스 사다리라는 입방 그래프가 생성된다.

참조