bipartite 그래프를 검출

Question

나는 단지 bipartite 그래프를 탐지하는 알고리즘을 만들었지 만, 알고리즘에 의하면 나는 bipartite로 간주 할 수없는 어떤 그래프를 생각했다.

(A)--(B) 

(C) 

그래서이 3 개 노드가 있지만 A 및 B 간의 1 개 에지가 같은

그래프 간다. 실제로이 부분이 맞습니까?

Answer 1

예, 샘플 그래프는 실제로 2 부분입니다.

보기는 예를 들어 소개 문장 내용의 Wikipedia article ... 그래프 이론으로 된 그래프 (또는 bigraph)의 수학적 필드

은 꼭지점 분할 될 수있는 그래프이다

두 개의 분리 된 은 모든 에지가 U의 꼭지점을 V의 하나의 꼭지점에 연결하도록 U와 V를 설정합니다. 즉, U와 V는 각각 독립적 인 집합입니다. 마찬가지로, bipartite 그래프는 홀수 길이 사이클을 포함하지 않는 그래프입니다.

이 그래프를 나눌 수있는 방법은 두 가지가 있습니다 ("{A, C}, {B}"또는 "{B, C}, {A}")으로 된 그래프에 필요한 조건을 충족하는 것 .

연결된 그래프가 아닌 이원 그래프가 필요하지 않습니다.