Bipartite Graph (1) 썸네일형 리스트형 112. Bipartite Graph 음이 아닌 정수 $k$에 대해 그래프가 다음 조건을 만족하면 그 그래프를 $k$분 그래프(${\color{#FF0000}k}$-partite Graph)라고 한다. 정점을 $k$개의 그룹으로 분리했을 때 간선으로 직접 연결된 두 정점이 항상 서로 다른 그룹에 속하게 할 수 있다. 이중 $k = 2$일 때 조건을 만족하는 그래프를 이분 그래프(Bipartite Graph)라고 한다. 이분 그래프에 존재하는 모든 사이클은 길이(사이클에 포함된 정점의 수)가 짝수이며, 그 역도 성립한다. 모든 트리는 이분 그래프이다. 어떤 그래프가 이분 그래프인지 확인하는 방법은 간단한데, 임의의 정점에서 DFS를 시작해서 인접한 정점을 탐색할 때마다 그 정점을 이전 정점과 다른 그룹에 추가한 다음 DFS가 끝났을 때 간선이.. 이전 1 다음
