В стране 100 городов некоторые из которых сведение дорогами. известно что из столицы выходит 50 дорог и что между городами а и б есть дорога и между городами б и в то есть и дорога между городами а и в есть. какое максимальное количество дорог может быть в такой стране

Задача формализации: граф без кратковолосых дорог, 100 вершин (городов), один особый город — столица C, deg(C) = 50. Известно, что между городами a и b есть дорога, между b и v есть дорога, и между a и v есть дорога (образуется треугольник a–b–v). Нужно найти максимальноеPossible число дорог (ребер) в такой стране. Решение по шагам: 1) Обозначим столицу как вершину C. Тогда вокруг нее есть ровно 50 ребер, т.е. она подключена к 50 другим городам. Всего кроме столицы есть 99 городов. 2) Разделим все ребра на две группы: - ребра, инцидентные столице: ровно 50 ребер; - ребра между непери столице: ребра внутри множества остальных 99 городов. Обозначим их количество как E_rest. Тогда общее число дорог E_total = 50 + E_rest. 3) Чтобы максимизировать E_total, нужно максимизировать E_rest. Максимальное число ребер внутри множества из 99 вершин равно числу ребер полного графа K99: E_rest_max = C(99, 2) = 99·98/2 = 4851. 4) Достижимо ли такое значение при условии треугольника a–b, b–v, a–v? Да: можно взять a, b, v среди тех 99 городов и сделать внутри множества 99 городов полный граф. Тогда существуют ребра ab, bv, av, и одновременно столицу соединяем с ровно 50 другими городами. Таким образом условие треугольника выполняется, не уменьшая максимума E_rest. 5) Следовательно, максимальное число дорог равно: E_total,max = 50 + 4851 = 4901. Ответ: Максимум дорог в такой стране — 4901.