하세 다이어그램 편집하기

'''하세 다이어그램'''(Hasse Diagram)은 부분 순서 집합(Partially Ordered Set, Poset)의 순서 관계를 시각적으로 표현하는 그래프이다.  불필요한 정보를 생략하여 보다 간결하게 표현하며, 수학 및 컴퓨터 과학에서 순서 관계를 분석하는 데 사용된다.
==정의==
하세 다이어그램은 부분 순서 집합을 표현하는 특수한 그래프이며, 다음 조건을 만족한다.
*'''반사성(Reflexivity)을 생략'''
**모든 원소 x에 대해 '''x ≤ x'''가 성립하지만, 다이어그램에서 자기 자신을 가리키는 간선은 생략된다.

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

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

=== 기본 관계 표현 ===

다음은 집합 X = {1, 2, 4, 8}에서 나눗셈 관계를 기반으로 한 하세 다이어그램의 예제이다.<pre>
    8
    |
    4
    |
    2
    |
    1
</pre>위 다이어그램에서:
*`1 ≤ 2`, `2 ≤ 4`, `4 ≤ 8` 관계가 표현되었다.
*`1 ≤ 4`, `1 ≤ 8` 등의 관계는 이행성(Transitivity) 때문에 생략되었다.

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

1. 아래 다이어그램은 x1, x2 간에는 대소 관계가 있고, y 요소들 간에도 대소 관계가 있으나 x 요소들과 y 요소들 간의 대소 관계는 없는 것으로 본다.<pre>
x1   y1
|    |
x2   y2
     |
     y3
</pre>2. 만약 x1이 y1보다 큰 경우

* x1과 y1의 대소관계는 정의되었다. (간선으로 연결됨)
* 그러나 x2와 y1과의 관계는 정의되지 않았다.
<pre>
x1  
|  \  
x2  y1 
     |
    y2
     |
    y3
</pre>3. 만약 x2가 y1보다 큰 경우<pre>
x1  
| 
x2
|
y1 
|
y2
|
y3
</pre>4. 만약 x2가 y1보다 작은 경우

* 여기선 x2가 y1 보다 작은 것이 표현되지만, 아직 x2가 y2나 y3보다 작은지 큰지는 드러나지 않는다.
<pre>
x1  
| 
y1 
|  \
y2  x2
|
y3
</pre>
===부분 집합 관계(⊆)===
집합 '''S = {a, b}'''의 모든 부분 집합을 부분 순서 관계(⊆)로 표현하면 다음과 같다.<pre>
      {a, b}
     /      \
  {a}       {b}
     \      /
      ∅ (공집합)
</pre>위 다이어그램에서:
*`{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.
*[https://mathworld.wolfram.com/HasseDiagram.html Wolfram MathWorld - Hasse Diagram]
[[분류:알고리즘]]