IT용어위키

하세 다이어그램(Hasse Diagram)은 부분 순서 집합(Partially Ordered Set, Poset)의 순서 관계를 시각적으로 표현하는 그래프이다. 불필요한 정보를 생략하여 보다 간결하게 표현하며, 수학 및 컴퓨터 과학에서 순서 관계를 분석하는 데 사용된다.

정의

하세 다이어그램은 부분 순서 집합을 표현하는 특수한 그래프이며, 다음 조건을 만족한다.

반사성(Reflexivity)을 생략
- 모든 원소 x에 대해 x ≤ x가 성립하지만, 다이어그램에서 자기 자신을 가리키는 간선은 생략된다.

이행성(Transitivity)을 생략
- 만약 x ≤ y이고 y ≤ z이면, 직접적인 간선(x → z)은 생략된다.
- 즉, 다이어그램에서는 가장 직접적인 순서 관계만 표시된다.

방향성을 포함하지만 방향 화살표를 생략
- 유향 그래프(Directed Graph)이지만, 하세 다이어그램에서는 간선의 방향을 위쪽 방향으로 해석한다.
- 따라서 낮은 원소는 아래쪽, 높은 원소는 위쪽에 배치된다.

예제

기본 관계 표현

다음은 집합 X = {1, 2, 4, 8}에서 나눗셈 관계를 기반으로 한 하세 다이어그램의 예제이다.

위 다이어그램에서:

`1 ≤ 2`, `2 ≤ 4`, `4 ≤ 8` 관계가 표현되었다.
`1 ≤ 4`, `1 ≤ 8` 등의 관계는 이행성(Transitivity) 때문에 생략되었다.

비교 관계

다음은 집합 A = {x1, x2} , B = {y1, y2, y3} 을 비교 병합하는 하세 다이어그램의 예제이다.

1. 아래 다이어그램은 x1, x2 간에는 대소 관계가 있고, y 요소들 간에도 대소 관계가 있으나 x 요소들과 y 요소들 간의 대소 관계는 없는 것으로 본다.

x1   y1
|    |
x2   y2
     |
     y3

2. 만약 x1이 y1보다 큰 경우

x1과 y1의 대소관계는 정의되었다. (간선으로 연결됨)
그러나 x2와 y1과의 관계는 정의되지 않았다.

3. 만약 x2가 y1보다 큰 경우

x1  
| 
x2
|
y1 
|
y2
|
y3

4. 만약 x2가 y1보다 작은 경우

여기선 x2가 y1 보다 작은 것이 표현되지만, 아직 x2가 y2나 y3보다 작은지 큰지는 드러나지 않는다.

x1  
| 
y1 
|  \
y2  x2
|
y3

부분 집합 관계(⊆)

집합 S = {a, b}의 모든 부분 집합을 부분 순서 관계(⊆)로 표현하면 다음과 같다.

      {a, b}
     /      \
  {a}       {b}
     \      /
      ∅ (공집합)

위 다이어그램에서:

`{a, b} ⊇ {a}`, `{a, b} ⊇ {b}`, `{a} ⊇ ∅`, `{b} ⊇ ∅`의 포함 관계가 표현되었다.
`{a, b} ⊇ ∅` 등의 간선은 이행성으로 인해 생략되었다.

하세 다이어그램의 특징

하세 다이어그램은 다음과 같은 특징을 가진다.

순서 관계를 직관적으로 표현
- 수직적 배치를 이용하여 낮은 원소에서 높은 원소로의 관계를 쉽게 이해할 수 있다.

반사성과 이행성을 생략하여 간결함 유지
- 모든 원소가 자기 자신과 비교되는 반사적 관계(x ≤ x)는 생략된다.
- 이행성을 통해 유도되는 관계도 생략하여 간선의 수를 최소화한다.

위상 정렬이 가능
- 유향 비순환 그래프(DAG)로 볼 수 있으며, 위상 정렬(Topological Sorting)이 가능하다.

응용

하세 다이어그램은 여러 수학 및 컴퓨터 과학 분야에서 활용된다.

부분 순서 집합(POSET) 분석
- 원소 간의 부분 순서를 직관적으로 표현하는 데 사용된다.

격자 이론(Lattice Theory)
- 논리 연산(Boolean Algebra) 및 수학적 격자 구조를 분석하는 데 활용된다.

데이터 의존성 분석
- 데이터 간의 선후 관계를 분석하는 데 유용하다.

위상 정렬(Topological Sorting)
- 유향 비순환 그래프(DAG)에서 정점 간의 순서를 결정하는 데 사용된다.

같이 보기

참고 문헌

Birkhoff, G., Lattice Theory, American Mathematical Society, 1995.
Davey, B. A., & Priestley, H. A., Introduction to Lattices and Order, Cambridge University Press, 2002.
Wolfram MathWorld - Hasse Diagram