Каков диаметр графика только с одной иглой?

Question

Я пытаюсь найти ответ на проблему в моем курсе "Распределенные алгоритмы", и для этого я хочу кое-что прояснить.

1. Какой диаметр графа с одним узлом, с ребром к себе? Это 1 или 0?

Если вам интересно, вопрос, на который я пытаюсь найти ответ, заключается в следующем:

В терминах n (# узлов) количество сообщений (= diam * |E|), используемых в алгоритме FloodMax, легко увидеть как O(n^3). Создайте класс орграфов, в котором произведение (diam * |E|) действительно является Omega(n^3).

Диграф, который я придумал, - это граф с одним узлом, который имеет направленное ребро. Таким образом, | E | будет 1, который равен n^2, и если diam равен 1, он также удовлетворяет второму условию, где diam = 1 = n. Так что это дает мне класс орграфов со сложностью сообщения Омега (n ^ 3).

Правильно ли я считаю, что на таком графике диаметр равен 1?

Answer 1

Две вещи:

1. Похоже, что это 0, что говорит:

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

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

   1 -- 2
   
   |E| = 1 = (1/4)*2^2 = (1/4)*n^2 = O(n^2)
   diam = 1 = 2 - 1 = n - 1 = O(n)
   tada!
   

   Или вот как мы можем заставить ваше решение работать, даже если диаметр составляет 0: 0 = 1 - 1 = n - 1 = O(n) => Ваше решение все еще работает!

   Поэтому, даже если вы рассматривали пути с циклами, я бы все равно счел ваше решение неверным.

Answer 2

O(n^3) и Omega(n^3) не означают cn^3, и нет проблем с функцией, которая равна 0 при конечном числе ненулевых значений n, находящихся в O(n^3) и Omega(n^3). Например, n^3-100 находится в обоих, как и n^3-100n^2. Для асимптотики неважно, какой диаметр для одного примера. Вас просят найти бесконечное семейство графов с достаточно большими диаметрами, и один пример графа не влияет на асимптотику бесконечного семейства.

Тем не менее, диаметр графа (или сильно связанного орграфа) можно определить несколькими способами. Одна возможность - это наибольшее значение, равное половине минимума длины обхода от v до w и обратно по всем парам v и w, и это 0, когда v и w совпадают. Итак, диаметр графа с одной вершиной равен 0.

Опять же, это совсем не помогает в том упражнении, которое у вас есть, для создания бесконечной семьи. Семья с одним узлом и множеством ребер к себе сама по себе не собирается. Подумайте, как можно добавить множество ребер к графам с большим диаметром, таким как n-цикл или траектория, без значительного уменьшения диаметра.