в стране 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.