Графический алгоритм разделения студентов на две группы

Question

Я изо всех сил пытаюсь создать эффективный алгоритм, который может определить, можно ли разделить группу студентов на две группы.

Обратите внимание, что существуют некоторые ограничения, предусмотренные типа, что для (X,Y) студента X должен быть с учеником Y и некоторыми ограничениями типа, что для (A,B) студента A не может быть с учеником B. Не у каждого ученика есть ограничение, и у некоторых учеников есть несколько ограничений.

Я рассмотрел график, в котором каждый ученик является узлом, а затем два узла связаны ребром, если учащиеся могут находиться в одной группе (например, они либо имеют ограничение, что они должны быть вместе, либо У меня есть ограничение, что они не могут быть вместе). Но я не уверен, какой алгоритм я мог бы применить для решения (или доказал, учитывая, что набор ограничений это невозможно), как только я построил это представление графика.

Любые советы приветствуются? Спасибо!

Answer 1

Вы можете использовать нижеследующие шаги, а затем использовать алгоритм Bipartite Graph.

1. Рассмотрим граф, где каждый ученик является узлом, а затем два узла соединены ребром, если студенты могли не быть в той же самой группе.

2. Если учащиеся A и B должны быть в одной группе, тогда подключите B к каждому узлу, к которому подключен A, и подключите A к каждому узлу, к которому подключен B.

теперь у вас есть график, который вы хотите проверить, если вершины можно разбить на два непересекающихся множества, и нет ни одного ребра между двумя узлами в одном наборе. это двухсторонний график, и вы можете найти алгоритмы о том, как это решить.

Редактировать с PeterdeRivaz комментарий

этот ответ лучше, как Питер сказал, что вы могли бы изменить мой шаг к этому:

1. Рассмотрим график, где каждый студент является узлом, а затем два узла связанный ребром, если ученики могут не быть в той же группе.

2. Если учащиеся A и B должны быть в одной группе, тогда соедините A и B с воображаемым учеником.

Answer 2

График A - график для студентов, которые должны быть вместе, график B - это график для студентов, которые не могут быть вместе.

Для каждого из двух узлов X, Y в A, где есть путь от X до Y, если существует и Edge между X и Y в B, то эта проблема не может быть решена. В противном случае это можно решить.

Решение этого вопроса будет итеративным для каждого набора подключенных узлов в A, где на каждой итерации вы выбираете набор произвольно и пытаетесь переместить его в одну из двух групп, проверяя ограничение для каждого узла набора чтобы убедиться, что вы удовлетворяете ограничениям с другими узлами в группе.Если ограничения не могут быть выполнены для одного узла в наборе, добавьте набор в другую группу.

Вы должны остановиться, когда каждый комплект находится в одной из двух групп без конфликтов.