하세 도형
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
하세 도형은 반순서 집합을 시각적으로 표현하는 방법으로, 반사율, 추이율, 반대칭율을 만족하는 관계를 그래프로 나타낸 것이다. 하세 도형은 각 원소를 노드로, 피복 관계(x < y이고 x < z < y인 z가 없는 관계)를 변으로 표현하며, 반사 관계와 추이 관계는 생략한다. 하세 도형은 멱집합, 약수와 배수, 집합 분할 등 다양한 예시를 통해 표현될 수 있으며, 다이어그램 작성 시 대칭성과 내부 구조를 고려하는 것이 중요하다. 브루하 순서, UML 클래스 다이어그램 등 다양한 분야에 응용된다.
더 읽어볼만한 페이지
- 기하 알고리즘 - 최근접 이웃 탐색
최근접 이웃 탐색은 다차원 공간에서 주어진 질의와 가장 유사한 데이터를 찾는 최적화 문제로, 데이터 압축, 데이터 마이닝, 기계 학습 등 다양한 분야에서 활용되며, 효율적인 탐색을 위해 다양한 알고리즘이 개발되고 있고, 개인 정보 보호 및 데이터 편향성과 같은 윤리적 문제에 대한 고려도 중요해지고 있다. - 기하 알고리즘 - 신발끈 공식
신발끈 공식은 평면 다각형의 꼭짓점 좌표를 이용해 면적을 구하는 공식으로, 사다리꼴, 삼각형, 행렬식 등으로 표현되며, 꼭짓점들을 특정 순서로 나열하여 계산하는 모습이 신발끈을 묶는 모양과 유사하여 붙여진 이름이다. - 그래프 그리기 - 덴드로그램
덴드로그램은 데이터 분석에서 데이터 포인트 간 계층적 관계를 시각적으로 표현하는 나무 형태의 다이어그램으로, 군집 분석에서 클러스터 간 유사성을 나타내기 위해 활용되며 다양한 분야에 응용된다. - 그래프 그리기 - 상태도 (오토마타 이론)
상태도는 유한 오토마타 이론에서 시스템의 상태와 전이를 시각적으로 표현하는 유향 그래프이며, 무어 머신, 밀리 머신, 하렐 상태도 등 다양한 형태로 활용된다.
| 하세 도형 |
|---|
2. 정의 및 기본 개념
하세 도형은 유한 부분 순서 집합(포셋)을 시각적으로 표현하는 방법이다. 각 원소는 점으로 표현되고, 순서 관계는 선으로 표현된다. 이때, 반사 관계와 추이 관계는 표현하지 않아 간결하게 나타낸다.
예를 들어, 집합 {x, y, z}의 멱집합 원소들에 대한 부분 집합 관계나 60의 약수들에 대한 배수 관계를 하세 도형으로 나타낼 수 있다.
하세 도형은 포셋을 직관적으로 나타내는 유용한 도구이지만, "좋은" 하세 도형을 그리기는 어려울 수 있다. 이는 주어진 포셋에 대해 하세 도형을 그리는 여러 방법이 존재하고, 순서의 대칭성과 내부 구조가 쉽게 손실될 수 있기 때문이다.
아래는 포함 관계 에 의해 정렬된 4개 원소 집합의 멱집합에 대한 네 가지 하세 다이어그램이다.
각 다이어그램은 동일한 부분 순서를 나타내지만, 서로 다른 구조를 강조한다. 첫 번째 다이어그램은 멱집합이 등급 포셋임을 보여준다. 두 번째 다이어그램은 4차원 초입방체와 3차원 입방체, 사면체(추상 3-다포체)와 삼각형(추상 2-다포체)의 관계를, 세 번째 다이어그램은 구조의 내부 대칭성을 보여준다. 네 번째 다이어그램은 정점을 4x4 격자로 배열한다.
일반적인 그래프로 부분 순서 집합 (''S'', ≤)을 표현하면, ''u'' ≤ ''v'' 관계를 그래프의 변 (''u'', ''v'')로 나타낼 수 있다. 그러나 이 그래프는 매우 복잡하고 불필요한 정보를 포함한다. 반순서의 조건인 반사율(''a'' ≤ ''a''), 추이율(''a'' ≤ ''b''이고 ''b'' ≤ ''c''이면 ''a'' ≤ ''c''), 반대칭율(''a'' ≤ ''b''이고 ''b'' ≤ ''a''이면 ''a'' = ''b'')을 고려하면 그래프를 간소화할 수 있다.
위 그림은 집합 분할이 더 작다고 하는 반순서 집합 ({1,2,3,4}, ≤)에서 루프(반사율)를 제외한 그래프이다. 하지만 이 그래프에도 추이율에 의해 불필요한 정보가 포함되어 있다. 따라서 추이 관계와 반사 관계를 제거하고 남은 관계만을 변으로 그리면 더 간결한 하세 도형을 얻을 수 있다.
2. 1. 표현 규칙
포셋에서 하세 도형은 피복 관계를 이용하여 표현한다. 피복 관계는 다음과 같이 정의된다.- x < y 이고, x < z < y 인 z 가 존재하지 않는 관계
하세 도형은 다음의 규칙을 따른다.
- 더 작은 원소 x는 아래쪽에 위치한다.
- 더 큰 원소 y는 위쪽에 위치한다.
- 두 원소가 덮개 관계에 있으면, 두 원소를 선으로 연결한다.
- 반사 관계 (x ≤ x) 와 추이 관계 (x ≤ y 이고 y ≤ z 이면 x ≤ z)는 표현하지 않는다.
이러한 규칙에 따라, 하세 도형은 피복 관계의 역으로 표현될 수 있다.
3. 예시
- 집합 \{{ ''x'', ''y'', ''z'' }\}의 멱집합에는 포함 관계에 의한 반순서가 있으며, 하세 그림으로 나타낼 수 있다.
- 60의 모든 약수의 집합 ''A'' = { 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60 }에는, 나눗셈에 의한 반순서가 있으며, 하세 그림으로 나타낼 수 있다.
- 집합 { 1, 2, 3, 4 }에는 모두 15개의 분할이 있으며, 세분화(refinement)에 의한 반순서(더 세분화된 분할이 더 작다고 가정)가 있으며, 하세 그림으로 나타낼 수 있다.
하세 도형은 유한 포셋을 다루는 간단하면서도 직관적인 도구이지만, "좋은" 다이어그램을 그리는 것은 상당히 어렵다. 일반적으로 주어진 포셋에 대해 하세 다이어그램을 그릴 수 있는 방법이 여러 가지이기 때문이다. 단순히 순서의 최소 원소부터 시작하여 더 큰 원소를 점진적으로 그리는 것은 종종 순서의 대칭성과 내부 구조를 쉽게 손실 시키는 결과를 낳는다.
다음은 이 문제를 보여주는 예시이다. 포함 관계 에 의해 정렬된 4개 원소 집합의 멱집합에 대한 네 가지 하세 다이어그램을 살펴보자. 각 부분 집합은 특정 원소가 부분 집합에 있는지(1) 없는지(0)를 보여주는 이진 인코딩으로 레이블이 지정된 노드를 갖는다.
첫 번째 다이어그램은 멱집합이 등급 포셋임을 명확히 보여준다. 두 번째 다이어그램은 동일한 등급 구조를 갖지만, 일부 가장자리를 다른 가장자리보다 길게 만들어 4차원 초입방체가 두 개의 3차원 입방체의 조합적 합집합이며, 사면체(추상 3-다포체)가 마찬가지로 두 개의 삼각형(추상 2-다포체)을 병합한다는 것을 강조한다. 세 번째 다이어그램은 구조의 내부 대칭성을 보여준다. 네 번째 다이어그램에서 정점은 4×4 격자로 배열된다.
3. 1. 멱집합
집합 {x, y, z}의 멱집합은 포함 관계에 의한 반순서를 가지며, 위와 같은 하세 그림으로 나타낼 수 있다.3. 2. 약수와 배수
60의 약수들에 대한 배수 관계는 다음과 같이 표현된다.3. 3. 집합 분할
집합 { 1, 2, 3, 4 }에는 모두 15개의 분할이 있으며, 더 세분화된 분할이 더 작은 것으로 정의하는 세분화(refinement)에 의한 반순서 관계가 있다. 이는 위의 하세 그림으로 나타낼 수 있다.4. 다이어그램 작성 및 설계
하세 다이어그램은 포셋을 직관적으로 표현하는 도구이지만, '좋은' 다이어그램을 그리기는 어렵다. 순서의 대칭성과 내부 구조를 보존하면서 표현하기 위해 다양한 방법이 시도된다.
포함 관계 에 의해 정렬된 4개 원소 집합의 멱집합을 예로 들어, 이 어려움을 보여주는 네 가지 하세 다이어그램은 다음과 같다.
각 부분 집합은 원소의 포함 여부(1) 또는 미포함(0)을 나타내는 이진 인코딩으로 레이블이 지정된 노드를 갖는다.
- 첫 번째 다이어그램은 멱집합이 등급 포셋임을 보여준다.
- 두 번째 다이어그램은 4차원 초입방체가 두 개의 3차원 입방체의 조합적 합집합임을 강조한다.
- 세 번째 다이어그램은 구조의 내부 대칭성을 보여준다.
- 네 번째 다이어그램에서 정점은 4×4 격자로 배열된다.
반순서 집합 (''S'', ≤)을 시각적으로 표현하기 위해 그래프를 사용하고, ''u'' ≤ ''v'' 관계를 그래프 내의 변 (''u'', ''v'')로 나타낼 수 있다. 그러나 이 그래프는 불필요한 정보(반사율, 추이율)를 포함하여 매우 복잡해진다.
추이 관계와 반사 관계를 고려하여 필수적인 관계만을 변으로 그리면 더 간결한 하세 도형을 얻을 수 있다. 이 관계를 "피복 관계"(cover relation)라고 하며, 하세 도형은 이 관계를 사용하여 정의된다. 즉, 하세 도형은 피복 관계의 역으로 식별할 수 있다.
하세 도표는 유한한 반순서 집합을 다루는 단순하고 직관적인 도구이지만, "좋은" 그림을 그리는 것은 다소 어렵다. 주어진 반순서 집합에 대해 하세 도표는 다양한 형태로 그릴 수 있다. 가장 작은 원소를 출발점으로 하여 점차 큰 쪽으로 그려나가는 방법이 있는데, 이 방법으로 생성된 그림은 대칭성이나 순서의 내부 구조가 쉽게 사라져 좋지 않다.
집합 ''S'' = {''a'', ''b'', ''c'', ''d''} 의 멱집합을 예시로, ''S''의 모든 부분집합의 집합 을 통해 부분집합의 포함 관계 로 순서를 정할 수 있다. 이 순서를 그린 3가지 하세 도표는 아래와 같다.
왼쪽 그림은 가장 단순하며, 5층으로, 각 층의 꼭짓점은 원소의 수가 같은 부분집합에 대응한다. 아래에서 두 번째 층은 원소가 1개인 집합에 대응한다.
위의 예는 같은 순서에 대한 다른 하세 도표를 나타내고 있으며, 각각이 원래의 수학적 구조의 다른 면을 반영하고 있다. 왼쪽 그림은 꼭짓점의 층마다 원소의 수가 대응하고 있다. 오른쪽 그림은 그 구조의 내부 대칭성을 강하게 반영하고 있다. 가운데 그림은 두 개의 입방체를 연결한 것과 같은 형태가 되어, 멱집합 2''S'' 와 product order 2 × 2{''a'', ''b'', ''c''} 사이의 관계를 강조한 것이다.
더 좋은 그림을 그리기 위한 다양한 알고리즘이 고안되었지만, 현재로서는 좋은 그림을 그리는 데는 인간이 개입하는 것이 좋다.
4. 1. 좋은 다이어그램의 조건
하세 도형은 유한 포셋을 다루는 간단하고 직관적인 도구이지만, "좋은" 다이어그램을 그리기는 꽤 어렵다. 주어진 포셋에 대해 하세 다이어그램을 그리는 방법이 여러 가지이기 때문이다. 단순히 순서의 최소 원소부터 시작하여 더 큰 원소를 점진적으로 그리는 방법은 순서의 대칭성과 내부 구조를 쉽게 잃어버리게 만든다.다음은 이 문제를 보여주는 예시이다. 포함 관계 에 의해 정렬된 4개 원소 집합의 멱집합에 대한 네 가지 하세 다이어그램을 살펴보자. 각 부분 집합은 특정 원소가 부분 집합에 있는지(1) 없는지(0)를 보여주는 이진 인코딩으로 레이블이 지정된 노드를 갖는다.
첫 번째 다이어그램은 멱집합이 등급 포셋임을 명확하게 보여준다. 두 번째 다이어그램은 동일한 등급 구조를 갖지만, 일부 가장자리를 다른 가장자리보다 길게 만들어 4차원 초입방체가 두 개의 3차원 입방체의 조합적 합집합이며, 사면체(추상 3-다포체)가 두 개의 삼각형(추상 2-다포체)을 병합한다는 것을 강조한다. 세 번째 다이어그램은 구조의 내부 대칭성을 보여준다. 네 번째 다이어그램에서 정점은 4×4 격자로 배열된다.
4. 2. 상향 평면성 (Upward planarity)
부분 순서가 하세 다이어그램으로 그려질 때 두 모서리가 교차하지 않는 경우, 해당 덮개 그래프는 ''상향 평면적''이라고 한다. 상향 평면성과 교차 없는 하세 다이어그램 구성에 대한 여러 결과는 다음과 같다.
- 그려질 부분 순서가 격자인 경우, 순서 차원이 최대 2인 경우에만 교차 없이 그릴 수 있다.[3] 이 경우, 순서 차원을 실현하는 두 개의 선형 순서에서 요소의 데카르트 좌표를 도출한 다음 드로잉을 시계 반대 방향으로 45도 회전하여 교차 없는 드로잉을 찾을 수 있다.
- 부분 순서가 최대 하나의 최소 원소를 갖거나 최대 하나의 최대 원소를 갖는 경우, 교차 없는 하세 다이어그램이 있는지 여부를 선형 시간 내에 테스트할 수 있다.[4]
- 여러 소스와 싱크가 있는 부분 순서를 교차 없는 하세 다이어그램으로 그릴 수 있는지 여부를 결정하는 것은 NP-완전 문제이다.[5]
5. 응용
하세 도형은 여러 분야에 응용된다.
- 모든 코세터 군에는 여러 개의 반순서가 있으며, 이를 통틀어 '''브루하 순서'''라고 부른다.
- 소프트웨어 공학/객체 지향 설계에서 소프트웨어 시스템의 클래스와 이들 클래스 간의 상속 관계는 클래스 다이어그램을 사용하여 묘사된다.
5. 1. 브루하 순서 (Bruhat order)
모든 코세터 군 (''W'', ''S'')에는 여러 개의 반순서가 있으며, 이를 통틀어 '''브루하 순서'''라고 부른다. 이들의 정의는 생성계 ''S''에서의 기약어(reduced word)에 기반한다. 강한 브루하 순서에서 원소 ''w''가 원소 ''y''보다 크다는 것은, ''y''의 기약어를 접두사로 갖는 ''w''의 기약어가 존재하는 경우이다. 이 순서에 대한 하세 도형은 (''W'', ''S'')의 케일리 그래프와 일치한다. 대칭군 ''S''''n''의 경우, 케일리 그래프는 치환 다면체이다. ''n''=3일 경우, 하세 다이어그램은 하나의 정점이 가장 위에 있고, 하나의 정점이 가장 아래에 있는 (정) 육각형이 된다.5. 2. UML 클래스 다이어그램
소프트웨어 공학/객체 지향 설계에서 소프트웨어 시스템의 클래스와 이들 클래스 간의 상속 관계는 하세 다이어그램의 한 형태인 클래스 다이어그램을 사용하여 묘사된다. 이때 클래스를 연결하는 가장자리는 슈퍼클래스 끝에 열린 삼각형이 있는 실선 세그먼트로 그려진다.
참조
[1]
참고
[2]
참고
[3]
참고
[4]
참고
[5]
참고
[6]
문서
無限な半順序は推移簡約を持つとは限らない。各元には必ず immediate successor がなければならない。実数の区間 [0, 1] を考えてみればよい。
[7]
참고
[8]
참고
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com