학생들을 두 그룹으로 나누는 그래프 알고리즘

학생들 그룹이 두 그룹으로 나눌 수 있는지 여부를 결정할 수있는 효율적인 알고리즘을 만드는 데 어려움을 겪고 있습니다. (X,Y) 학생 X 학생 Y 및 (A,B) 학생 A 학생 B 함께 할 수없는 유형의 몇 가지 제약과 함께해야하는 유형의 일부를 제공 제약이 있다는 것을학생들을 두 그룹으로 나누는 그래프 알고리즘

는

참고. 모든 학생이 그에게 제약이있는 것은 아니며 일부 학생들에게는 여러 가지 제약이 있습니다.

학생들이 동일한 그룹에 속할 수 있다면 각 학생이 노드이고 두 노드가 가장자리로 연결되어있는 그래프를 고려했습니다 (예 : 함께 있어야하거나 제한되는 제약 조건이 있음). 그들이 함께 할 수 없다는 제약이있다). 그러나 일단이 그래프 표현을 구성하면 어떤 알고리즘을 적용하여 적용 할 수 있는지 (또는 입증 된 제약 조건 집합은 불가능 함) 확실하지 않습니다.

어떤 조언을 주시면 감사하겠습니다. 고맙습니다!

출처

2014-11-20 user3298872

귀하의 계획이 첫 단계로 좋다고 생각합니다. '동일한 그룹 내'제약 조건으로 연결되어있는 여러 클러스터를 가질 수 있습니다. 그 후, 클러스터를 두 그룹으로 분리하기 위해 '동일한 그룹이 아님'제약 조건을 사용할 수 있습니다. 나는 아무런 제약이없는 학생들을 어떻게 대우해야할지 모른다. –

알리 (Ali)가 제안한 것처럼 2 가지 그래프를 사용하여 그래프를 2 가지 색상만으로 채색하려고합니다. – purpletentacle

아래 단계를 사용하여 Bipartite Graph 알고리즘을 사용할 수 있습니다.

각 학생이 노드와 학생들이 같은 그룹에 있지 수 있다면 두 개의 노드가 가장자리로 연결되어 그래프를 생각해 보자.
학생 A와 B가 같은 그룹에 있어야만한다면 A가 연결된 모든 노드에 B를 연결하고 B가 연결된 모든 노드에도 A를 연결하십시오.

이제 정점을 두 개의 분리 된 세트로 나눌 수 있고 동일한 세트의 두 노드 사이에 모서리가 없는지 확인하려는 그래프가 있습니다. 이것은 Bipartite Graph이며이를 해결하는 방법에 대한 알고리즘을 찾을 수 있습니다.

각 학생이 노드와 두 개의 노드가있는 그래프를 고려 : 피터 당신이 내 단계를 바꿀 수 말했듯이 PeterdeRivaz 주석과

편집

이 답변이 더 낫다 학생들이 이 아니라면은 같은 그룹에 속할 수 있습니다.
학생 A와 학생 B가 같은 그룹에 있어야하고 A와 B를 가상 학생과 연결해야하는 경우.

출처

2014-11-20 08:14:11 Lrrr

우아한 감소! – Sayakiss

@Sayakiss, thanks Sayakiss :)이 좋은 것을 찾으면 투표를 잊지 마시길 바랍니다 :) – Lrrr

A와 B가 같은 그룹에 있어야하지만 연결이 없으면 어떻게 될까요? 새로운 상상의 학생을 통해 그들과 더 쉽게 합칠 수 있습니까? –

그래프 A는 함께 있어야하는 학생들을위한 그래프이며, 그래프 B는 함께있을 수없는 학생들을위한 그래프입니다.

X에서 Y까지의 경로가있는 A의 모든 노드 X, Y에 대해 B에 X와 Y 사이에 Edge와 Edge가 있으면이 문제를 해결할 수 없습니다. 그렇지 않으면 해결 될 수 있습니다.

A에서 모든 반복에서 임의로 세트를 선택하고 두 그룹 중 하나로 이동하려고하는 세트의 모든 노드에 대한 제약 조건을 확인하는 A의 모든 연결 노드 세트를 반복하면이 문제를 해결할 수 있습니다. 그룹의 다른 노드에 대한 제약 조건을 만족하는지 확인하십시오.제한 조건이 세트의 한 노드에 대해 충족 될 수 없으면 세트를 다른 그룹에 추가하십시오.

모든 세트가 충돌없이 두 그룹 중 하나에있는 경우 중지해야합니다.

출처

2014-11-20 08:21:45

학생들을 두 그룹으로 나누는 그래프 알고리즘

답변

관련 문제