Кратко — инструменты и типичные примеры.
1) Тривиальные границы.
- Для связного графа на $n$ вершинах и $m$ рёб: $n-1\le m\le \left(\genfrac{}{}{0ex}{}{n}{2}\right)$.
- Диаметр $D$ всегда удовлетворяет $1\le D\le n-1$. Примеры: $K_n$ даёт $D=1$; путь $P_n$ даёт $D=n-1$.
2) Оценки через степени (Moore‑тип).
- Пусть максимальная степень $\Delta \ge 2$. Тогда (оценка сверху для размера шара радиуса $D$)
$$n\le 1+\Delta +\Delta (\Delta -1)+\cdots +\Delta (\Delta -1{)}^{D-1}=1+\Delta \frac{(\Delta -1{)}^D-1}{\Delta -2}.$$ Отсюда для заданных $n,\Delta$ минимальный возможный диаметр удовлетворяет
$$D\le \lceil {\log }_{\Delta -1}(1+\frac{(\Delta -2)(n-1)}{\Delta })\rceil .$$ - Так как $\Delta \ge \lceil 2m/n\rceil$ (макс. степень не меньше средней), можно подставить ${\Delta }_0=\lceil 2m/n\rceil$ и получить явную верхнюю оценку диаметра через $n$ и $m$:
$$D\le \lceil {\log }_{{\Delta }_0-1}(1+\frac{({\Delta }_0-2)(n-1)}{{\Delta }_0})\rceil ,{\Delta }_0=\lceil 2m/n\rceil .$$ (Эта оценка даёт смысл: чем больше средняя степень, тем меньше возможный диаметр.)
3) Оценки снизу / конструкции с большим диаметром при фиксированном $m$.
- Если $m=n-1$ (дерево), максимальный диаметр достигается путем $P_n$: $D=n-1$.
- Для больших $m$ стандартная «лоли-поп» конструкция: кликa $K_r$ прикреплена к висячему пути длины $t$. Тогда
$$n=r+t,m=\left(\genfrac{}{}{0ex}{}{r}{2}\right)+t,$$ и диаметр по крайней мере $t\approx n-r$. Чтобы для заданного $m$ сделать диаметр максимальным, берут максимально возможное $r$ с $\left(\genfrac{}{}{0ex}{}{r}{2}\right)\le m$, т.е.
$$r\approx \lfloor \frac{1+\sqrt{1+8m}}{2}\rfloor ,$$ и получают оценку
$$D\gtrsim n-r.$$ Эта конструкция показывает, что даже при больших $m$ (многие рёбра «концентрируются» в кликe) диаметр может оставаться большим.
- Деревообразные (сжатые) деревья с малой степенью (например, сбалансированное $\Delta$-древо) дают большие диаметры порядка $\Theta (\log n/\log (\Delta ))$ при фиксированной $\Delta$.
4) Конструкции с малым диаметром при фиксированном $m$.
- Чем «равномернее» распределены рёбра (высокая минимальная степень), тем меньше диаметр. Достаточное условие для $D\le 2$:
$$\delta \ge \frac{n-1}{2}\Rightarrow D\le 2,$$ потому что любые две не смежные вершины имеют общий сосед. Здесь $\delta$ — минимальная степень. Поскольку $\delta$ не выражается напрямую через $m$ без дополнительной информации, для гарантии малого диаметра обычно требуется, чтобы $m$ был очень близок к $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$.
5) Практическая стратегия оценок.
- Для верхней оценки $D$ по $n,m$: оцените $\Delta \ge \lceil 2m/n\rceil$ и примените Moore‑оценку из п.2.
- Для нижней оценки (показать, что диаметр можно сделать большим): используйте лолипоп (кластер + путь) или путь/дерево, чтобы сконструировать пример при заданных $n,m$.
Краткое резюме:
- Верхний предел диаметра задаёт Moore‑тип оценка через максимальную степень, которую можно связать с $m$ через среднюю степень.
- Наихудшие по диаметру графы при малых $m$ — пути и деревья; при больших $m$ — лолипоп (кластер+длинный хвост).
- Наименьший диаметр достигается при близости к полному графу (диаметр 1 при $m=\left(\genfrac{}{}{0ex}{}{n}{2}\right)$, диаметр 2 при достаточно большой минимальной степени).