그래프가 이분법인지 확인하는 방법은 무엇입니까?

그래프의 정점을 두 개의 독립적인 집합으로 나눌 수 있는 경우 그래프의 모든 모서리가 첫 번째 집합에서 시작하여 두 번째 세트 또는 두 번째 세트에서 시작하여 첫 번째 세트에 연결됩니다. 즉, 동일한 세트에서 가장자리를 찾을 수 없다고 말할 수 있습니다.

정점 채색을 사용하여 이분 그래프의 확인이 가능합니다. 정점이 같은 집합에 있으면 같은 색을 가집니다. 다른 집합에 대해서는 색이 바뀝니다.

입력 및 출력

입력:인접 매트릭스 
알고리즘
 
isBipartite(출처)
 

 입력 - 소스 정점. 
 출력 그 :그래프가 이분법이면 참입니다.
 
빈 대기열 qu를 정의하고 색상 목록 coloArray를 시작합니다. 처음에는 모든 노드가 어떤 색상으로도 색상이 지정되지 않습니다. 소스 정점을 빨간색으로 지정합니다. qu가 비어 있지 않을 때 qu에 소스를 추가하고, qu에서 항목을 제거하고 가져옵니다. u에 자체 루프가 있으면 u와 연결된 모든 정점 v에 대해 false를 반환하고 v에 색상이 없으면 do, colorArray[u] =red이면 colorArray[v] :=blue else if colorArray[u] =blue, 그 다음 colorArray[v] :=red는 v를 대기열에 추가(colorArray[v] =colorArray[u])한 다음 false를 반환합니다. done return trueEnd 
 
예시
 
#include#include#include#define NODE 6 using namespace std;/*int graph[NODE][NODE] ={ {0, 1, 1, 1, 0, 0} , {1, 0, 0, 1, 1, 0}, {1, 0, 0, 1, 0, 1}, {1, 1, 1, 0, 1, 1}, {0, 1, 0, 1, 0, 1}, {0, 0, 1, 1, 1, 0}}; */int 그래프[노드][노드] ={ {0, 1, 0, 0, 0, 1}, {1, 0, 1, 0, 0, 0}, {0, 1, 0, 1, 0 , 0}, {0, 0, 1, 0, 1, 0}, {0, 0, 0, 1, 0, 1}, {1, 0, 0, 0, 1, 0}};bool isBipartite( int 소스) { 큐 qu; 문자열 색상 배열[노드]; for(int i =0; i 
출력
 
그래프는 이분법입니다.