룩 그래프

룩 그래프
8x8 룩 그래프
꼭지점	nm
가장자리	nm(n + m)/2 − nm
직경	2
둘레	3 (max(n, m) 3 3)
색수	최대(n, m)
스펙트럼	{m + n − 2, m − 2, n − 2, −2}
특성.	일체형 완벽하다 규칙적인. 정점 전이성의 잘 덮인
그래프 및 매개 변수 표

그래프 이론에서, 룩의 그래프는 체스판에 있는 룩 체스 피스의 모든 법적 움직임을 나타내는 그래프입니다.룩 그래프의 각 정점은 체스판의 정사각형을 나타내며, 각 모서리는 같은 행(랭크) 또는 같은 열(파일)의 두 정사각형을 서로 연결하는데, 이는 룩이 이동할 수 있는 정사각형을 나타냅니다.이러한 그래프는 직사각형 모양의 체스판을 위해 구성될 수 있으며, 수학적으로 두 개의 완전한 그래프의 데카르트 곱, 2차원 해밍 그래프 또는 완전한 초당 그래프의 선 그래프로 정의할 수 있습니다.

Rook의 그래프는 모든 정점을 다른 정점으로 이동시키는 대칭을 가지고 있어 매우 대칭적입니다.정사각형 체스판에서 정의된 룩의 그래프에서는 두 모서리마다 대칭이며, 모든 정점 쌍은 같은 거리에 있는 다른 모든 쌍과 대칭입니다(거리 추이적입니다).비교적 소수 치수의 체스판의 경우 순환 그래프입니다.한 가지 예외를 제외하고, 각 모서리가 속한 삼각형의 수와 각 인접하지 않은 정점 쌍을 연결하는 4주기의 존재로 다른 모든 그래프와 구별할 수 있다.

Rook의 그래프는 완벽한 그래프입니다. 즉, 체스판 정사각형의 모든 부분 집합이 색칠되어 행 또는 열의 두 정사각형이 같은 색을 가지지 않도록 색칠할 수 있고 색칠의 수가 단일 행 또는 열의 부분 집합의 최대 제곱 수(유도된 하위 그래프의 클리크 수)와 같아집니다.룩의 그래프에서 정사각형 부분 집합에서 이러한 방식으로 형성된 그래프는 모든 완벽한 그래프를 특징짓는 강력한 완벽한 그래프 정리를 증명하는 데 사용되는 완벽한 그래프 분해의 핵심 요소 중 하나를 형성한다.루크의 그래프의 독립 번호와 지배 번호, 또는 그들이 서로 공격하지 않도록 배치될 수 있는 루크의 최대 수, 또는 그들이 체스판의 2차원 중 작은 것과 같으며, 이것들은 공격하지 않는 것을 의미하는 잘 커버된 그래프이다.한 번에 1개씩 최대 사이즈에 도달할 때까지 고정되지 않습니다.

정의 및 수학적 구성

n × m 루크의 그래프는 n × m 체스판의 ^[1]루크의 움직임을 나타낸다.정점은 체스판의 정사각형을 나타내며 좌표(x, y)가 주어질 수 있다. 여기서 1 x x and n과 1 y y m m이다.좌표(x₁, y₁)와 (x₂,y₂)를 가진 두 정점은 x = x₂(두 정사각형은 체스판의 동일한 파일에 속하고 수직 루크 이동에 의해 연결됨) 또는₁ y₂ = y(두 정사각형은 동일한 순위에 속하며 ^[1]수평 이동에 의해 연결됨)인₁ 경우에만 인접합니다.

체스판의 단일 순위 또는 단일 파일 내에서, 모든 정사각형은 서로 도달할 수 있으므로, 이러한 정사각형은 완전한 그래프를 형성하는 정점의 부분 집합인 클리크를 형성합니다.n × m 체스판에 대한 전체 룩의 그래프는 그래프_n K_m ◻ K의 데카르트 곱으로 이 두 종류의 패를 형성할 수 있다. 정사각형 체스판에 대한 룩의 그래프는 동일한 크기의 패의 데카르트 곱이기 때문에, 해밍 그래프의 한 예이다.해밍 그래프로서의 치수는 2이고, 모든 2차원 해밍 그래프는 정사각형 체스판의 ^[2]루크 그래프입니다.정사각형 체스판 그래프는 라틴 정사각형의 정사각형을 나타내며 모서리는 같은 ^[3]값을 포함할 수 없는 정사각형의 쌍을 나타내기 때문에 라틴 정사각형의 그래프라고도 합니다.스도쿠 그래프는 ^[4]값이 일정하지 않은 스도쿠 퍼즐의 정사각형을 연결하는 추가 모서리가 있는 루크의 그래프입니다.

기하학적으로, Rook의 그래프는 볼록 폴리토프 계열의 정점과 가장자리(골격)의 집합으로 형성될 수 있다. 즉, 인접한 폴리토프 ^[5]쌍의 데카르트 곱이다.예를 들어 3-3 듀오프리즘은 2개의 삼각형의 데카르트 곱으로 형성된 4차원 도형으로 3×3 룩의 그래프를 ^[6]골격으로 한다.

규칙성과 대칭성

규칙성이 강하다

Moon(1963년)과 Hoffman(1964년)은 $m{\displaystyle }$×$$ {\$displaystyle m\times$ n$$$}$ look의 그래프가 다음 특성을 모두 갖는 것을 관찰했다.

• $여기$에는${\displaystyle m}$× n$체스$ 보드의 각 정사각형에 하나씩$, m개$의 $정점$이 $있습니다.$각 정점은 m${\displaystyle }$+${\displaystyle n}$ - $({displaystyle$ m$+n-2}$개$$ 모서리에 $인접$하여 동일한 등급의 $m{\displaystyle }$-$$({$displaystyle m-1}$개$$) 정사각형과 같은 파일의${\displaystyle }$n -$$({$displaystyle n-1}$개$$) $정사각형$에 연결됩니다.
• 룩 그래프 내의 삼각형은 단일 순위 또는 파일 내의 세 개의 정사각형으로 구성됩니다.$m{\displaystyle n}$n { $displaystyle$m \ $neq$ n$\}$일 때, 정확히 ${\displaystyle \genfrac{}{}{0ex}{}{\mathrm{n}}{}}$( m${\displaystyle 2\genfrac{}{}{0ex}{}{}{}}$) { $displaystyle$ n { \ $tbinom${$m$} {2}$$엣지$$(같은 랭크에서 정사각형을 연결하는 것)는${\displaystyle }$m -$$ { $displaystyle m-2}$개의$$ $삼각형$에 속하고 $나머지{\displaystyle }$m (${\displaystyle \genfrac{}{}{0ex}{}{\mathrm{n}}{}}$ 2$$) \ $displaystyle$ m {\$tbin$ {\ tbin {\n} {\n}$개$의 정사각형을 연결하는 것$(같은$ 정사각형을 연결하는 것)은 같은 정사각형을 연결하는 것) 에지에 속합니다.파일)은 n${\displaystyle }$- $(\displaystyle$ n-2$$$)$ $삼각형$에 속합니다.m ${\displaystyle =}$ {\$displaystyle m=$n$\}$인 경우, 각 에지는${\displaystyle }$m - ${\displaystyle 2}$ $=$n -$$ {\$displaystyle m-2=$n-2}개의$$ $삼각형$에 속합니다.
• 서로 인접하지 않은 두 정점은 각각 고유한 $(\displaystyle$4)-vertex 사이클에 속하며, 동일한 두 등급과 파일의 조합을 사용하는 다른 두 정점을 통해 서로 연결됩니다.

m ${\displaystyle =}$ ${\displaystyle n}$ ${\displaystyle =}$ {\$displaystyle$ m$=n=4$ $경우$를 제외하고 이러한 속성은 룩의 그래프를 고유하게 특징짓습니다.즉, 룩의 그래프는 이러한 수의 정점, 모서리, 모서리당 삼각형이 있고 두 개의 비인접 ^[7][8]정점을 통과하는 고유한 4주기를 가진 유일한 그래프입니다.

m ${\displaystyle =}$ {$displaystyle$ m$=n$인 $경우{\displaystyle }$ n${\displaystyle }$×$$ {$displaystyle$ n$\times$ n$}$rook의$$ 그래프는 ${\displaystyle {}^{}}$ ${\displaystyle \mathrm{srg}(}$ ( n${\displaystyle {}^{}2}$, 2${\displaystyle n}$ -${\displaystyle 2}$,${\displaystyle }$2 $){display \operatorname {srg}$ ( $n^$ {$2},$2 -$n$ - 2 - 2 )Times$$$}$인 강력한 정규 그래프라고 기재함으로써 이러한 조건을 생략할 수 있습니다$.$각각 정점당 모서리 수,^[1] 모서리당 삼각형 수 및 두 개의 비정점 공유 네이버 수.반대로 이들 파라미터를 가진 모든 강력한 정규 그래프는 n${\displaystyle }$${\displaystyle =}$ \ $displaystyle$ n$$$=$4$$^[7][8]\ $displaystyle{\displaystyle }$ n $=$ 4 를 $제외$하고 n ×$$ \ $times$ n } look 그래프여야 합니다.

n ${\displaystyle =}$ ${\displaystyle 4}${\$displaystyle$ n$=4$일 때, 4${\displaystyle }$×$$ {\$displaystyle$ 4$\times$4} look의 ^[9]$그래프$와 동일한 매개 변수를 가진 다른 강력한 규칙 그래프인 Shrikhande 그래프가 있습니다.Shrikhande 그래프는 Moon과 Moser가 나열한 것과 동일한 속성을 따릅니다.이는 Shrikhande 그래프의 각 정점 근방이 연결되어 6$(\displaystyle$ 6$)$ 사이클을 형성한다는 점에서 $(\displaystyle$ 4$\times$4) 루크의$$ 그래프와 구별할 수 있습니다.$이$와는${\displaystyle \mathrm{대조적}}$으로$$4 × 4 { $style$4 \ $times$ 4$$} rook$$ 그래프에서는 각 정점의 근방은 2개의 삼각형을 형성합니다.각 정점의 근방은 그 랭크와 파일에 대해 각각1개의 삼각형을 형성합니다.근처의 한쪽에서 ^[10]다른 쪽으로의 가장자리는 형성되지 않습니다.$4{\displaystyle \mathrm{}}$×$루크$의 그래프와 Shrikhande $그래프$를 구별하는 또 다른 방법은 n ${\displaystyle =}$ 4 ($style$$$n$=$ 루크의$$ 그래프는 4개의 클리(체스보드의 $4개$의 랭크 또는 $4개$의 파일)^[9]로 커버할 수 있는 반면, 쉬리칸데 그래프를 커버하려면 6개의 클리크가 필요합니다.

대칭

Rook의 그래프는 정점 추이적이고${\displaystyle }$(${\displaystyle m}$ ${\displaystyle +n}$ - ${\displaystyle 2}$)$({displaystyle (m+n-2)}$ - 규칙적이다. 이러한 방식으로 표준 ^[11]체스 피스의 움직임으로 형성된 유일한 규칙적인 그래프이다.$m{\displaystyle n}$n \ $displaystyle$m \ $neq$ n$,$ 、 Rook areries대칭은 그래프의 행과 열을 독립적으로 허용함으로써 형성되므로 그래프의 자기동형성 $그룹$에는 m${\displaystyle !}$ $!\$ $displaystyle$ m!$n!$$}$개의$$ 요소m ${\displaystyle =}$ {\$displaystyle$ m$=n$일 때 그래프에는 행과 열을 교환하는 추가 대칭이 있으므로 자기동형 $개수$는 ${\displaystyle \mathrm{2n}{}^{}}$\$displaystyle$$2n$!$^{2$^[12]

룩 그래프에 있는 두 꼭지점은 각각 인접 또는 비인접 여부에 따라 서로 1 또는 2의 거리에 있습니다.두 개의 비인접 정점은 그래프의 대칭에 의해 다른 두 개의 비인접 정점으로 변환할 수 있다.룩의 그래프가 정사각형이 아닐 경우 인접한 정점 쌍은 수평 또는 수직에 인접한 정점 쌍에 따라 대칭 그룹의 두 궤도로 떨어집니다. 그러나 그래프가 정사각형이 될 경우 인접한 두 정점도 대칭에 의해 서로 매핑될 수 있으므로 그래프는 거리 ^[13]추이적입니다.

m$${$displaystyle$ m$}$ $및$ n {$displaystyle$ n$}$이 비교적 소수일 $때{\displaystyle }$, 룩 그래프의 대칭 $그룹{\displaystyle {}_{}}$ $S{\displaystyle {}_{}}$${\displaystyle {}_{}}$m × ${\displaystyle {}_{}}$ { $displaystyle S_{m}\times$ S_${n$$}$은 $C_times$ C_n $= C$ $×$ $C_n$ { $displaystyle$ C_{$m$} {n} {n} {$n}$ {timesclassesclashesclook}의$$ 서브그룹을 포함합니다.${\displaystyle$ mn$}$개의$$ 정점이므로 이 경우 룩 그래프는 순환 ^[14]그래프입니다.

스퀘어 룩의 그래프는 연결 동종이며, 이는 연결된 두 개의 유도 하위 그래프 사이의 모든 동형성을 전체 ^[15]그래프의 자기 동형으로 확장할 수 있음을 의미한다.

기타 속성

완벽.

룩의 그래프는 완전한 초당 그래프_n,m K의 선 그래프로 볼 수도 있습니다.즉, 완전한 초당 그래프의 대응하는 에지가 공통의 ^[16]엔드포인트를 공유하는 경우에만 K의 각_n,m 에지에 대해 하나의 정점이 있고 룩의 그래프의 두 정점이 인접해 있습니다.이 뷰에서 양분 중 한쪽의 ih 정점에서 다른 한쪽의 j 정점까지의 완전 양분 그래프의 가장자리는 좌표(i, j)^[1]를 가진 체스판 정사각형에 대응한다.

임의의 초당 그래프는 완전한 초당 그래프의 서브 그래프이며, 이에 대응하여 초당 그래프의 선 그래프는 룩 ^[17]그래프의 유도 서브 그래프이다.초당 그래프의 선 그래프는 완벽합니다. 그 그래프와 유도된 하위 그래프에서, 어떤 정점 색채에 필요한 색상의 수는 가장 큰 전체 하위 그래프에서 정점의 수와 동일합니다.초당 그래프의 선 그래프는 완벽한 그래프의 중요한 패밀리를 형성한다. 추드노프스키 등이 사용한 소수의 패밀리 중 하나이다. (2006) 완벽한 그래프를 특성화하고 홀수 구멍과 홀수 방지 구멍이 없는 모든 그래프가 ^[18]완벽하다는 것을 보여준다.특히 루크의 그래프 자체는 완벽하다.

루크의 그래프는 완벽하기 때문에, 그래프의 어떤 색에도 필요한 색상의 수는 루크의 가장 큰 집단 크기입니다.룩 그래프의 클리프는 단일 행 또는 단일 열의 부분 집합이며, 이 중 가장 큰 것은 최대 크기(m, n)이므로 그래프의 색수이기도 합니다.n × n 룩 그래프의 n-컬러는 라틴 사각형으로 해석할 수 있다. n × n 그리드의 행과 열을 n개의 다른 값으로 채우는 방법을 기술하여 동일한 값이 행 또는 ^[19]열에 두 번 나타나지 않도록 한다.룩 그래프의 최적 색상을 찾는 것은 간단하지만 부분 색상을 그래프 전체의 색상으로 확장할 수 있는지 여부를 결정하는 것은 NP-완료입니다(이 문제를 프리컬러링 익스텐션이라고 부릅니다.마찬가지로 부분 라틴 정사각형을 완전한 라틴 ^[20]정사각형으로 완성할 수 있는지 여부를 결정하는 것은 NP-완전입니다.

인디펜던스

루크의 그래프에서 독립된 세트는 정점의 집합으로, 두 개가 그래프의 동일한 행 또는 열에 속하지 않습니다. 체스 용어로는 두 개가 서로 공격하지 않는 루크의 배치에 해당합니다.완전한 그래프는 또한 유도된 모든 하위 그래프에서 가장 큰 독립 집합의 크기가 그래프 정점의 최소 개수의 분할에 있는 클리 수와 동일한 그래프로 설명될 수 있다.룩 그래프에서는 행 집합 또는 열 집합(둘 중 더 적은 집합)이 이러한 최적 파티션을 형성합니다.따라서 그래프에서 가장 큰 독립 집합의 크기는 최소(m, n)^[1]입니다.루크 그래프의 모든 최적 색상의 모든 색상 클래스는 최대 독립 집합입니다.

Rook의 그래프는 충분히 커버된 그래프입니다.Rook의 그래프에 있는 모든 독립 세트는 최대 독립 세트까지 확장할 수 있으며, Rook의 그래프에 있는 모든 독립 세트는 동일한 크기인 min(m,^[21] n)을 가집니다.

지배

그래프의 도미네이션 번호는 모든 지배 세트 중 최소 카디널리티입니다.루크의 그래프에서 정점 집합은 해당 정사각형이 m × n 보드의 모든 정사각형을 점유하거나 루크가 이동하는 경우에만 지배적인 집합이다.m × n 보드의 경우 지배 번호는 min(m, n)입니다.^[22]

루크의 그래프에서 k-지배 집합은 대응하는 정사각형이 (루크의 이동을 통해) 다른 모든 정사각형을 최소 k회 공격하는 정점 집합이다.룩의 그래프에서 k-튜플 지배 세트는 대응하는 정사각형이 다른 모든 정사각형을 k회 이상 공격하고 그 자체가 k - 1회 이상 공격되는 정점 집합이다.모든 k-지배적 및 k-튜플 지배적 집합 중 최소 카디널리티는 각각 k-지배적 번호와 k-튜플 지배적 번호이다.정사각형 기판 및 짝수 k에서는 n even (k² - 2k)/4 및 k < 2n일 때 k-domination number는 nk/2이다.마찬가지로 k가 홀수이고 2n ^[23]미만일 때 k-튜플 지배수는 n(k+1)/2이다.

스펙트럼

룩 그래프의 스펙트럼(인접 행렬의 고유값)은 4개의 $고유값{\displaystyle }$m + $({displaystyle$ m$+n-2$${\displaystyle }m{\displaystyle }$ -$$({$displaystyle m-2$ $n{\displaystyle }$-$$$({displaystyle$ $n-2$$\})$로 구성됩니다.이러한 값은 모두 정수이므로 룩의 그래프는 적분 그래프입니다.4개의 고유값 중$$1개가 2(\$displaystyle$-2$)$인${\displaystyle }$4개의 고유값을 가질 수 있는 그래프 클래스는 3개(및 많은 예외 그래프)뿐이며, 3개의 클래스 중 하나는 rook의 그래프 클래스입니다.m$${\$displaystyle$ m$}$과 n$${\$displaystyle$ n$\}$의 대부분의 조합에서 $m{\displaystyle }$×$$ {\$displaystyle$ m$\times$ n$}$ look의 그래프는 스펙트럼이 같은 그래프는 없습니다.특히 n ${\displaystyle =}$ $({displaystyle$ n${\displaystyle =}2$})$$${\displaystyle \mathrm{또는}}$ n${\displaystyle }$=$$ - 1({$displaystyle$ n$=m-1$ $또는{\displaystyle }$ 두 $숫자{\displaystyle }$m({$displaystyle$ n$})$의 합계가 18 이상이고 2 ${\displaystyle {t\mathrm{}}^{}}$ 2${\displaystyle {}^{}}$±$$({$displaystyle 2t^2}\pm$ t$\})$^[24]의 형식이 아닐 때 해당됩니다.

「 」를 참조해 주세요.

• 킹스 그래프, 나이트 그래프, 퀸스 그래프, 체스 피스의 움직임에서 정의된 다른 세 개의 그래프
• 격자 그래프, 체스판의 정사각형 수평 및 수직 인접 그래프

레퍼런스

외부 링크

• Weisstein, Eric W., "Lattice Graph", MathWorld