초그래프 문서 원본 보기

{{위키데이터 속성 추적}}
[[파일:Hypergraph-wikipedia.svg|섬네일|하이퍼그래프의 예]]
[[그래프 이론]]에서, '''초그래프'''({{llang|en|hypergraph|하이퍼그래프}})는 한 변이 여러 꼭짓점을 연결할 수 있는, [[그래프 (그래프 이론)|그래프]]의 일반화이다. [[전자공학]]에서는 게이트와 넷으로 구성된 디지털 회로를 꼭짓점과 원, 점선 등으로 알기 쉽게 표현하고 이것으로 회로를 분석에 사용한다.

== 정의 ==
'''초그래프''' <math>H=(V,E)</math>는 다음과 같은 데이터로 주어진다.
* 집합 <math>V</math>. 그 원소를 '''꼭짓점'''이라고 한다.
* <math>E\subseteq\mathcal P(V)</math>. 그 원소를 '''초변'''({{llang|en|hyperedge|하이퍼에지}})이라고 한다. <math>e\in E</math>의 원소를 <math>e</math>의 '''끝점'''({{llang|en|endpoint}})이라고 한다. 하나의 끝점만을 갖는 변을 '''고리'''({{llang|en|loop}})라고 한다.

두 초그래프 <math>H=(V,E)</math>와 <math>H'=(V',E')</math> 사이의 '''사상'''은 다음 조건을 만족시키는 함수 <math>f\colon V\to V'</math>이다.
* 임의의 <math>e\in E</math>에 대하여, <math>f[e]\in E'</math>

'''유향 초그래프'''({{llang|en|directed hypergraph}}) <math>H=(V,E)</math>는 다음과 같은 데이터로 주어진다.
* 집합 <math>V</math>. 그 원소를 '''꼭짓점'''이라고 한다.
* <math>E\subseteq\mathcal P(V)\times\mathcal P(V)</math>. 그 원소를 '''초호'''({{llang|en|hyperarc|하이퍼아크}})이라고 한다. <math>e</math>의 첫 번째 성분의 원소를 <math>e</math>의 '''시점'''({{llang|en|source}}), <math>e</math>의 두 번째 성분의 원소를 <math>e</math>의 '''종점'''({{llang|en|target}})이라고 한다.

두 유향 초그래프 <math>H=(V,E)</math>와 <math>H'=(V',E')</math> 사이의 '''사상'''은 다음 조건을 만족시키는 함수 <math>f\colon V\to V'</math>이다.
* 임의의 <math>(e_1,e_2)\in E</math>에 대하여, <math>(f[e_1],f[e_2])\in E'</math>

=== 다중 초그래프 ===
'''다중 초그래프'''({{llang|en|multihypergraph}}) <math>H=(V,E,\partial)</math>는 다음과 같은 데이터로 주어진다.<ref name="Bretto">{{서적 인용|성=Bretto|이름=Alain|제목=Hypergraph theory. An introduction|언어=en|총서=Mathematical Engineering|출판사=Springer|위치=[[함 (스위스)|함]]|날짜=2013|isbn=978-3-319-00079-4|issn=2192-4732|doi=10.1007/978-3-319-00080-0|zbl=1269.05082|lccn=2013932774}}</ref>{{rp|1, §1.1}}
* 집합 <math>V</math>. 그 원소를 '''꼭짓점'''이라고 한다.
* 집합 <math>E</math>. 그 원소를 '''초변'''이라고 한다.
* 함수 <math>\partial\colon E\to\mathcal P(V)</math>. <math>\partial e</math>의 원소를 <math>e</math>의 '''끝점'''이라고 한다. 하나의 끝점만을 갖는 변을 '''고리'''라고 한다.

두 다중 초그래프 <math>H=(V,E,\partial)</math>와 <math>H'=(V,E,\partial')</math> 사이의 '''사상''' <math>(f,g)</math>는 다음과 같은 데이터로 주어진다.
* 함수 <math>f\colon V\to V'</math>
* 함수 <math>g\colon E\to E'</math>
이는 다음 조건을 만족시켜야 한다.
* <math>f\circ\partial=\partial'\circ g</math>

범주론적으로, 다중 초그래프와 그 사상의 범주 <math>\operatorname{MHGraph}</math>는 [[쉼표 범주]]
:<math>\operatorname{MHGraph}=\operatorname{Set}\downarrow\mathcal P</math>
이다.<ref name="Jäkel">{{arXiv 인용|성=Jäkel|이름=Christian|제목=A coalgebraic model of graphs|언어=en|날짜=2015|전자문서=1508.02169|분류=math.CO|id={{doi 2|10.48550/arXiv.1508.02169}}}}</ref>{{rp|1, Example 1.1}} 여기서 [[자기 함자]] <math>\mathcal P\colon\operatorname{Set}\to\operatorname{Set}</math>는 [[멱집합]] [[자기 함자]]
:<math>\mathcal P(V)=\{S\colon S\subseteq V\}</math>
:<math>\mathcal P(f)\colon S\mapsto f(S)</math>
이다.

'''유향 다중 초그래프'''({{llang|en|directed multihypergraph}}) <math>H=(V,E,s,t)</math>는 다음과 같은 데이터로 주어진다.<ref name="Bretto"/>{{rp|95, §6.1}}
* 집합 <math>V</math>. 그 원소를 '''꼭짓점'''이라고 한다.
* 집합 <math>E</math>. 그 원소를 '''초호'''라고 한다.
* 함수 <math>s\colon E\to\mathcal P(V)</math>. <math>s(e)</math>의 원소를 <math>e</math>의 '''시점'''이라고 한다.
* 함수 <math>t\colon E\to\mathcal P(V)</math>. <math>s(e)</math>의 원소를 <math>e</math>의 '''종점'''이라고 한다.

두 유향 다중 초그래프 <math>H=(V,E,s,t)</math>와 <math>H'=(V',E',s',t')</math> 사이의 '''사상''' <math>(f,g)</math>는 다음과 같은 데이터로 주어진다.
* 함수 <math>f\colon V\to V'</math>
* 함수 <math>g\colon E\to E'</math>
이는 다음 두 조건을 만족시켜야 한다.
* <math>f\circ s=s'\circ g</math>
* <math>f\circ t=t'\circ g</math>

범주론적으로, 유향 다중 초그래프와 그 사상의 범주 <math>\operatorname{DMHGraph}</math>는 [[쉼표 범주]]
:<math>\operatorname{DMHGraph}=\operatorname{Set}\downarrow\mathcal P\times\mathcal P</math>
이다.<ref name="Jäkel"/>{{rp|1, Example 1.1}} 여기서 [[자기 함자]] <math>\mathcal P\times\mathcal P\colon\operatorname{Set}\to\operatorname{Set}</math>는 두 멱집합 자기 함자 <math>\mathcal P\colon\operatorname{Set}\to\operatorname{Set}</math>의 [[화살표 범주]] <math>\operatorname{Set}^\rightarrow</math>에서의 [[곱 (범주론)|곱]]이다.

== 같이 보기 ==
* [[전자 설계 자동화]]

== 참고 문헌 ==
<references/>

== 외부 링크 ==
* {{eom|제목=Hypergraph}}
* {{매스월드|id=Hypergraph|제목=Hypergraph}}
* {{매스월드|id=Hyperedge|제목=Hyperedge}}
* {{nlab|id=hypergraph|제목=Hypergraph}}
* {{nlab|id=hypergraph category|제목=Hypergraph category}}
* {{플래닛매스|urlname=hypergraph|제목=Hypergraph}}

{{전거 통제}}
{{토막글|공학}}

[[분류:그래프 이론]]
[[분류:전자공학]]
[[분류:전자 설계 자동화]]
[[분류:집합족]]