В стране 18 больших городов, каждые два из которых соединены авиалинией. Сколько всего авиалинией между этими городами?
Можно пожалуйста с объяснением
Ответы
Каждая авиалиния соединяет два города. В качестве первого города можно взять любой из 20 городов (город А) , а в качестве второго – любой из 19 оставшихся (город В) . Перемножив эти числа, получаем 20 • 19 = 380. Однако при этом подсчете каждая авиалиния учтена дважды. Тогда нужно 380:2=190 авиалиний.
Ответ:
153
Пошаговое объяснение:
Из теории графов:
УТВЕРЖДЕНИЕ:
Число всех ребер графа равно полусумме степеней всех вершин графа.
Применительно к нашей задаче
города - вершины графа, соединяющие авиалинии - ребра графа.
Количество ребер выходящих из данной вершины, назыв. её степенью. В нашей задаче все вершины (города) соединены с остальными 17-ю авиалинией. Значит степени каждой вершины =
17.
Итак, по утверждению число всех авиалиний равно полусумме степеней всех вершин графа:
1/2×(18×17)=9×17=153.
P.S. : Можно попробовать проверить справедливость утверждения на малых числах. Пусть будет 3 города, 4 города, 5 городов и т.д.