📂그래프이론

하이퍼그래프의 정의

정의

1. 어떤 유한집합 $V \ne \emptyset$ 을 하이퍼버텍스 셋^{hypervertex set}이라 한다.
2. 하이퍼에지^hyperedge란 하이퍼버텍스 셋의 부분집합을 말하고, 하이퍼에지의 집합 $E$ 를 하이퍼에지 셋^{hyperedge set}이라 한다. 다시 말해, 하이퍼에지 셋이란 하이퍼버텍스 셋의 멱집합의 부분집합 $E \subset 2^{V}$ 로써 정의될 수 있다.
3. 하이퍼버텍스와 하이퍼에지의 페어 $G = (V, E)$ 를 하이퍼그래프^hypergraph라 한다.

설명 ¹

쉽게 말해 하이퍼그래프란 ‘둘 간의 관계’에 관심을 가지는 그래프를 넘어 ‘다자 간의 관계’에 관계를 가지는 개념이다. 예를 들어 인적 네트워크에서 $A$ 와 $B$, $B$ 와 $C$ 는 개인적으로 만나는데, $B$ 가 없을 때 $A, C$ 가 만나지 않아도 $B$ 가 있을 땐 셋이서 만난다면 $A, B, C$ 는 기수 $3$ 의 하이퍼에지로 묶여있는 것으로 본다.

하이퍼그래프는 그 자유분방한 정의에서 알 수 있듯, 단순히 그래프의 일반화라기 보단 집합 혹은 데이터라고 하는 것을 새롭게 표현하는 것에 가깝다. 점과 선으로 시각화할 수 있는 그래프와 달리 상상하기부터 쉽지가 않고, 또 그런만큼 반대로 복잡한 대상에 대한 새로운 관점을 주기도 한다.

당연히 응용수학 분야에서 큰 각광을 받고 있으나, 하이퍼그래프 그 자체에 대한 이론적인 연구는 그래프이론의 틀을 잘 유지하면서 확장하기가 쉽지 않다고 한다. 가장 먼저 떠올릴 수 있는 인접행렬과 같은 개념조차도 텐서가 나와야 할 정도니 당연한 일이다.