разбиение орграфа на подграфы

Question

Учитывая DAG с | V | = n и имеет s источников, мы должны представить такие подграфы, чтобы каждый подграф имел приблизительно k1 = √ | s | источники и примерно k2 = √ | n | узлы.

Если мы определим высоту DAG как максимальную длину пути от некоторого источника до некоторого приемника.

Мы требуем, чтобы все сгенерированные подграфы имели примерно одинаковую высоту.

Пересечение каждой пары наборов узлов (подграфов) пусто.

На прилагаемом рисунке вы видите пример правого разбиения (каждое ребро на графике направлено вверх).

В этом примере 36 узлов и 8 приемников [# 10,11,12,13,20,21,22,23]. Поэтому каждый подграф должен иметь 6 узлов и 2 или 3 приемника.

У вас есть идея для алгоритма?

Большое спасибо

Answer 1

Похоже, вы пропустили некоторую информацию, даже если предположить, что график косвенно связан.посмотрите на следующий пример.
у вас должно быть 3 вершины в каждом подграфе, однако посмотрите на вершину 6, если она без 5 - мы закончили, потому что граф не связан, как вы сказали, это должно быть в комментарии.
если это так - должно быть самое большее с одним из {7,8,9} - скажем, с 7. то есть U = {5,6,7}
давайте теперь посмотрим на 8, скажем такнаходится в U ', так как 5 не в U', нет никакого возможного решения, в котором подмножество U 'будет соединено.
пожалуйста, посмотрите еще раз на описание задачи и дайте нам более подробную информацию (или приведите этот пример в качестве контрпримера, чтобы показать, что он может быть неразрешимым)