초그래프

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

 정의 
초그래프 는 다음과 같은 데이터로 주어진다.
 집합 . 그 원소를 꼭짓점이라고 한다.
 . 그 원소를 초변()이라고 한다. 의 원소를 의 끝점()이라고 한다. 하나의 끝점만을 갖는 변을 고리()라고 한다.

두 초그래프 와  사이의 사상은 다음 조건을 만족시키는 함수 이다.
 임의의 에 대하여, 

유향 초그래프() 는 다음과 같은 데이터로 주어진다.
 집합 . 그 원소를 꼭짓점이라고 한다.
 . 그 원소를 초호()이라고 한다. 의 첫 번째 성분의 원소를 의 시점(), 의 두 번째 성분의 원소를 의 종점()이라고 한다.

두 유향 초그래프 와  사이의 사상은 다음 조건을 만족시키는 함수 이다.
 임의의 에 대하여, 

 다중 초그래프 
다중 초그래프() 는 다음과 같은 데이터로 주어진다.
 집합 . 그 원소를 꼭짓점이라고 한다.
 집합 . 그 원소를 초변이라고 한다.
 함수 . 의 원소를 의 끝점이라고 한다. 하나의 끝점만을 갖는 변을 고리라고 한다.

두 다중 초그래프 와  사이의 사상 는 다음과 같은 데이터로 주어진다.
 함수 
 함수 
이는 다음 조건을 만족시켜야 한다.


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

이다. 여기서 자기 함자 는 멱집합 자기 함자

이다.

유향 다중 초그래프() 는 다음과 같은 데이터로 주어진다.
 집합 . 그 원소를 꼭짓점이라고 한다.
 집합 . 그 원소를 초호라고 한다.
 함수 . 의 원소를 의 시점이라고 한다.
 함수 . 의 원소를 의 종점이라고 한다.

두 유향 다중 초그래프 와  사이의 사상 는 다음과 같은 데이터로 주어진다.
 함수 
 함수 
이는 다음 두 조건을 만족시켜야 한다.



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

이다. 여기서 자기 함자 는 두 멱집합 자기 함자 의 화살표 범주 에서의 곱이다.

 같이 보기 
 전자 설계 자동화

 참고 문헌 

 외부 링크 







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