하이퍼그래프

3. 정의

그래프 이론에서, 하이퍼그래프는 그래프를 일반화한 것이다. 일반적인 그래프의 에지(edge)는 두 개의 정점(vertex)을 연결하지만, 하이퍼에지(hyperedge)는 여러 개의 정점을 연결할 수 있다.

하이퍼그래프는 정점 집합과 하이퍼에지 집합으로 구성된다. 하이퍼에지는 정점 집합의 공집합이 아닌 부분집합이다. 형식적으로 하이퍼그래프 ''H''는 순서쌍 $H\; =\; (X,\; E)$로 표현된다. 여기서 ''X''는 정점들의 집합이고, ''E''는 ''X''의 부분집합들의 집합으로, 하이퍼에지들의 집합이다.

단순 하이퍼그래프는 루프(단일 정점을 가진 하이퍼에지)나 반복되는 하이퍼에지가 없다.

4. 성질

• '''비어있음''' - 변(hyperedge)이 없다.
• '''비단순''' (또는 '''다중''') - 루프(단일 정점을 가진 하이퍼에지) 또는 반복되는 변이 있다. 이는 동일한 정점 집합을 포함하는 두 개 이상의 변이 있을 수 있음을 의미한다.
• '''단순''' - 루프와 반복되는 변이 없다.
• '''d^영어-정규''' - 모든 정점의 차수는 d^영어이며, 정확히 d^영어개의 하이퍼에지에 포함된다.
• '''2-채색 가능''' - 정점을 두 개의 클래스 ''U''와 ''V''로 분할하여, 최소 2의 기수를 가진 각 하이퍼에지가 두 클래스 모두에서 최소 하나의 정점을 포함하도록 할 수 있다. '''속성 B'''라고도 한다.
• * '''이분'''과 '''균형'''은 더 강력한 속성이다.
• '''k^영어-균일''' - 각 하이퍼에지는 정확히 k^영어개의 정점을 포함한다.
• '''k^영어-분할''' - 정점은 k^영어개의 부분으로 분할되며, 각 하이퍼에지는 각 유형의 정점을 정확히 하나씩 포함한다.
• * 모든 '''k^영어-분할''' 하이퍼그래프 (k^영어 ≥ 2)는 '''k^영어'''-균일하고 이분 그래프(및 2-채색 가능)이다.
• '''축소됨'''^[26] - 어떤 하이퍼에지도 다른 하이퍼에지의 진정한 부분 집합이 아니다. 즉, 모든 하이퍼에지는 포함에 대해 최대이다. 하이퍼그래프의 '''축소'''는 다른 하이퍼에지에 포함된 모든 하이퍼에지를 제거하여 얻는다.
• '''하향 폐쇄''' - 무방향 하이퍼그래프의 변의 모든 하위 집합도 하이퍼에지이다. 하향 폐쇄 하이퍼그래프는 일반적으로 '''추상 단순 복합체'''라고 한다. 모든 하이퍼에지가 기수 1을 갖지 않는 한 일반적으로 축소되지 않는다.
• * ''확장 속성''을 가진 추상 단순 복합체는 '''매트로이드'''라고 한다.
• '''층상''' - 임의의 두 하이퍼에지에 대해, 서로소이거나, 하나가 다른 하나에 포함된다. 즉, 하이퍼에지 집합은 층상 집합족을 형성한다.

5. 관련 하이퍼그래프

부분 하이퍼그래프는 일부 정점이 제거된 하이퍼그래프이다. 공식적으로, $A\; \backslash subseteq\; X$에 의해 유도된 부분 하이퍼그래프 $H\_A$는 다음과 같이 정의된다.

:$H\_A=\backslash left(A,\; \backslash lbrace\; e\; \backslash cap\; A\; \backslash mid\; e\; \backslash in\; E,\; e\; \backslash cap\; A\; \backslash neq\; \backslash emptyset\; \backslash rbrace\; \backslash right).$

이를 ''H''를 ''A''로 '''제한'''한다고도 한다.^[27]

부분 하이퍼그래프의 확장은 $H\_A$에 부분적으로 포함된 $H$의 각 하이퍼에지가 확장 $Ex(H\_A)$에 완전히 포함된 하이퍼그래프이다. 공식적으로

:$Ex(H\_A)\; =\; (A\; \backslash cup\; A\text{'},\; E\text{'}\; )$이고, $A\text{'}\; =\; \backslash bigcup\_\{e\; \backslash in\; E\}\; e\; \backslash setminus\; A$ 및 $E\text{'}\; =\; \backslash lbrace\; e\; \backslash in\; E\; \backslash mid\; e\; \backslash subseteq\; (A\; \backslash cup\; A\text{'})\; \backslash rbrace$이다.

부분 하이퍼그래프는 일부 에지가 제거된 하이퍼그래프이다.^[27] 에지 인덱스 집합의 부분 집합 $J\; \backslash subset\; I\_e$가 주어지면, $J$에 의해 생성된 부분 하이퍼그래프는 다음과 같다.

:$\backslash left(X,\; \backslash lbrace\; e\_i\; \backslash mid\; i\backslash in\; J\; \backslash rbrace\; \backslash right).$

부분 집합 $A\backslash subseteq\; X$가 주어지면, 섹션 하이퍼그래프는 부분 하이퍼그래프이다.

:$H\; \backslash times\; A\; =\; \backslash left(A,\; \backslash lbrace\; e\_i\; \backslash mid\; i\backslash in\; I\_e,\; e\_i\; \backslash subseteq\; A\; \backslash rbrace\; \backslash right).$

$H$의 쌍대 $H^*$는 정점과 에지가 서로 바뀐 하이퍼그래프이므로, 정점은 $\backslash lbrace\; e\_i\; \backslash rbrace$로 주어지고, 에지는 $\backslash lbrace\; X\_m\; \backslash rbrace$로 주어지는데,

:$X\_m\; =\; \backslash lbrace\; e\_i\; \backslash mid\; x\_m\; \backslash in\; e\_i\; \backslash rbrace.$

하이퍼그래프의 쌍대를 구하는 연산은 대합이다. 즉,

:$\backslash left(H^*\backslash right)^*\; =\; H.$

연결된 하이퍼그래프 ''H''와 동일한 정점 집합을 가진 연결 그래프 ''G''는 ''H''의 모든 하이퍼에지가 ''G''에서 연결된 부분 그래프를 유도된 부분 그래프하는 경우 ''H''의 호스트 그래프이다. 연결되지 않은 하이퍼그래프 ''H''의 경우, ''G''는 ''G''의 연결 요소와 ''H''의 연결 요소 사이에 일대일 대응이 있고, 각 연결 요소 ''G''가 해당 ''H''의 호스트인 경우 호스트 그래프이다.

하이퍼그래프의 2-섹션 (또는 클리크 그래프, 표현 그래프, 프라이멀 그래프, 가이프만 그래프)은 하이퍼그래프와 동일한 정점을 가지며, 동일한 하이퍼에지에 포함된 모든 정점 쌍 사이에 에지를 가진 그래프이다.

6. 행렬 표현

접속 행렬(Incidence matrix^영어)은 하이퍼그래프의 정점과 하이퍼에지 간의 포함 관계를 나타내는 행렬이다. 무방향 하이퍼그래프의 경우, $I\; =\; (b\_\{ij\})$로 표현되며, 여기서 각 요소는 다음과 같이 정의된다.^[6][30][41]

:

여기서 $v\_i$는 정점, $e\_j$는 하이퍼에지를 나타낸다. 이 행렬의 전치 행렬 $I^t$는 원래 하이퍼그래프의 쌍대 하이퍼그래프를 정의한다.^[6]

방향 하이퍼그래프의 경우, 각 하이퍼에지 $e\_j$는 머리(head) $H(e\_j)$와 꼬리(tail) $T(e\_j)$를 가진다. 이 경우 접속 행렬 $I\; =\; (b\_\{ij\})$의 요소는 다음과 같이 정의된다.^[28]

:
인접 행렬(Adjacency matrix^영어)은 그래프의 인접 행렬을 일반화한 것으로, 하이퍼에지의 가중치를 나타내는 행렬이다. 일반적인 하이퍼그래프에서 하이퍼에지 $e\_\{k\; \backslash leq\; m\}$가 실수 가중치 $w\_\{e\_\{k\}\}\; \backslash in\; \backslash R$를 가질 때, 인접 행렬 $A\; =\; (a\_\{ij\})$는 다음과 같이 정의된다.

:
이분 그래프 표현 (사건 그래프): 하이퍼그래프 ''H''는 이분 그래프 ''BG''로 표현될 수 있다. ''X''와 ''E''는 ''BG''의 부분 집합이며, 정점 ''x₁''이 ''H''의 에지 ''e₁''에 포함되는 경우에만 (''x₁'', ''e₁'')은 에지로 연결된다. 이러한 이분 그래프는 사건 그래프라고도 불린다.

7. 사이클

일반적인 무방향 그래프는 사이클과 비순환 그래프라는 하나의 개념을 가지지만, 하이퍼그래프에서는 일반 그래프의 비순환성과 일치하는 여러 개의 서로 다른 비순환성 정의가 존재한다.^[29]

클로드 베르주는 하이퍼그래프의 인접 그래프(위에 정의된 이분 그래프)가 비순환적일 경우 베르주-비순환적이라는 정의를 제시했다.^[29] 하지만 이 정의는 매우 제한적이어서, 서로 다른 두 정점 $v\; \backslash neq\; v\text{'}$와 서로 다른 두 하이퍼에지 $f\; \backslash neq\; f\text{'}$에 대해 $v,\; v\text{'}\; \backslash in\; f$ 이고 $v,\; v\text{'}\; \backslash in\; f\text{'}$인 경우 베르주-사이클을 가진다. 베르주-사이클성은 인접 그래프를 탐색하여 선형 시간 안에 확인할 수 있다.

더 약한 개념의 하이퍼그래프 비순환성으로 α-비순환성이 있다.^[30] 이 개념은 하이퍼그래프가 컨포멀하고 (프라이멀 그래프의 모든 클릭이 일부 하이퍼에지에 의해 덮여 있음) 프라이멀 그래프가 현 그래프인 것과 동일하며, GYO 알고리즘(그레이엄의 알고리즘이라고도 함)^[31][32]을 통해 빈 그래프로 축소 가능한 것과 동일하다. 이는 귀의 일반화된 정의를 사용하여 하이퍼에지를 제거하는 합류 반복 프로세스이다. 데이터베이스 이론에서 기본 하이퍼그래프가 α-비순환적이면 데이터베이스 스키마가 특정 바람직한 속성을 가지며,^[33] 1차 논리의 가드 프래그먼트의 표현력과도 관련이 있다. 하이퍼그래프가 α-비순환적인지 여부는 선형 시간 안에 테스트할 수 있다.^[34]

α-비순환성은 α-사이클적인 하이퍼그래프에 하이퍼에지를 추가하면 α-비순환적이 될 수 있다는 직관에 반하는 속성을 가진다. 예를 들어, 하이퍼그래프의 모든 정점을 포함하는 하이퍼에지를 추가하면 항상 α-비순환적이 된다. 이러한 단점을 보완하기 위해 로널드 페이긴^[35]은 β-비순환성과 γ-비순환성이라는 더 강력한 개념을 정의했다. β-비순환성은 하이퍼그래프의 모든 서브하이퍼그래프가 α-비순환적이어야 한다는 조건으로, 그레이엄의 정의와 같다.^[32][35] γ-비순환성은 데이터베이스 스키마의 여러 바람직한 속성과 동일하며 바흐만 다이어그램과 관련된 더 제한적인 조건이다. β-비순환성과 γ-비순환성 모두 다항 시간 안에 테스트할 수 있다.

이 네 가지 비순환성 개념은 서로 비교 가능하다. 베르주-비순환성은 γ-비순환성을, γ-비순환성은 β-비순환성을, β-비순환성은 α-비순환성을 의미한다. 하지만 역은 성립하지 않아 네 가지 개념은 모두 다르다.^[35]

8. 동형, 대칭, 동일성

준동형 사상은 한 하이퍼그래프의 정점 집합에서 다른 하이퍼그래프로의 사상으로, 각 변이 다른 하나의 변으로 매핑되도록 하는 것이다.

하이퍼그래프 $H=(X,E)$가 하이퍼그래프 $G=(Y,F)$와 ''동형''이라는 것은 $H\; \backslash simeq\; G$로 표기하며, 다음 조건을 만족하는 전단사 함수 $\backslash phi:X\; \backslash to\; Y$가 존재함을 의미한다.

:$\backslash phi(e\_i)\; =\; f\_\{\backslash pi(i)\}$ (여기서 $\backslash pi$는 $I$의 순열)

이때, $\backslash phi$를 그래프의 동형 사상이라고 한다. $H\; \backslash simeq\; G$는 $H^*\; \backslash simeq\; G^*$와 동치이다.

하이퍼그래프의 변에 명시적으로 레이블이 지정된 경우, ''강력 동형''이라는 개념이 추가된다. $H$가 $G$와 ''강력 동형''이라는 것은 순열 $\backslash pi$가 항등원인 경우를 의미하며, $H\; \backslash cong\; G$로 표기한다. 모든 강력 동형 그래프는 동형이지만, 그 역은 성립하지 않는다.

하이퍼그래프의 정점에 명시적으로 레이블이 지정된 경우, ''동치''와 ''같음''의 개념이 있다. $H$가 $G$와 ''동치''라는 것은 $H\backslash equiv\; G$로 표기하며, 다음을 만족하는 동형 사상 $\backslash phi$가 존재함을 의미한다.

:$\backslash phi(x\_n)\; =\; y\_n$

:$\backslash phi(e\_i)\; =\; f\_\{\backslash pi(i)\}$

$H\backslash equiv\; G$는 $H^*\; \backslash cong\; G^*$와 동치이다.

또한, 순열 $\backslash pi$가 항등원일 경우, $H$는 $G$와 같다고 하며, $H=G$로 표기한다. 이러한 같음의 정의에 따르면, 그래프는 자기 쌍대적이다. 즉, $\backslash left(H^*\backslash right)\; ^*\; =\; H$이다.

하이퍼그래프 자기 동형 사상은 정점 집합에서 자기 자신으로의 동형 사상, 즉 정점의 재 레이블링이다. 하이퍼그래프 ''H'' (= (''X'', ''E''))의 자기 동형 사상의 집합은 군을 이루며, 합성 연산에 대해 닫혀 있다. 이를 하이퍼그래프의 자기 동형 군이라고 하며 Aut(''H'')로 표기한다.

예시로, 다음과 같은 변을 가진 하이퍼그래프 $H$와 $G$를 고려해 보자.

:$H\; =\; \backslash lbrace$

e_1 = \lbrace a,b \rbrace,

e_2 = \lbrace b,c \rbrace,

e_3 = \lbrace c,d \rbrace,

e_4 = \lbrace d,a \rbrace,

e_5 = \lbrace b,d \rbrace,

e_6 = \lbrace a,c \rbrace

\rbrace

:$G\; =\; \backslash lbrace$

f_1 = \lbrace \alpha,\beta \rbrace,

f_2 = \lbrace \beta,\gamma \rbrace,

f_3 = \lbrace \gamma,\delta \rbrace,

f_4 = \lbrace \delta,\alpha \rbrace,

f_5 = \lbrace \alpha,\gamma \rbrace,

f_6 = \lbrace \beta,\delta \rbrace

\rbrace

$H$와 $G$는 동형( $\backslash phi(a)=\backslash alpha$ 등)이지만 강하게 동형은 아니다. 예를 들어 $H$에서 정점 $a$는 변 1, 4, 6과 만나지만($e\_1\; \backslash cap\; e\_4\; \backslash cap\; e\_6\; =\; \backslash lbrace\; a\backslash rbrace$), 그래프 $G$에서는 변 1, 4, 6을 모두 만나는 정점이 존재하지 않는다($f\_1\; \backslash cap\; f\_4\; \backslash cap\; f\_6\; =\; \backslash varnothing$).

이 예에서 $H$와 $G$는 동치이며($H\backslash equiv\; G$), 이중 그래프는 강하게 동형이다($H^*\backslash cong\; G^*$).

하이퍼그래프 ''H''의 랭크 $r(H)$는 하이퍼그래프 내 모든 간선의 최대 크기이다.

두 정점 ''x''와 ''y''가 $\backslash phi(x)=y$를 만족하는 자기동형사상 $\backslash phi$가 존재하면 ''대칭적''이라고 한다. 두 간선 $e\_i$와 $e\_j$가 $\backslash phi(e\_i)=e\_j$를 만족하는 자기동형사상$\backslash phi$가 존재하면 ''대칭적''이라고 한다.

모든 정점이 대칭적이면 하이퍼그래프는 ''정점-추이적''(또는 ''정점-대칭적'')이다. 모든 간선이 대칭적이면 하이퍼그래프는 ''간선-추이적''이다. 하이퍼그래프가 간선-대칭적이고 정점-대칭적이면, ''추이적''이다.

하이퍼그래프 쌍대성에 의해, 간선-추이성에 대한 연구는 정점-추이성에 대한 연구와 동일하다.

9. 분할

E. 다우버의 분할 정리에 따르면, 변 추이적 하이퍼그래프 $H=(X,E)$에 대해, 정점 집합 $X$의 분할^[36]

:$(X\_1,\; X\_2,\backslash cdots,X\_K)$

이 존재하여, 각 $1\backslash le\; k\; \backslash le\; K$에 대해 $X\_k$에 의해 생성된 부분 하이퍼그래프 $H\_\{X\_k\}$가 추이적이며,

:$\backslash sum\_\{k=1\}^K\; r\backslash left(H\_\{X\_k\}\; \backslash right)\; =\; r(H)$

가 성립한다. 여기서 $r(H)$는 ''H''의 랭크이다.

따름 정리에 따르면, 정점 추이적이지 않은 변 추이적 하이퍼그래프는 이색적이다.

그래프 분할(특히 하이퍼그래프 분할)은 IC 설계^[37] 및 병렬 컴퓨팅에 많은 응용 분야를 가지고 있다.^[38][39][40] 효율적이고 확장 가능한 하이퍼그래프 분할 알고리즘은 머신 러닝 작업에서 대규모 하이퍼그래프를 처리하는 데에도 중요하다.^[41]

10. 채색

집합 \{1, 2, 3, ..., λ\}의 색상 중 하나를 하이퍼그래프의 모든 꼭짓점에 할당하여 각 하이퍼에지(hyperedge)가 서로 다른 색상의 꼭짓점을 최소한 두 개 이상 포함하도록 하는 것을 고전적인 하이퍼그래프 채색이라고 한다. 즉, 크기가 2 이상인 단색 하이퍼에지는 없어야 한다. 이러한 의미에서 이는 그래프 채색의 직접적인 일반화이다. 모든 채색에 사용된 최소 고유 색상 수를 하이퍼그래프의 채색 수라고 한다.

최대 ''k''개의 색상을 사용하여 채색이 존재하는 하이퍼그래프를 ''k-채색 가능''이라고 한다. 2-채색 가능한 하이퍼그래프는 정확히 이분 그래프이다.

고전적인 하이퍼그래프 채색의 일반화는 많다. 그중 하나는 단색 모서리가 허용될 때의 혼합 하이퍼그래프 채색이다. 일부 혼합 하이퍼그래프는 어떤 수의 색상으로도 채색할 수 없다. 채색 불가능성에 대한 일반적인 기준은 알려져 있지 않다. 혼합 하이퍼그래프가 채색 가능한 경우, 사용된 색상의 최소 및 최대 수를 각각 하한 및 상한 채색 수라고 한다.^[25]

하이퍼그래프의 채색은 다음과 같이 정의된다. H = (V, E)라는 하이퍼그래프에서 \Vert V\Vert = n이라고 한다. C = \{c₁, c₂, ..., c_n\}가 H의 타당한 채색이라는 것은, 모든 e \in E, \vert e\vert > 1에 대해 임의의 정점 v_i, v_j \in e에서 c_i \neq c_j가 되는 경우만을 의미한다.

11. 응용

무방향 하이퍼그래프는 만족 문제^[5], 데이터베이스^[30], 머신 러닝^[41], 슈타이너 트리 문제^[6] 등을 모델링하는 데 유용하다. 하이퍼그래프는 데이터 모델 및 분류기 정규화 (수학)로서 머신 러닝 작업에 광범위하게 사용되어 왔다.^[7] 응용 분야에는 추천 시스템(하이퍼에지로서의 커뮤니티)^[8][9], 이미지 검색(하이퍼에지로서의 상관 관계)^[10], 생물 정보학(하이퍼에지로서의 생화학적 상호 작용)^[11]이 있다. 대표적인 하이퍼그래프 학습 기술로는 하이퍼그래프 라플라시안으로 스펙트럼 그래프 이론을 확장한 하이퍼그래프 스펙트럼 클러스터링과 학습 결과를 제한하기 위해 추가적인 하이퍼그래프 구조적 비용을 도입하는 하이퍼그래프 반지도 학습이 있다.^[13] 대규모 하이퍼그래프의 경우, Apache Spark를 사용하여 구축된 분산 프레임워크도 사용할 수 있다.^[41]

방향 하이퍼그래프는 전화 애플리케이션^[14], 자금 세탁 탐지^[15], 운영 연구^[16], 운송 계획 등을 모델링하는 데 사용할 수 있다. 또한 혼 만족성을 모델링하는 데에도 사용할 수 있다.^[28]

12. 하이퍼그래프 그리기

하이퍼그래프는 그래프보다 종이에 그리기 어렵지만, 여러 연구자들이 하이퍼그래프 시각화 방법을 연구해왔다.

13. 그래프 개념의 확장

그래프와 관련된 많은 정리와 개념은 하이퍼그래프에도 적용된다. 특히 하이퍼그래프의 매칭, 하이퍼그래프의 정점 덮개(횡단이라고도 함), 하이퍼그래프의 선 그래프, 하이퍼그래프 문법, 램지 정리, 에르되시-코-라조 정리, 균일 하이퍼그래프에 대한 크루스칼-카토나 정리, 하이퍼그래프에 대한 홀 정리 등이 있다. 유향 하이퍼그래프에서는 추이 폐쇄와 최단 경로 문제도 확장 적용된다.^[16]

램지의 정리가 대표적인 예로, 그래프 이론의 많은 정리는 하이퍼그래프에서도 성립한다. 그래프의 대칭성에 관한 연구도 하이퍼그래프로 확장하여 적용 가능하다. 하이퍼그래프에서 준동형은 어떤 하이퍼그래프의 정점 집합에서 다른 정점 집합으로의 사상이 존재하고, 하나의 에지가 다른 쪽의 에지에 대응하는 것을 의미한다. 동형은 반대 방향으로도 준동형인 경우를 말한다. 자기동형은 정점 집합이 라벨을 다시 붙인 정점 집합과 준동형임을 말한다. 하이퍼그래프의 자기동형 집합 ''H'' (= (''X'', ''E''))은 합성에 대해 군이 되고, 하이퍼그래프의 자기동형군이라고 불리며 Aut(''H'')로 표시된다. 하이퍼그래프의 모임은 사상으로서의 하이퍼그래프 준동형의 모임으로 이루어진 범주이다.

하이퍼그래프 ''H'' = (''X'', ''E'')의 "횡단(transversal)" 또는 "히팅 세트(hitting set)" $T\backslash subseteq\; X$는 어느 에지든 교집합이 공집합이 아닌 집합을 말한다. 즉, T와 각 에지 사이에 공통적인 노드가 반드시 존재한다. 횡단 ''T''는 그 진부분 집합으로서 횡단이라고 부를 수 있는 것이 없는 경우에 "최소"라고 한다. ''H''의 "횡단 하이퍼그래프"는 (''X'', ''F'')로 표시되는 하이퍼그래프이며, ''F''는 ''H''의 전체 최소 횡단으로 이루어진다. 횡단 하이퍼그래프의 계산은 기계 학습 등의 컴퓨터 과학 분야에서 응용되고 있으며, 게임 이론, 데이터베이스의 인덱스화, 충족 가능성 문제, 최적화 등과 관련된다.

각 에지의 농도(원소의 개수)가 ''k''인 하이퍼그래프를 "k-균일(k-uniform)" 또는 "k-하이퍼그래프(k-hypergraph)"라고 부른다. 그래프는 2-균일 하이퍼그래프이다. 정점 ''v''의 차수 ''d(v)''는 그 정점이 속하는 에지의 개수이다. 모든 정점의 차수가 ''k''인 하이퍼그래프를 "k-정규(k-regular)"라고 한다.

$V\; =\; \backslash \{v\_1,\; v\_2,\; ~\backslash ldots,\; ~\; v\_n\backslash \}$과 $E\; =\; \backslash \{e\_1,\; e\_2,\; ~\; \backslash ldots,\; ~\; e\_m\backslash \}$이 있다고 가정하면, 모든 하이퍼그래프에는 $n\; \backslash times\; m$의 "접속 행렬" $A\; =\; (a\_\{ij\})$가 있으며, 다음이 성립한다.

:

접속 행렬의 전치 행렬 $A^t$에 의해 정의되는 하이퍼그래프 $H^*\; =\; (V^*,\; E^*)$를 $H$의 "쌍대(dual)"라고 하며, $V^*$는 ''m''개의 원소로 이루어진 집합, $E^*$는 ''n''개의 $V^*$의 부분 집합으로 이루어진 집합이다. $v^*\_j\; \backslash in\; V^*$과 $e^*\_i\; \backslash in\; E^*$에 대해 $a\_\{ij\}\; =\; 1$일 때만 $~\; v^*\_j\; \backslash in\; e^*\_i$이다. 균일 하이퍼그래프의 쌍대는 정규이며, 역도 성립한다. 쌍대를 고려함으로써 새로운 발견이 많다.

14. 추가 일반화

하이퍼그래프의 한 가지 가능한 일반화는 간선이 다른 간선을 가리키도록 허용하는 것이다. 이 일반화에는 두 가지 변형이 있다.

한 가지는 간선이 정점의 집합뿐만 아니라 정점의 부분 집합, 정점의 부분 집합의 부분 집합 등을 ''무한정'' 포함할 수 있다는 것이다. 본질적으로 모든 간선은 트리 또는 방향 비순환 그래프의 내부 노드이며 정점은 잎 노드이다. 하이퍼그래프는 공통으로 공유된 노드(즉, 주어진 내부 노드 또는 잎이 여러 다른 트리에 나타날 수 있음)가 있는 트리의 모음일 뿐이다. 반대로, 트리의 모든 모음은 이러한 일반화된 하이퍼그래프로 이해할 수 있다. 트리는 컴퓨터 과학 및 다른 많은 수학 분야에서 널리 사용되기 때문에 하이퍼그래프가 자연스럽게 나타난다고 말할 수 있다. 예를 들어, 이러한 일반화는 항 대수의 모델로 자연스럽게 발생한다. 간선은 항에 해당하고 정점은 상수 또는 변수에 해당한다.

이러한 하이퍼그래프의 경우 집합 구성원은 순서를 제공하지만, 순서는 부분 순서도 전순서도 아니다. 이는 전이적이지 않기 때문이다. 이 일반화의 레비 그래프에 해당하는 그래프는 방향 비순환 그래프이다. 예를 들어, 정점 집합이 $V=\; \backslash \{a,b\backslash \}$이고 간선이 $e\_1=\backslash \{a,b\backslash \}$ 및 $e\_2=\backslash \{a,e\_1\backslash \}$인 일반화된 하이퍼그래프를 생각해 보자. 그러면 $b\backslash in\; e\_1$이고 $e\_1\backslash in\; e\_2$이지만 $b\backslash in\; e\_2$는 사실이 아니다. 그러나 이러한 하이퍼그래프에 대한 집합 구성원의 전이적 폐포는 부분 순서를 유도하고 하이퍼그래프를 부분 순서 집합으로 "평탄화"한다.

또는 간선이 방향, 비순환 그래프로 간선이 정렬되어야 한다는 요구 사항과 상관없이 다른 간선을 가리키도록 허용할 수 있다. 이를 통해 정점이 전혀 포함될 필요가 없는 간선 루프가 있는 그래프를 허용할 수 있다. 예를 들어, 두 개의 간선 $e\_1$과 $e\_2$ 및 0개의 정점으로 구성된 일반화된 하이퍼그래프를 생각해 보자. $e\_1\; =\; \backslash \{e\_2\backslash \}$이고 $e\_2\; =\; \backslash \{e\_1\backslash \}$이다. 이 루프는 무한히 재귀적이므로 간선인 집합은 기초 공리를 위반한다. 특히, 이러한 하이퍼그래프에 대한 집합 구성원의 전이적 폐포는 없다. 이러한 구조는 처음에는 이상하게 보일 수 있지만, 해당 레비 그래프의 동등한 일반화가 더 이상 이분 그래프가 아닌 일반 방향 그래프일 뿐이라는 점에 유의하면 쉽게 이해할 수 있다.

이러한 하이퍼그래프에 대한 일반화된 인접 행렬은 정의상 정방 행렬이며, 정점과 간선의 총 개수와 같은 랭크를 갖는다. 따라서 위의 예에서 인접 행렬은 다음과 같다.

:

참조

_[1] 논문 Analyzing Dynamic Hypergraphs with Parallel Aggregated Ordered Hypergraph Visualization https://hal.inria.fr[...] IEEE 2020
_[2] arXiv Hypergraphs: an introduction and review
_[3] citation ε-nets and simplex range queries
_[4] 서적 Heuristics: Intelligent Search Strategies for Computer Problem Solving https://books.google[...] Addison-Wesley Publishing Company 2021-06-12
_[5] 간행물 Witnesses for non-satisfiability of dense random 3CNF formulas https://ieeexplore.i[...] IEEE 2021-01-20
_[6] 서적 Optimal Interconnection Trees in the Plane Springer 2021-01-20
_[7] citation Advances in Neural Information Processing Systems MIT Press 2021-07-24
_[8] citation Random Hypergraphs and their applications 2009
_[9] citation Using rich social media information for music recommendation via hypergraph model https://www.research[...] 2011-10
_[10] citation Hypergraph with sampling for image retrieval
_[11] citation Predicting protein interactions via parsimonious network history inference
_[12] citation Visual-textual joint relevance learning for tag-based social image search http://ink.library.s[...] 2017-09-22
_[13] citation A hypergraph-based learning algorithm for classifying gene expression and arrayCGH data with prior knowledge
_[14] 논문 A Directed Hypergraph Database: A Model for the Local Loop Telephone Plant https://archive.org/[...] 1982
_[15] 간행물 Exchange Pattern Mining in the Bitcoin Transaction Directed Hypergraph http://fc17.ifca.ai/[...] Springer 2021-01-20
_[16] 논문 Directed hypergraphs: Introduction and fundamental algorithms - A survey 2017
_[17] citation Proc. 11th International Symposium on Graph Drawing (GD 2003) Springer 2010-05-17
_[18] citation Orthogonal hypergraph drawing for improved visibility http://jgaa.info/acc[...] 2010-05-17
_[19] citation How to draw a hypergraph
_[20] citation Graph Drawing Springer-Verlag
_[21] citation Database and Expert Systems Applications Springer International Publishing
_[22] citation Graph Drawing Springer-Verlag
_[23] citation Hypergraph planarity and the complexity of drawing Venn diagrams
_[24] citation Graph Drawing Springer-Verlag
_[25] 웹사이트 Vitaly Voloshin: Mixed Hypergraph Coloring Website http://spectrum.troy[...] 2022-04-27
_[26] 논문 Degrees of acyclicity for hypergraphs and relational database schemes 1983-07-01
_[27] Citation Matching Theory North-Holland
_[28] 논문 Directed hypergraphs and applications
_[29] 서적 Graphs and Hypergraphs North-Holland
_[30] 논문 On the Desirability of Acyclic Database Schemes http://cse.unl.edu/~[...] 2021-01-03
_[31] 논문 An algorithm for tree-query membership of a distributed query https://www.computer[...] 2018-09-02
_[32] 논문 On the universal relation University of Toronto
_[33] 서적 Foundations of Databases Addison-Wesley
_[34] 논문 Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs
_[35] 논문 Degrees of Acyclicity for Hypergraphs and Relational Database Schemes
_[36] 서적 Graph Theory https://books.google[...] CRC Press 2018
_[37] 간행물 Multilevel hypergraph partitioning: applications in VLSI domain 1999-03
_[38] 간행물 Graph partitioning models for parallel computing https://digital.libr[...] 2000
_[39] 학회자료 A Hypergraph Model for Mapping Repeated Sparse Matrix–Vector Product Computations onto Multicomputers
_[40] 간행물 Hypergraph-Partitioning Based Decomposition for Parallel Sparse-Matrix Vector Multiplication
_[41] 서적 2015 IEEE International Conference on Data Mining https://www.ruizhang[...] 2015