초그래프
그래프 이론에서, 초그래프(틀:Llang)는 한 변이 여러 꼭짓점을 연결할 수 있는, 그래프의 일반화이다. 전자공학에서는 게이트와 넷으로 구성된 디지털 회로를 꼭짓점과 원, 점선 등으로 알기 쉽게 표현하고 이것으로 회로를 분석에 사용한다.
정의
초그래프 는 다음과 같은 데이터로 주어진다.
- 집합 . 그 원소를 꼭짓점이라고 한다.
- . 그 원소를 초변(틀:Llang)이라고 한다. 의 원소를 의 끝점(틀:Llang)이라고 한다. 하나의 끝점만을 갖는 변을 고리(틀:Llang)라고 한다.
두 초그래프 와 사이의 사상은 다음 조건을 만족시키는 함수 이다.
- 임의의 에 대하여,
유향 초그래프(틀:Llang) 는 다음과 같은 데이터로 주어진다.
- 집합 . 그 원소를 꼭짓점이라고 한다.
- . 그 원소를 초호(틀:Llang)이라고 한다. 의 첫 번째 성분의 원소를 의 시점(틀:Llang), 의 두 번째 성분의 원소를 의 종점(틀:Llang)이라고 한다.
두 유향 초그래프 와 사이의 사상은 다음 조건을 만족시키는 함수 이다.
- 임의의 에 대하여,
다중 초그래프
다중 초그래프(틀:Llang) 는 다음과 같은 데이터로 주어진다.[1]틀:Rp
- 집합 . 그 원소를 꼭짓점이라고 한다.
- 집합 . 그 원소를 초변이라고 한다.
- 함수 . 의 원소를 의 끝점이라고 한다. 하나의 끝점만을 갖는 변을 고리라고 한다.
두 다중 초그래프 와 사이의 사상 는 다음과 같은 데이터로 주어진다.
- 함수
- 함수
이는 다음 조건을 만족시켜야 한다.
범주론적으로, 다중 초그래프와 그 사상의 범주 는 쉼표 범주
이다.[2]틀:Rp 여기서 자기 함자 는 멱집합 자기 함자
이다.
유향 다중 초그래프(틀:Llang) 는 다음과 같은 데이터로 주어진다.[1]틀:Rp
- 집합 . 그 원소를 꼭짓점이라고 한다.
- 집합 . 그 원소를 초호라고 한다.
- 함수 . 의 원소를 의 시점이라고 한다.
- 함수 . 의 원소를 의 종점이라고 한다.
두 유향 다중 초그래프 와 사이의 사상 는 다음과 같은 데이터로 주어진다.
- 함수
- 함수
이는 다음 두 조건을 만족시켜야 한다.
범주론적으로, 유향 다중 초그래프와 그 사상의 범주 는 쉼표 범주
이다.[2]틀:Rp 여기서 자기 함자 는 두 멱집합 자기 함자 의 화살표 범주 에서의 곱이다.