Question

в стране 20 городов, некоторые пары городов соединены двусторонними авиалиниями. оказалось, что никакие четыре авиалинии не образуют цикл (то есть нельзя, стартовав из некоторого города, за 4 перелета посетить другие 3 города и вернуться в исходный). какое максимальное число авиалиний могло быть в этой стране?

Answer 1

Найдите количество ребер в полном графе на 20 вершинах.Каждая вершина соединена с 19 вершинами. Однако, мы посчитали каждое ребро дважды, поэтому общее количество ребер равно 20 * 19 / 2 = 190.Найдите максимальное количество ребер в графе без циклов длины 4.Максимальное количество ребер, при котором не образуется цикл длины 4, равно 3 * 6 = 18. Для этого мы можем выбрать какую-то вершину и соединить ее с 6 другими вершинами. Затем мы можем выбрать еще одну вершину, не соединенную с предыдущими 7, и повторить процесс, пока не соединим все вершины.Ответ:Максимальное количество ребер в графе без циклов длины 4 равно 18. Таким образом, в этой стране может быть не более 190 + 18 = 208 авиалиний.