인접성 (Adjacency)
1. 개요
인접성(Adjacency)이란 수학 및 컴퓨터 과학에서 두 개의 객체 사이에 직접적인 연결 관계가 존재하거나, 정의된 위상/거리 체계 내에서 최소 단위의 근접성을 가지는 상태를 의미한다. 이는 단순히 물리적인 거리를 측정하는 것을 넘어, 그래프 이론에서는 정점 간의 연결 관계로, 위상수학에서는 근방(Neighborhood)의 개념으로, 디지털 영상 처리에서는 픽셀 간의 공유 경계로 정의되는 추상적 개념이다.
2. 그래프 이론에서의 인접성
그래프 이론에서 인접성은 정점(Vertex, 노드)들 사이의 관계를 정의하는 핵심 개념이다.
2.1 정의
그래프 $G = (V, E)$에서 두 정점 $u, v \in V$가 간선 $e = (u, v) \in E$로 연결되어 있을 때, 두 정점 $u$와 $v$는 인접하다(Adjacent)고 말한다. 이때 간선 $e$는 두 정점을 잇는 직접적인 경로가 된다.
2.2 인접성과 부합성(Incidence)의 차이
인접성과 혼동하기 쉬운 개념으로 부합성(Incidence)이 있다. 두 개념의 결정적인 차이는 관계를 맺는 대상의 종류에 있다.
- 인접성(Adjacency): 정점과 정점 사이의 관계. (예: 정점 A와 정점 B가 간선으로 연결됨 $\rightarrow$ A와 B는 인접함)
- 부합성(Incidence): 정점과 간선 사이의 관계. (예: 정점 A가 간선 $e$의 끝점임 $\rightarrow$ 정점 A와 간선 $e$는 부합함)
2.3 인접성 표현 방식 및 복잡도 비교
그래프의 인접 관계를 컴퓨터 메모리에 저장하는 방식은 크게 인접 행렬과 인접 리스트로 나뉜다.
| 구분 |
인접 행렬 (Adjacency Matrix) |
인접 리스트 (Adjacency List) |
| 정의 |
$V \times V$ 크기의 2차원 배열로 표현 |
각 정점마다 연결된 정점들의 목록을 저장 |
| 공간 복잡도 |
$O(V^2)$ |
$O(V + E)$ |
| 연결 확인 시간 |
$O(1)$ (상수 시간) |
$O(\text{degree}(v))$ (정점의 차수만큼 탐색) |
| 특징 |
밀집 그래프(Dense Graph)에 유리 |
희소 그래프(Sparse Graph)에 유리 |
[표현 예시]
정점 {0, 1, 2}가 있고 간선 {(0,1), (0,2)}가 존재하는 그래프의 경우:
- 인접 행렬:
$$\begin{pmatrix} 0 & 1 & 1 \\ 1 & 0 & 0 \\ 1 & 0 & 0 \end{pmatrix}$$
- 인접 리스트:
- 0: [1, 2]
- 1: [0]
- 2: [0]
3. 위상수학적 인접성과 근방
위상수학에서는 거리(Metric)라는 수치 대신 '집합'의 포함 관계로 인접성을 정의한다. 이를 통해 구체적인 거리 개념이 없더라도 '가까움'을 정의하기 위해 근방(Neighborhood) 개념을 사용한다.
3.1 근방과 개집합
위상 공간 $X$의 한 점 $p$의 근방이란, $p$를 포함하는 어떤 개집합(Open set, 내부의 모든 점이 다시 근방을 가지는 집합) $U$가 존재하여 $p \in U \subseteq N$을 만족하는 집합 $N$을 의미한다. 즉, 두 점이 인접하다는 것은 한 점이 다른 점의 근방 내에 존재하거나, 공통의 근방을 공유함을 시사한다.
3.2 폐포(Closure)를 통한 정의
점 $x$가 집합 $A$에 인접해 있다는 것은 $x$가 $A$의 폐포(Closure) $\text{cl}(A)$에 속함을 의미한다. 폐포란 집합 $A$와 그 집합의 모든 집적점(Limit point)을 포함하는 가장 작은 닫힌 집합이다. 만약 $x \in \text{cl}(A)$라면, $x$의 임의의 근방은 항상 $A$의 원소와 교집합을 가지므로, $x$는 $A$와 위상적으로 인접하다고 볼 수 있다.
4. 연결성과 인접성의 관계
개별 요소 간의 국소적인 인접성은 전체 공간의 전역적인 성질인 연결성(Connectedness)으로 확장된다.
- 연결성 (Connectedness): 공간이 두 개의 서로소인 개집합으로 분리되지 않는 성질을 말한다. 이는 인접한 요소들이 사슬처럼 이어져 전체를 구성하고 있음을 의미한다.
- 경로 연결성 (Path-connectedness): 공간 내의 임의의 두 점 $a, b$에 대해, $a$에서 $b$로 가는 연속 함수 $f: [0, 1] \to X$ (경로)가 존재하는 성질이다.
- 그래프 이론에서는 인접한 정점들을 따라 이동하여 목적지에 도달할 수 있다면 두 정점은 '연결되어 있다'고 정의하며, 이는 위상수학의 경로 연결성과 개념적으로 일치한다.
5. 응용 및 확장 개념
인접성 개념은 이산 공간인 디지털 환경에서 매우 중요하게 다뤄진다.
5.1 디지털 이미지의 픽셀 인접성
2차원 격자 구조의 이미지에서 픽셀 $(x, y)$의 인접성은 공유하는 경계의 형태에 따라 정의된다.
- 4-인접 (4-adjacency): 상, 하, 좌, 우의 변을 공유하는 픽셀만 인접한 것으로 간주한다.
- 8-인접 (8-adjacency): 변뿐만 아니라 꼭짓점(대각선)을 공유하는 픽셀까지 모두 인접한 것으로 간주한다.
[인접성 도식도]
[ 4-인접 ] [ 8-인접 ]
( ) ( ) ( ) ( )
( ) [P] ( ) ( ) ( ) [P] ( ) ( )
( ) ( ) ( ) ( )
(참고: 실제 이미지에서는 4-인접은 십자(+) 형태, 8-인접은 3x3 정사각형 형태의 연결성을 띤다.)
5.2 m-인접성 (m-adjacency)
8-인접성은 대각선 연결을 허용함으로써 경로의 모호함(Ambiguity)을 유발할 수 있다. 이를 해결하기 위해 m-인접성(mixed-adjacency)이 정의되었다. 이는 8-인접성 중 특정 조건(두 픽셀이 4-인접한 공통 픽셀을 가지지 않는 경우 등)을 만족하는 경우에만 인접한 것으로 간주하여, 디지털 영상 처리에서 픽셀 간의 유일한 경로를 정의하는 데 사용된다.
5.3 알고리즘 구현 예시 (Python)
다음은 2차원 배열에서 특정 좌표의 8-인접 픽셀을 탐색하는 코드이다.
def get_adjacent_pixels(x, y, width, height):
adjacent = []
# -1, 0, 1의 오프셋을 이용하여 8방향 탐색
for dx in [-1, 0, 1]:
for dy in [-1, 0, 1]:
if dx == 0 and dy == 0:
continue # 자기 자신은 제외
nx, ny = x + dx, y + dy
# 배열 범위 내에 있는지 확인 (Boundary Check)
if 0 <= nx < width and 0 <= ny < height:
adjacent.append((nx, ny))
return adjacent
# 예시: 5x5 이미지에서 (2, 2) 좌표의 인접 픽셀 찾기
width, height = 5, 5
target_x, target_y = 2, 2
result = get_adjacent_pixels(target_x, target_y, width, height)
print(f"좌표 ({target_x}, {target_y})의 8-인접 픽셀 목록:")
print(result)
# 출력 결과: [(1, 1), (1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2), (3, 3)]
6. 관련 항목
- [[거리 공간 (Metric Space)]]: 점들 사이의 거리를 정의하여 인접성을 정량화한 공간.
- [[위상 동형 (Homeomorphism)]]: 두 위상 공간의 인접성 구조가 보존되는 연속 함수 관계.
- [[인접 행렬 (Adjacency Matrix)]]: 그래프의 인접 관계를 행렬로 표현한 것.
- [[연결 성분 (Connected Component)]]: 그래프 내에서 서로 인접한 정점들의 최대 집합.
# 인접성 (Adjacency)
## 1. 개요
**인접성(Adjacency)**이란 수학 및 컴퓨터 과학에서 두 개의 객체 사이에 직접적인 연결 관계가 존재하거나, 정의된 위상/거리 체계 내에서 최소 단위의 근접성을 가지는 상태를 의미한다. 이는 단순히 물리적인 거리를 측정하는 것을 넘어, 그래프 이론에서는 정점 간의 연결 관계로, 위상수학에서는 근방(Neighborhood)의 개념으로, 디지털 영상 처리에서는 픽셀 간의 공유 경계로 정의되는 추상적 개념이다.
## 2. 그래프 이론에서의 인접성
그래프 이론에서 인접성은 정점(Vertex, 노드)들 사이의 관계를 정의하는 핵심 개념이다.
### 2.1 정의
그래프 $G = (V, E)$에서 두 정점 $u, v \in V$가 간선 $e = (u, v) \in E$로 연결되어 있을 때, 두 정점 $u$와 $v$는 **인접하다(Adjacent)**고 말한다. 이때 간선 $e$는 두 정점을 잇는 직접적인 경로가 된다.
### 2.2 인접성과 부합성(Incidence)의 차이
인접성과 혼동하기 쉬운 개념으로 **부합성(Incidence)**이 있다. 두 개념의 결정적인 차이는 관계를 맺는 대상의 종류에 있다.
- **인접성(Adjacency):** 정점과 정점 사이의 관계. (예: 정점 A와 정점 B가 간선으로 연결됨 $\rightarrow$ A와 B는 인접함)
- **부합성(Incidence):** 정점과 간선 사이의 관계. (예: 정점 A가 간선 $e$의 끝점임 $\rightarrow$ 정점 A와 간선 $e$는 부합함)
### 2.3 인접성 표현 방식 및 복잡도 비교
그래프의 인접 관계를 컴퓨터 메모리에 저장하는 방식은 크게 인접 행렬과 인접 리스트로 나뉜다.
| 구분 | 인접 행렬 (Adjacency Matrix) | 인접 리스트 (Adjacency List) |
| :--- | :--- | :--- |
| **정의** | $V \times V$ 크기의 2차원 배열로 표현 | 각 정점마다 연결된 정점들의 목록을 저장 |
| **공간 복잡도** | $O(V^2)$ | $O(V + E)$ |
| **연결 확인 시간** | $O(1)$ (상수 시간) | $O(\text{degree}(v))$ (정점의 차수만큼 탐색) |
| **특징** | 밀집 그래프(Dense Graph)에 유리 | 희소 그래프(Sparse Graph)에 유리 |
**[표현 예시]**
정점 {0, 1, 2}가 있고 간선 {(0,1), (0,2)}가 존재하는 그래프의 경우:
- **인접 행렬:**
$$\begin{pmatrix} 0 & 1 & 1 \\ 1 & 0 & 0 \\ 1 & 0 & 0 \end{pmatrix}$$
- **인접 리스트:**
- 0: [1, 2]
- 1: [0]
- 2: [0]
## 3. 위상수학적 인접성과 근방
위상수학에서는 거리(Metric)라는 수치 대신 '집합'의 포함 관계로 인접성을 정의한다. 이를 통해 구체적인 거리 개념이 없더라도 '가까움'을 정의하기 위해 **근방(Neighborhood)** 개념을 사용한다.
### 3.1 근방과 개집합
위상 공간 $X$의 한 점 $p$의 **근방**이란, $p$를 포함하는 어떤 개집합(Open set, 내부의 모든 점이 다시 근방을 가지는 집합) $U$가 존재하여 $p \in U \subseteq N$을 만족하는 집합 $N$을 의미한다. 즉, 두 점이 인접하다는 것은 한 점이 다른 점의 근방 내에 존재하거나, 공통의 근방을 공유함을 시사한다.
### 3.2 폐포(Closure)를 통한 정의
점 $x$가 집합 $A$에 **인접**해 있다는 것은 $x$가 $A$의 **폐포(Closure)** $\text{cl}(A)$에 속함을 의미한다. 폐포란 집합 $A$와 그 집합의 모든 집적점(Limit point)을 포함하는 가장 작은 닫힌 집합이다. 만약 $x \in \text{cl}(A)$라면, $x$의 임의의 근방은 항상 $A$의 원소와 교집합을 가지므로, $x$는 $A$와 위상적으로 인접하다고 볼 수 있다.
## 4. 연결성과 인접성의 관계
개별 요소 간의 국소적인 인접성은 전체 공간의 전역적인 성질인 **연결성(Connectedness)**으로 확장된다.
1. **연결성 (Connectedness):** 공간이 두 개의 서로소인 개집합으로 분리되지 않는 성질을 말한다. 이는 인접한 요소들이 사슬처럼 이어져 전체를 구성하고 있음을 의미한다.
2. **경로 연결성 (Path-connectedness):** 공간 내의 임의의 두 점 $a, b$에 대해, $a$에서 $b$로 가는 연속 함수 $f: [0, 1] \to X$ (경로)가 존재하는 성질이다.
- 그래프 이론에서는 인접한 정점들을 따라 이동하여 목적지에 도달할 수 있다면 두 정점은 '연결되어 있다'고 정의하며, 이는 위상수학의 경로 연결성과 개념적으로 일치한다.
## 5. 응용 및 확장 개념
인접성 개념은 이산 공간인 디지털 환경에서 매우 중요하게 다뤄진다.
### 5.1 디지털 이미지의 픽셀 인접성
2차원 격자 구조의 이미지에서 픽셀 $(x, y)$의 인접성은 공유하는 경계의 형태에 따라 정의된다.
- **4-인접 (4-adjacency):** 상, 하, 좌, 우의 변을 공유하는 픽셀만 인접한 것으로 간주한다.
- **8-인접 (8-adjacency):** 변뿐만 아니라 꼭짓점(대각선)을 공유하는 픽셀까지 모두 인접한 것으로 간주한다.
**[인접성 도식도]**
```text
[ 4-인접 ] [ 8-인접 ]
( ) ( ) ( ) ( )
( ) [P] ( ) ( ) ( ) [P] ( ) ( )
( ) ( ) ( ) ( )
```
*(참고: 실제 이미지에서는 4-인접은 십자(+) 형태, 8-인접은 3x3 정사각형 형태의 연결성을 띤다.)*
### 5.2 m-인접성 (m-adjacency)
8-인접성은 대각선 연결을 허용함으로써 경로의 모호함(Ambiguity)을 유발할 수 있다. 이를 해결하기 위해 **m-인접성(mixed-adjacency)**이 정의되었다. 이는 8-인접성 중 특정 조건(두 픽셀이 4-인접한 공통 픽셀을 가지지 않는 경우 등)을 만족하는 경우에만 인접한 것으로 간주하여, 디지털 영상 처리에서 픽셀 간의 유일한 경로를 정의하는 데 사용된다.
### 5.3 알고리즘 구현 예시 (Python)
다음은 2차원 배열에서 특정 좌표의 8-인접 픽셀을 탐색하는 코드이다.
```python
def get_adjacent_pixels(x, y, width, height):
adjacent = []
# -1, 0, 1의 오프셋을 이용하여 8방향 탐색
for dx in [-1, 0, 1]:
for dy in [-1, 0, 1]:
if dx == 0 and dy == 0:
continue # 자기 자신은 제외
nx, ny = x + dx, y + dy
# 배열 범위 내에 있는지 확인 (Boundary Check)
if 0 <= nx < width and 0 <= ny < height:
adjacent.append((nx, ny))
return adjacent
# 예시: 5x5 이미지에서 (2, 2) 좌표의 인접 픽셀 찾기
width, height = 5, 5
target_x, target_y = 2, 2
result = get_adjacent_pixels(target_x, target_y, width, height)
print(f"좌표 ({target_x}, {target_y})의 8-인접 픽셀 목록:")
print(result)
# 출력 결과: [(1, 1), (1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2), (3, 3)]
```
## 6. 관련 항목
- [[거리 공간 (Metric Space)]]: 점들 사이의 거리를 정의하여 인접성을 정량화한 공간.
- [[위상 동형 (Homeomorphism)]]: 두 위상 공간의 인접성 구조가 보존되는 연속 함수 관계.
- [[인접 행렬 (Adjacency Matrix)]]: 그래프의 인접 관계를 행렬로 표현한 것.
- [[연결 성분 (Connected Component)]]: 그래프 내에서 서로 인접한 정점들의 최대 집합.