Количество трансляций, позволяющих 95% пар узлов обмениваться в направленном графе

Question

У меня есть направленный невзвешенный граф с N узлами и ребрами E. Узлы имеют среднюю степень 2E/N.

В первом раунде каждый узел передает свою информацию всем своим соседям. В последующих раундах узлы передавали информацию, полученную от своих соседей во время предыдущего раунда, всем другим соседям и т. Д.

График не ограничен ацикличным.

Мой вопрос: Сколько последовательных раундов вещания требуется, в среднем, для 95% пар узлов, достигших друг друга? Можно ли рассчитать приблизительную цифру, основанную на средней степени графа?

Answer 1

В среднем, я полагаю, вы имеете в виду среднее по всем возможным (N, E) ориентированным графам без краев.

теорема 1

Если Е < = (N-1)^2, будет по меньшей мере, один график, в котором информация не будет распространяться.

Доказательство

Ориентированный граф с N узлов имеет до N (N-1) ребер. Рассмотрим полный график, выберите узел и удалите все его исходящие ребра (в качестве альтернативы мы можем удалить все его входящие края). Информация из этого узла не может распространяться, и мы остаемся с краями N (N-1) - (N-1) = (N-1)^2.

следствие 1

< Когда Е = (N-1)^2, существует, по крайней мере, один график, в котором информация не может распространяться, поэтому среднее число раундов бесконечно.

---

теорема 2а

Если E> (N-1)^2 максимальное число раундов 2.

Доказательство

Ориентированный граф с N узлами и E> (N-1)^2 ребра - это полный граф, где до (N-2) ребра удалены.

Если мы хотим удалить ребра из полного графика, количество раундов будет равно 3 (например, от узла А до узла В), нам нужно убедиться, что нет узла В и ребра А-> B и B-> C. Это означает, что нам нужно удалить хотя бы одно ребро (либо A-> B, либо B-> C) для каждого из (N-2) возможных «B» узлов. Нам также необходимо удалить прямой A-> C ребро. В целом нам нужно удалить (N-3) ребра.

---

теорема 2b

Если E> (N-1)^2 количество раундов минимальное 2.

Доказательство

Trivial. Граф является неполным, поэтому существует по крайней мере один путь длины 2.

Следствие 2

, если (N-1)^2 < < Е N (N-1), количество раундов это 2.

---

теорема 3

Если E = N (N-1), количество раундов 1

Доказательство

Trivial. Полный график.

---

Теперь вы спрашиваете о более чем 95% пар узлов.

Конечно, мы можем построить некоторые (N-1)^2 < E < Графики N (N-1), где> = 95% пар упорядоченных узлов могут связываться в 1 раунде, пары узлов сообщаются в 2 раундах.

Это тривиально, если вы рассматриваете полный направленный граф из 6 узлов, где удалено только одно ребро. (6 * 5-1)/(6 * 5) = 96,66% пар упорядоченных узлов могут связываться в одном раунде.

Почему вы спрашиваете конкретно о 95%? Важно ли вывести расчеты именно за это число? Дайте нам знать. Я не думаю, что вы можете получить простую точную общую формулу, особенно когда N и E малы. Может быть, мы можем сформулировать что-то асимптотически (для очень больших N).