Сначала несколько определений: «накопленный граф» - это граф, ребра которого добавляются к нему позже.Тема - проблема ориентации (создание ориентированного неориентированного графа), когда наша цель - сделать максимальный выходной градус наименьшим из возможных.
Теперь они дали такой алгоритм: «Когда край (u, v)добавлено, мы направим его из вершины с более низкой степенью в верхнюю. Если равно, выберите случайным образом. "
Например, если outdegree (u) = 3 и outdegree (v) = 4, и мы только что добавили (u, v), алгоритм направит его из u -> v.Если бы их конечная степень была равна, то и u, v и v, u были бы возможны.
Вопрос состоит в том, чтобы доказать верхнюю границу O (log n) для максимально возможной степени.Второй вопрос заключается в том, чтобы сформировать график, в котором этот алгоритм приведет к максимальной степени омега (log n).
Пока что все, на что я могу указать, это то, что этот вопрос неверен.
Прежде всего, мой друг предположил, что они на самом деле имели в виду O (log m) [m = # ребер], поскольку для n вершин в неориентированном графе мы имеем не более n (n-1)/ 2 ребра, что в конечном итоге O (n ^ 2).Если мы предположим, что в полном графе выходной уровень каждого узла равен log (n), мы получим общее количество выходных степеней n * log (n), которое значительно меньше, чем n ^ 2 (и не имеет смысла, поскольку все выходные степени должны суммироватьсядо числа ребер.).
Я придумал этот алгоритм, который доказывает, что, поскольку мы выбираем случайным образом в случаях, когда оба равны, наивысшая возможная степень O (n): прямые n-1 вершин кпоследний (возможный в худшем случае, когда все ориентации находятся в одном направлении).Теперь у нас есть n-1 вершин с конечной степенью 1 и 1 с 0. Затем повторяем рекурсивно для достижения n + (n-1) + (n-2) + ... + 1 + 0 градусов.
Возможно, я неправильно понял проблему, но это то, что я до сих пор понял.
РЕДАКТИРОВАТЬ: преподаватель отредактировал вопрос и сказал, что график в этом вопросе - лес (что означает, что вы можете иметь максимум V-1края).Я полагаю, что мне удалось доказать первый вопрос:
Представьте себе следующее: поскольку единственный способ (наихудший сценарий) иметь степень 2 - это соединить два узла с степенью 1, мы должны иметь 4узлы, где A соединен с B, а C соединен с D, чтобы добавить ребро из A в C и сделать один из них со степенью 2. Поскольку это наименьшее дерево, которое можно создать со степенью 2, единственноеспособ создать степень 3 состоит в том, чтобы построить два одинаковых дерева и снова соединить их вместе.Если мы повторим этот процесс, пока не достигнем n вершин, мы заметим, что в конечном итоге мы получим 1 + 2 + 4 + 8 + ... + log n в качестве нашей степени.
Прямо сейчас я продолжаю думать о второмвопрос.