그래프 연산
Graph operations그래프 연산은 초기 그래프에서 새로운 그래프를 만든다.다음과 같은 주요 범주로 구분할 수 있다.
단항작업
단항 연산은 단일 초기 그래프에서 새 그래프를 생성한다.
기본 운영
그래프 편집 작업이라고도 하는 기본 작업 또는 편집 작업은 정점 또는 에지의 추가 또는 삭제, 정점의 병합 및 분할, 에지 수축 등과 같은 간단한 로컬 변경에 의해 초기 한 개에서 새로운 그래프를 만든다.그래프 쌍 간의 그래프 편집 거리는 한 그래프를 다른 그래프로 변환하는 데 필요한 최소 기본 작업 수입니다.
고급 작업
고급 연산은 다음과 같은 복잡한 변경에 의해 처음부터 새로운 그래프를 생성한다.
이진 연산
이항 연산은 다음과1 같은 두 개의 초기 그래프 G = (V11, E)와 G2 = (V2, E2)에서 새로운 그래프를 만든다.
- 그래프 조합: G1 ∪ G2. 두 가지 정의가 있다.가장 일반적인 것, 즉 그래프의 분리 결합에서, 그 결합은 해체된 것으로 가정된다.덜 일반적으로(수학에서 조합의 일반적 정의와 더 일관성이 있지만), 두 그래프의 결합은 그래프(V1 v V2, E1 e2 E)로 정의된다.
- 그래프 교차로: G1 ∩ G2 = (V11 ∩ V2, E ∩ E2);[1]
- 그래프 조인: 첫 번째 그래프의 정점과 두 번째 그래프의 정점을 연결하는 모든 가장자리가 있는 그래프.이것은 (표시가 없는 그래프의 경우) 정류 연산이다.[2]
- 정점 집합의 데카르트 곱을 기준으로 제품을 그래프로 표시:
- 데카르트 그래프 제품: 상호 작용 및 연관 연산(표시가 없는 그래프의 경우)[2]
- 사전 그래프 제품(또는 그래프 구성): 연관성(표시가 없는 그래프의 경우) 및 비확정 연산,[2]
- 강력한 그래프 제품: 상호 작용 및 연관 연산(표시가 없는 그래프의 경우)
- 텐서 그래프 제품(또는 직접 그래프 제품, 범주형 그래프 제품, 기본 그래프 제품, 크로네커 그래프 제품): 상호 작용 및 연관 연산(표시가 없는 그래프의 경우)
- 지그재그 그래프 제품;[3]
- 다른 제품을 기준으로 제품 그래프 작성:
- 직렬-직렬 그래프 구성:
- 병렬 그래프 구성: 상호 작용(레이블링되지 않은 그래프의 경우)
- 직렬 그래프 구성: 비 커밋 작업,
- 소스 그래프 구성: 상호 교환 작업(레이블링되지 않은 그래프의 경우);
- 하조스 건설.
메모들
- ^ Bondy, J. A.; Murty, U. S. R. (2008). Graph Theory. Graduate Texts in Mathematics. Springer. p. 29. ISBN 978-1-84628-969-9.
- ^ a b c 하라리, F. 그래프 이론.MA: Addison-Wesley, 1994.
- ^ Reingold, O.; Vadhan, S.; Wigderson, A. (2002). "Entropy waves, the zig-zag graph product, and new constant-degree expanders". Annals of Mathematics. 155 (1): 157–187. arXiv:math/0406038. doi:10.2307/3062153. JSTOR 3062153. MR 1888797.
- ^ Frucht, Robert; Harary, Frank (1970). "On the corona of two graphs". Aequationes Mathematicae. 4: 322–324. doi:10.1007/bf01844162. hdl:2027.42/44326.
