Страница 45 номер 66, ГДЗ по математике за 10 и 11 класс к учебнику Высоцкого. Вероятность и статистика базовый и углубленный уровни
В графе семь вершин, нет петель и кратных рёбер. Какое наибольшее число рёбер может быть в этом графе?
Каждое ребро соединяет две различные вершины — иначе это была бы петля, — и разным рёбрам отвечают разные пары вершин — иначе это были бы кратные рёбра. Значит, рёбер не больше, чем пар, которые можно составить из семи вершин: \[C_7^2 = \frac{7 \cdot 6}{2} = 21.\]
Ровно 21 ребро достигается: у полного графа \(K_7\) нет ни петель, ни кратных рёбер, а рёбер в нём ровно \(C_7^2 = 21\).
Ответ: наибольшее число рёбер равно 21 — столько рёбер у полного графа \(K_7\) с семью вершинами.
В графе семь вершин, нет петель и кратных рёбер. Какое наибольшее число рёбер может быть в этом графе?
В графе семь вершин, петель нет и кратных рёбер нет.
Каждое ребро такого графа соединяет две различные вершины — иначе это была бы петля. Двух разных рёбер с одной и той же парой концов быть не может — иначе это были бы кратные рёбра. Значит, разным рёбрам отвечают разные пары вершин, а потому рёбер в графе не больше, чем пар, которые можно составить из семи вершин: \[C_7^2 = \frac{7 \cdot 6}{2} = 21.\]
Ровно 21 ребро и достигается. Проведём ребро между каждыми двумя из семи вершин — получится полный граф \(K_7\). Петель в нём нет, кратных рёбер тоже нет, а рёбер ровно \(C_7^2 = 21\), то есть верхняя граница достигнута.
Ответ: наибольшее число рёбер равно 21 — столько рёбер у полного графа \(K_7\) с семью вершинами.
