유도 부분 그래프

정점을 고르면 간선이 정해진다

삼각형 A,B,C에서 S={A,B,C}를 고르면 세 간선이 모두 남는다. AB와 BC만 남기는 것은 부분 그래프이지만 이 S의 유도 부분 그래프는 아니다.

두 정점의 예

같은 삼각형에서 {A,C}를 고르면 A,C와 간선 AC만 남는다. B에 닿는 AB와 BC는 끝점 B가 선택 집합에 없으므로 남기지 않는다.

클리크와 독립 집합

선택 집합 S가 클리크이면 G[S]는 완전 그래프다. S가 독립 집합이면 G[S]에는 간선이 없다. 선택 정점들 내부의 연결을 빠짐없이 보는 표현이기 때문이다.

간선 유도와의 구별

정점을 먼저 고르는 유도 부분 그래프와 간선을 먼저 골라 그 끝점들을 남기는 간선 유도 부분 그래프는 다르다. 무엇을 선택 기준으로 삼는지 명시해야 한다.

관련 문서

부분 그래프 / 클리크 / 독립 집합 (그래프 이론) / 완전 그래프 / 정점 (그래프 이론) / 간선 (그래프 이론)