격자 그래프
1. 개요
격자 그래프는 정수 좌표를 갖는 평면의 점에 해당하는 그래프로, x, y 좌표가 특정 범위 내에 있으며, 두 꼭짓점 사이의 거리가 1일 때 간선으로 연결된다. 사각형, 삼각형, 하난 격자 그래프 등 다양한 유형이 있으며, 정수뿐만 아니라 실수로도 표현될 수 있고, 2차원 평면, 3차원 입체 또는 그 이상의 차원을 사용하기도 한다. 사각형 격자 그래프는 경로 그래프의 데카르트 곱이며, 이분 그래프의 특징을 갖는다. 격자 그래프는 그래프 마이너 이론과 이차원성 이론에서 중요한 역할을 한다.
| 종류 | 평면 그래프 |
|---|---|
| 특징 | 정규 그래프 케일리 그래프 거리-정규 그래프 완벽 그래프 대칭 그래프 |
이미지 준비중입니다.
이미지 준비중입니다.
| 꼭짓점 연결도 | n (n은 격자의 차원) |
|---|---|
| 변 연결도 | n (n은 격자의 차원) |
| 색칠수 | 2 (이분 그래프) |
| 대칭군 | 격자의 종류에 따라 다름 |
| 사용 분야 | 병렬 컴퓨팅 통신망 셀룰러 네트워크 물리적 모델 이산 공간 |
|---|
-
평면 그래프 -
다듬은 정육면체
깎은 정육면체는 정육면체의 꼭짓점을 잘라 만든 다면체로, 6개의 정팔각형과 8개의 정삼각형으로 구성되고, 마름모 입방팔면체 등과 연관되며, 데카르트 좌표계와 트리보나치 수열로 꼭짓점 위치를 나타낼 수 있고, 키랄성 및 팔면체 대칭성을 가지며 여러 분야에 활용됩니다. -
평면 그래프 -
정이십면체
정이십면체는 20개의 정삼각형 면으로 이루어진 볼록 정다면체로, 정반오각기둥 양쪽에 정오각뿔을 붙인 형태이며, 정십이면체와 쌍대 관계를 가지고 다양한 분야에서 활용된다. -
그래프족 -
척도 없는 네트워크
척도 없는 네트워크는 네트워크 과학에서 연결 정도 분포가 멱법칙을 따르는, 즉 일부 허브 노드가 압도적으로 많은 연결을 가지는 불균등한 연결 구조를 가진 네트워크를 의미하며, 바라바시-앨버트 모델로 설명된다. -
그래프족 -
정규 그래프
정규 그래프는 그래프 이론에서 모든 꼭짓점의 차수가 동일한 그래프를 의미하며, 각 꼭짓점이 k개의 변에 잇닿아 있는 그래프를 k-정규 그래프라고 하고, 여러 성질 및 다양한 분야에 응용된다. -
알고리즘 -
텍스트-비디오 모델
텍스트-비디오 모델은 텍스트 입력을 기반으로 비디오를 생성하는 인공지능 모델로서, 다양한 모델들이 개발되고 교육, 홍보, 창작 산업 등 여러 분야에 활용되지만 컴퓨팅 자원 소모, 데이터 부족, 텍스트 해석 오류, 윤리적 문제 등의 한계점을 가진다. -
알고리즘 -
마스터 정리
마스터 정리는 분할 정복 알고리즘의 시간 복잡도 분석 도구로서, 점화식을 세 가지 경우로 나누어 재귀 알고리즘의 효율성을 파악하고, 다양한 정렬 및 일반 알고리즘 분석에 활용되지만, 특정 조건에서는 적용이 제한될 수 있습니다.
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 격자의 그래프 마이너인데, 여기서 이다.
격자 그래프는 격자 제외 정리 때문에 그래프 마이너 이론에서 기본적인 객체이다. 또한 이차원성 이론에서 중요한 역할을 한다.