초그래프

하이퍼그래프의 예

그래프 이론에서, 초그래프(영어: hypergraph 하이퍼그래프^[*])는 한 변이 여러 꼭짓점을 연결할 수 있는, 그래프의 일반화이다. 전자공학에서는 게이트와 넷으로 구성된 디지털 회로를 꼭짓점과 원, 점선 등으로 알기 쉽게 표현하고 이것으로 회로를 분석에 사용한다.

정의

초그래프 $H=(V,E)$는 다음과 같은 데이터로 주어진다.

• 집합 $V$. 그 원소를 꼭짓점이라고 한다.
• $E\subseteq {\mathcal {P}}(V)$. 그 원소를 초변(영어: hyperedge 하이퍼에지^[*])이라고 한다. $e\in E$의 원소를 $e$의 끝점(영어: endpoint)이라고 한다. 하나의 끝점만을 갖는 변을 고리(영어: loop)라고 한다.

두 초그래프 $H=(V,E)$와 $H'=(V',E')$ 사이의 사상은 다음 조건을 만족시키는 함수 $f\colon V\to V'$이다.

• 임의의 $e\in E$에 대하여, $f[e]\in E'$

유향 초그래프(영어: directed hypergraph) $H=(V,E)$는 다음과 같은 데이터로 주어진다.

• 집합 $V$. 그 원소를 꼭짓점이라고 한다.
• $E\subseteq {\mathcal {P}}(V)\times {\mathcal {P}}(V)$. 그 원소를 초호(영어: hyperarc 하이퍼아크^[*])이라고 한다. $e$의 첫 번째 성분의 원소를 $e$의 시점(영어: source), $e$의 두 번째 성분의 원소를 $e$의 종점(영어: target)이라고 한다.

두 유향 초그래프 $H=(V,E)$와 $H'=(V',E')$ 사이의 사상은 다음 조건을 만족시키는 함수 $f\colon V\to V'$이다.

• 임의의 $(e_{1},e_{2})\in E$에 대하여, $(f[e_{1}],f[e_{2}])\in E'$

다중 초그래프

다중 초그래프(영어: multihypergraph) $H=(V,E,\partial )$는 다음과 같은 데이터로 주어진다.^{:1, §1.1}

• 집합 $V$. 그 원소를 꼭짓점이라고 한다.
• 집합 $E$. 그 원소를 초변이라고 한다.
• 함수 $\partial \colon E\to {\mathcal {P}}(V)$. $\partial e$의 원소를 $e$의 끝점이라고 한다. 하나의 끝점만을 갖는 변을 고리라고 한다.

두 다중 초그래프 $H=(V,E,\partial )$와 $H'=(V,E,\partial ')$ 사이의 사상 $(f,g)$는 다음과 같은 데이터로 주어진다.

• 함수 $f\colon V\to V'$
• 함수 $g\colon E\to E'$

이는 다음 조건을 만족시켜야 한다.

• $f\circ \partial =\partial '\circ g$

범주론적으로, 다중 초그래프와 그 사상의 범주 $\operatorname {MHGraph}$는 쉼표 범주

$\operatorname {MHGraph} =\operatorname {Set} \downarrow {\mathcal {P}}$

이다.^{:1, Example 1.1} 여기서 자기 함자 ${\mathcal {P}}\colon \operatorname {Set} \to \operatorname {Set}$는 멱집합 자기 함자

${\mathcal {P}}(V)=\{S\colon S\subseteq V\}$

${\mathcal {P}}(f)\colon S\mapsto f(S)$

이다.

유향 다중 초그래프(영어: directed multihypergraph) $H=(V,E,s,t)$는 다음과 같은 데이터로 주어진다.^{:95, §6.1}

• 집합 $V$. 그 원소를 꼭짓점이라고 한다.
• 집합 $E$. 그 원소를 초호라고 한다.
• 함수 $s\colon E\to {\mathcal {P}}(V)$. $s(e)$의 원소를 $e$의 시점이라고 한다.
• 함수 $t\colon E\to {\mathcal {P}}(V)$. $s(e)$의 원소를 $e$의 종점이라고 한다.

두 유향 다중 초그래프 $H=(V,E,s,t)$와 $H'=(V',E',s',t')$ 사이의 사상 $(f,g)$는 다음과 같은 데이터로 주어진다.

• 함수 $f\colon V\to V'$
• 함수 $g\colon E\to E'$

이는 다음 두 조건을 만족시켜야 한다.

• $f\circ s=s'\circ g$
• $f\circ t=t'\circ g$

범주론적으로, 유향 다중 초그래프와 그 사상의 범주 $\operatorname {DMHGraph}$는 쉼표 범주

$\operatorname {DMHGraph} =\operatorname {Set} \downarrow {\mathcal {P}}\times {\mathcal {P}}$

이다.^{:1, Example 1.1} 여기서 자기 함자 ${\mathcal {P}}\times {\mathcal {P}}\colon \operatorname {Set} \to \operatorname {Set}$는 두 멱집합 자기 함자 ${\mathcal {P}}\colon \operatorname {Set} \to \operatorname {Set}$의 화살표 범주 $\operatorname {Set} ^{\rightarrow }$에서의 곱이다.

같이 보기

• 전자 설계 자동화

외부 링크

• “Hypergraph”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4. 
• Weisstein, Eric Wolfgang. “Hypergraph”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• Weisstein, Eric Wolfgang. “Hyperedge”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• “Hypergraph”. 《nLab》 (영어). 
• “Hypergraph category”. 《nLab》 (영어). 
• “Hypergraph”. 《PlanetMath》 (영어).