격자 그래프

1. 개요

격자 그래프는 정수 좌표를 갖는 평면의 점에 해당하는 그래프로, x, y 좌표가 특정 범위 내에 있으며, 두 꼭짓점 사이의 거리가 1일 때 간선으로 연결된다. 사각형, 삼각형, 하난 격자 그래프 등 다양한 유형이 있으며, 정수뿐만 아니라 실수로도 표현될 수 있고, 2차원 평면, 3차원 입체 또는 그 이상의 차원을 사용하기도 한다. 사각형 격자 그래프는 경로 그래프의 데카르트 곱이며, 이분 그래프의 특징을 갖는다. 격자 그래프는 그래프 마이너 이론과 이차원성 이론에서 중요한 역할을 한다.

2. 종류

격자 그래프는 정수뿐만 아니라 실수로도 표현 가능하며, 데카르트 좌표와 같은 2차원 평면뿐만 아니라 입체 3차원 또는 그 이상을 사용하기도 한다.

2.1. 사각형 격자 그래프

사각형 격자 그래프(또는 그리드 그래프)는 꼭짓점이 정수 좌표를 갖는 평면의 점에 해당하며, x 좌표는 1,...,n 범위, y 좌표는 1,...,m 범위 내에 있다. 두 꼭짓점은 해당 점 사이의 거리가 1일 때마다 간선으로 연결된다. 이는 축에 평행한 변을 가진 직사각형 내의 정수 점에 대한 단위 거리 그래프이다.

2.1.1. 성질

정사각형 격자 그래프는 두 경로 그래프의 그래프의 데카르트 곱으로 표현할 수 있다. 즉, n-1과 m-1개의 변을 가진 두 경로 그래프의 데카르트 곱이다. 경로 그래프는 중앙값 그래프이므로, 정사각형 격자 그래프 또한 중앙값 그래프이다. 모든 정사각형 격자 그래프는 이분 그래프이며, 이는 체스판 방식으로 정점을 칠하면 쉽게 확인할 수 있다.

경로 그래프는 1 x n 격자 그래프이다. 2 x 2 격자 그래프는 4-사이클이다.

모든 평면 그래프 H는 h × h 격자의 그래프 마이너인데, 여기서 $h\; =\; 2|V(H)|\; +\; 4|E(H)|$이다.

격자 그래프는 격자 제외 정리 때문에 그래프 마이너 이론에서 기본적인 객체이다. 또한 이차원성 이론에서 중요한 역할을 한다.

2.2. 삼각형 격자 그래프

삼각 격자 그래프는 삼각 격자에 해당하는 그래프이다.

2.3. 하난 격자 그래프

평면상 유한 점 집합에 대한 하난 격자 그래프는 집합의 각 점을 지나는 모든 수직선과 수평선의 교차점으로 얻은 격자에 의해 생성된다.

2.4. 기타

룩 그래프(체스 말인 룩이 체스판에서 할 수 있는 모든 합법적인 움직임을 나타내는 그래프)는 때때로 격자 그래프라고도 불리지만, 이 그래프는 여기서 설명하는 격자 그래프와 다르다. 페어리 체스 말인 와지르의 유효한 움직임은 사각형 격자 그래프를 형성한다.

3. 고차원 격자 그래프

이러한 격자 그리드는 정수뿐만 아니라 실수로도 표현 가능하며, 때로는 데카르트 좌표와 같은 2차원 평면뿐만 아니라 입체의 3차원 또는 그 이상을 사용하기도 한다.