에지를 제거하여 이분 그래프에 그래프를 그리십시오 (가장자리/2 이상은 아님) - 알고리즘?

Question

그래서 우리는 그래프가 주어지고 두 개의 그래프가 될 때까지 (원래의 그래프의 가장자리/2)를 넘지 않도록 할 수 있습니다.

E={ (4, 1),(1 ,2), (2 ,3),(7, 2),(1 ,5),(8 ,4), (5 ,8),(8, 9)} 

과 정점의 집합 :

V= { 1,2,3,4,5,6,7,8} 

하나가이 문제를 해결하는 방법을

우리가 주어진한다고 가정하자? 어떤 종류의 알고리즘이 있나요? 모든 종류의 설명은 인정 될 것입니다.

Answer 1

임의의 노드를 집합 A의 첫 번째 구성원으로 선택하십시오. 연결된 노드가 있으면 집합 B의 첫 번째 구성원으로 하나를 선택하십시오. 다른 노드를 집합 B의 첫 번째 구성원으로 선택하십시오.

이제 두 세트의 노드 A와 B가 있습니다. 어느 세트에도없는 노드를 반복적으로 선택하십시오. 해당 노드를 A와 B의 노드에 연결하는 엣지 수를 셉니다. A를 설정하기 위해이 노드를 연결하는 가장자리가 더있는 경우 세트 B의 노드에 연결하는 가장자리를 지우고 세트 B에 넣습니다. 그렇지 않으면이를 연결하는 가장자리를 지우십시오 노드를 집합 A에 놓고 집합 A에 놓습니다. 노드에 연결된 가장자리의 반 이상을 지우지 않도록하십시오.