Полный граф
Полный граф — это граф, в котором каждая пара различных вершин соединена ровно одним ребром. Поэтому из любой вершины можно напрямую попасть в любую другую.
Чтобы правильно читать это определение, полезно вспомнить вершины и рёбра графа. В полном графе соединены не только соседние вершины на рисунке: ребро есть между каждой парой вершин. Если одна вершина соединена с несколькими другими, но хотя бы с одной не соединена, граф уже не является полным.
Основные свойства
- В полном графе с \(n\) вершинами степень каждой вершины равна \(n-1\).
- Из каждой вершины можно попасть в любую другую за один переход.
- Число рёбер определяется количеством пар вершин.
- При увеличении числа вершин граф быстро становится плотнее: каждая новая вершина соединяется со всеми уже имеющимися.
Здесь \(n\) — число вершин, а \(m\) — число рёбер. Деление на \(2\) необходимо, потому что пары вершин \(A\)–\(B\) и \(B\)–\(A\) задают одно и то же неориентированное ребро.
В полном графе с \(5\) вершинами каждая вершина соединена с четырьмя другими. Число рёбер равно \(m=\frac{5\cdot4}{2}=10\). Если добавить шестую вершину, она соединится с пятью прежними вершинами, поэтому всего станет \(10+5=15\) рёбер.
Полный граф — это не то же самое, что доля полного графа. Доля показывает, насколько данный граф близок к полному: сравнивает фактическое число рёбер с максимально возможным. Также полный граф не обязан быть двудольным: например, \(K_3\) содержит треугольник и не является двудольным.
Сколько рёбер в полном графе \(K_4\)?
Главное
- Полный граф соединяет ребром каждую пару различных вершин.
- В графе \(K_n\) степень каждой вершины равна \(n-1\).
- Число рёбер вычисляют по формуле \(m=\frac{n(n-1)}{2}\); каждое ребро учитывается один раз.