6.10.3. Оценка количества ребер сверху и снизу

Оценка количества ребер сверху и снизу проводится на основе нескольких фактов.

1.Степень каждой вершины полного графа на единицу меньше числа его вершин, полный граф на n вершинах всегда является регулярным графом степени (n – 1), суммарная степень его вершин равна n(n + 1), а значит, количество ребер в полном графе равно n(n+1)/2. Это и есть ограничение количества ребер сверху – построить больше на n вершинах нельзя. Например, у графа на 7 вершинах максимально может быть 21 ребро.

2.Максимальное число ребер на n вершинах можно построить именно в случае, когда граф связный. Иначе их будет еще меньше, например, у несвязного графа на n вершинах в лучшем случае количество ребер равно (n–1)·(n – 2)/2 (лучший случай попытки разместить максимальное число ребер – это отделить одну изолированную вершину и построить полный граф на оставшихся (n – 1) вершине). Например, у несвязного графа на 7 вершинах максимально может быть 15 ребер.

3.Оценка снизу чаще всего сводится к оценке количества ребер, необходимых для образования именно связного графа. Минимальная с точки зрения расхода ребер конфигурация состоит именно в построении дерева. В дереве на n вершинах содержится всегда

(n – 1) ребро.

4.Если помимо условия ацикличности поставлено также требование обеспечить несвязность графа, то ребер удастся разместить