초그래프

testwiki
둘러보기로 이동 검색으로 이동

틀:위키데이터 속성 추적

하이퍼그래프의 예

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

정의

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

  • 집합 V. 그 원소를 꼭짓점이라고 한다.
  • E⊆𝒫(V). 그 원소를 초변(틀:Llang)이라고 한다. e∈E의 원소를 e의 끝점(틀:Llang)이라고 한다. 하나의 끝점만을 갖는 변을 고리(틀:Llang)라고 한다.

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

  • 임의의 e∈E에 대하여, f[e]∈E′

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

  • 집합 V. 그 원소를 꼭짓점이라고 한다.
  • E⊆𝒫(V)×𝒫(V). 그 원소를 초호(틀:Llang)이라고 한다. e의 첫 번째 성분의 원소를 e의 시점(틀:Llang), e의 두 번째 성분의 원소를 e의 종점(틀:Llang)이라고 한다.

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

  • 임의의 (e1,e2)∈E에 대하여, (f[e1],f[e2])∈E′

다중 초그래프

다중 초그래프(틀:Llang) H=(V,E,∂)는 다음과 같은 데이터로 주어진다.[1]틀:Rp

  • 집합 V. 그 원소를 꼭짓점이라고 한다.
  • 집합 E. 그 원소를 초변이라고 한다.
  • 함수 ∂:E→𝒫(V). ∂e의 원소를 e의 끝점이라고 한다. 하나의 끝점만을 갖는 변을 고리라고 한다.

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

  • 함수 f:V→V′
  • 함수 g:E→E′

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

  • f∘∂=∂′∘g

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

MHGraph⁡=Set⁡↓𝒫

이다.[2]틀:Rp 여기서 자기 함자 𝒫:Set⁡→Set는 멱집합 자기 함자

𝒫(V)={S:S⊆V}
𝒫(f):S↦f(S)

이다.

유향 다중 초그래프(틀:Llang) H=(V,E,s,t)는 다음과 같은 데이터로 주어진다.[1]틀:Rp

  • 집합 V. 그 원소를 꼭짓점이라고 한다.
  • 집합 E. 그 원소를 초호라고 한다.
  • 함수 s:E→𝒫(V). s(e)의 원소를 e의 시점이라고 한다.
  • 함수 t:E→𝒫(V). s(e)의 원소를 e의 종점이라고 한다.

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

  • 함수 f:V→V′
  • 함수 g:E→E′

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

  • f∘s=s′∘g
  • f∘t=t′∘g

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

DMHGraph⁡=Set⁡↓𝒫×𝒫

이다.[2]틀:Rp 여기서 자기 함자 𝒫×𝒫:Set⁡→Set는 두 멱집합 자기 함자 𝒫:Set⁡→Set의 화살표 범주 Set→에서의 곱이다.

같이 보기

참고 문헌

  1. ↑ 1.0 1.1 틀:서적 인용
  2. ↑ 2.0 2.1 틀:ArXiv 인용

외부 링크

틀:전거 통제 틀:토막글

원본 주소 "https://ko.wiki.beta.math.wmflabs.org/w/index.php?title=초그래프&oldid=3454"