3
Учитывая наличие DAG с | V | = n и имеет s источников, мы должны представить такие подграфы, что каждый подграф имеет приблизительно k1 = √ | s | источников и приблизительно k2 = √ | n | узлы.разделение графа на подграфы
Если мы определяем высоту DAG как максимальную длину пути от некоторого источника до некоторой раковины.
Мы требуем, чтобы все сгенерированные подграфы имели примерно одинаковую высоту.
Пересечение каждой пары узлов (подграфов) пуст.
Вы можете увидеть в прикрепленном изображении пример правого раздела (каждое ребро в графе направлено вверх).
Есть 36 узлов и 8 раковины [# 10,11,12,13,20,21,22,23] в примере .SO каждого подграфа должен иметь 6 узлов и 2 или 3 раковины ,
У вас есть идея для алгоритма?
Большое спасибо
Если это домашнее задание, вы должны добавить домашнее задание тег. Кроме того, это помогло бы, если бы вы предоставили какие у вас идеи для этого. – JoshD
Нет, это не домашняя работа его части исследовательского проекта. – Yakov
Как написано, это эквивалентно нахождению подмножеств множества. Если «leaf» означает узел, это означает только перечисление всех подмножеств размера (sqrt (| V |), взятых из G (с их ребрами), что тривиально. Если лист - это узел с ребром, который указывает * на * он, но не ребро, которое указывает * из * его, затем делает то же самое с узлами, которые могут быть листьями (при необходимости опуская края), затем выберите среди всех необходимых узлов (чтобы обеспечить «веточки»), затем среди всех ненужных узлов. Это выглядит слишком легко: уверены ли вы, что нет других условий? – Beta