초그래프

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

하이퍼그래프의 예

정의

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

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

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

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

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

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

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

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

다중 초그래프

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

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

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

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

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

• ${\displaystyle f\circ \partial =\partial '\circ g}$

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

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

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

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

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

이다.

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

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

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

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

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

• ${\displaystyle f\circ s=s'\circ g}$
• ${\displaystyle f\circ t=t'\circ g}$

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

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

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

같이 보기

• 전자 설계 자동화