그래프 결합 해제

전체 그래프의 분리 결합인 군집 그래프

수학의 한 분야인 그래프 이론에서 그래프의 분리 결합은 두 개 이상의 그래프를 결합하여 더 큰 그래프를 구성하는 연산이다.집합의 분리 결합과 유사하며, 결과의 정점 집합을 주어진 그래프의 정점 집합의 분리 결합으로 만들고, 결과의 에지 집합을 주어진 그래프 집합의 분리 결합으로 만들어진다.두 개 이상의 비어 있지 않은 그래프를 분리하는 것은 반드시 분리되어야 한다.

표기법

분리 결합은 그래프 합이라고도 하며, 더하기 기호 또는 원 모양의 더하기 기호로 나타낼 수 있다.$G{\displaystyle }$ ${\displaystyle G}$과 H ${\displaystyle H}$이(가) 두 그래프인 경우 $G{\displaystyle }$+ ${\displaystyle H}$ ${\displaystyle G+H}$ 또는$$ $G{\displaystyle }$g ${\displaystyle H}$ ${\displaystyle G\oplus H}$은(가) 분리 결합을 나타낸다$$.^[1]

관련 그래프 클래스

특정 등급의 그래프는 분리 결합 연산을 사용하여 나타낼 수 있다.특히:

• 숲은 나무들의 분리된 결합이다.^[2]
• 군집 그래프는 완전한 그래프의 분리 결합이다.^[3]
• 2-규칙 그래프는 주기 그래프의 분리 결합이다.^[4]

보다 일반적으로 모든 그래프는 연결된 그래프와 연결된 구성요소의 분리된 결합이다.

cographs는 분리 결합과 보완 연산을 조합하여 단일 버텍스 그래프로 구성할 수 있는 그래프다.^[5]

참조