하세 다이어그램 편집하기

'''하세 다이어그램'''(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) 때문에 생략되었다.
===또 다른 예제: 부분 집합 관계(⊆)===
집합 **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]
[[분류:알고리즘]]