Страница 67 номер 86, ГДЗ по алгебре за 10 класс к учебнику Бунимовича. Математика вероятность и статистика
Города — вершины, авиалинии — рёбра. Сначала граф полный: степень каждой из 30 вершин равна 29, сумма степеней \(30 \cdot 29 = 870\), рёбер \(870 : 2 = 435\).
Граф должен остаться связным, а в связном графе с 30 вершинами не меньше \(30 - 1 = 29\) рёбер: выбрасывая рёбра, лежащие на циклах, придём к дереву на тех же вершинах. Значит, закрыть можно не больше \(435 - 29 = 406\) линий.
Ровно 406 и закрывается: оставим 29 линий из одного города во все остальные — тогда из любого города в любой другой долетишь с одной пересадкой.
Ответ: можно закрыть 406 авиалиний.
Города — вершины графа, авиалинии — рёбра. Сначала соединена каждая пара городов, то есть граф полный: каждая из 30 вершин имеет степень 29, сумма степеней равна \(30 \cdot 29 = 870\), а число рёбер вдвое меньше — \(870 : 2 = 435\) авиалиний.
После сокращения граф должен остаться связным. В связном графе с 30 вершинами не может быть меньше 29 рёбер: выбрасывая из него рёбра, лежащие на циклах, связности не потеряешь и рано или поздно придёшь к дереву на тех же 30 вершинах, а в дереве \(30 - 1 = 29\) рёбер. Значит, закрыть можно не больше \(435 - 29 = 406\) линий.
Ровно 406 закрыть удаётся: оставим 29 линий, соединяющих один выбранный город со всеми остальными. Тогда из любого города в любой другой можно долететь с одной пересадкой в этом городе.
Ответ: можно закрыть 406 авиалиний.
