비숍 그래프

이 문서는 확인을 위해 추가 인용이 필요합니다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 기사를 개선할 수 있도록 도와주시기 바랍니다. 소스가 없는 재료는 문제가 발생하여 제거될 수 있습니다.출처 찾기: "Bishop's graph" – 뉴스, 신문, 책, 학자, JSTOR (2022년 11월) (이 템플릿 메시지를 제거하는 방법 및 시기 알아보기)

수학에서, 비숍 그래프(bishop's graph)는 체스 판 위의 비숍의 모든 법적 움직임을 나타내는 그래프입니다.각 꼭짓점은 체스판의 정사각형을 나타내고 각 모서리는 주교의 법적 움직임을 나타냅니다. 즉, 두 꼭짓점 사이에는 공통 대각선을 차지하는 모서리가 있습니다.체스판의 $치수$가${\displaystyle }$m ×$$ {\$displaystyle$ m$\times$n$\}$이면 유도 그래프를${\displaystyle }m{\displaystyle }$ ×$$ \$displaystyle$ m$\times$ n$}$ 비숍 그래프라고 합니다.

특성.

체스판에 빨간색과 검은색 두 가지 색의 정사각형이 있고, 수평 또는 수직으로 인접한 정사각형이 반대 색을 가지고 있다는 사실은 주교의 그래프가 두 개의 연결된 구성 요소를 가지고 있다는 것을 의미합니다. 그 꼭짓점 집합은 각각 빨간색과 검은색 정사각형입니다.그 이유는 주교의 대각선 움직임은 그것이 색깔을 바꾸는 것을 허용하지 않지만, 하나 이상의 움직임에 의해 주교는 어떤 정사각형에서 같은 색의 다른 정사각형으로 얻을 수 있기 때문입니다.보드의 변 길이가 짝수인 경우 두 구성 요소는 동형이지만 양쪽이 홀수인 경우에는 동형이 아닙니다.

원래 보드가 사각형이고 변의 길이가 홀수인 경우 주교 그래프의 구성 요소는 다이아몬드에 있는 루크 그래프로 처리될 수 있습니다. 왜냐하면 빨간색 사각형(예:)이 45도 회전하면 주교의 움직임이 루크의 움직임과 마찬가지로 수평 및 수직이 되기 때문입니다.

지배

광장은 주교가 정확히 한 번의 움직임으로 그 광장에 도달할 수 있다면 주교의 공격을 받는다고 합니다.지배적인 세트는 모든 광장이 그 주교들 중 한 명에 의해 공격받거나 점령되도록 하는 주교들의 배열입니다.독립적인 지배 집합은 어떤 주교도 다른 주교를 공격하지 않는 지배 집합입니다.정사각형의 측판을 지배하는 데 필요한 최소 주교 수는 정확히 n명이며, 이는 독립적인 지배 집합을 형성할 수 있는 최소 주교 수이기도 합니다.대조적으로, 주교들이 차지하는 모든 광장이 주교들 중 한 명에 의해 공격받는 지배적인 집합인, 전체 지배적인 집합은 더 많은 주교들을 필요로 합니다; 측면 3의 정사각형 판에서, 전체 지배적인 집합의 최소 $크기$는 2 ${\displaystyle \lceil }$ ${\displaystyle 2}$(${\displaystyle \mathrm{n}}$-${\displaystyle }$1 ) / 3$⌉,$ \$displaystyle 2$ $(n-1)/3,$최소$$ 우세 ^[1][2]집합보다 약 1/3 더 큽니다.

레퍼런스