Задания № 1, 8 · ЕГЭ

Доли полного графа

Сколько рёбер и соседей у вершины полного графа

2 мин чтенияСложность: Обновлено 29 сентября 2026

В полном графе каждая вершина соединена ребром с каждой другой вершиной. Поэтому для \(n\) вершин число рёбер равно \(\frac{n(n-1)}{2}\), а степень любой вершины равна \(n-1\).

Доли полного графаСлово «полный» означает, что соединены все возможные пары различных вершин.

Доли полного графа — это формулы, выражающие основные характеристики полного графа через число его вершин \(n\): число рёбер и степень вершины. Рассматривается простой неориентированный граф: петель и нескольких рёбер между одной парой вершин нет.

Формулы

Степень вершины — число рёбер, выходящих из этой вершины. Повторить определение можно на странице степень вершины. В полном графе у выбранной вершины есть ровно один сосед для каждой из остальных \(n-1\) вершин:

\[d=n-1\]

Чтобы найти число рёбер, можно сначала посчитать возможные пары вершин: \(n(n-1)\). Но каждое ребро при этом посчитано дважды — по одному разу от каждой его вершины. Поэтому:

\[m=\frac{n(n-1)}{2}\]

№

Пример

В полном графе с \(5\) вершинами степень каждой вершины равна \(5-1=4\). Число рёбер: \(m=\frac{5\cdot4}{2}=10\). Действительно, можно соединить каждую вершину с четырьмя другими, но при подсчёте такие соединения будут учтены дважды.

Не перепутайте

Выражение \(n(n-1)\) не является числом рёбер неориентированного полного графа: это удвоенное число рёбер. Деление на \(2\) обязательно. Также число рёбер \(m\) не равно степени одной вершины: степень равна \(n-1\).

Проверьте себя

Сколько рёбер в полном графе с \(6\) вершинами?

Главное за минуту

Главное

В полном графе каждая пара различных вершин соединена одним ребром.
Число рёбер: \(m=\frac{n(n-1)}{2}\); степень любой вершины: \(d=n-1\).
При подсчёте через степени каждое ребро учитывается у двух вершин, поэтому возникает деление на \(2\).