Некоторые города в стране соединены дорогами. Оказалось, что для любых двух городов найдется ровно один город, с которым соединены оба. Может ли в этой стране быть ровно 15 городов?
Arnfinn изменил статус на опубликованный
1 Ответ
Решение:
Пусть v = 15 — количество городов.
Для любого графа, удовлетворяющего условию, выполняется соотношение:
v=k(k-1) + 1, где k — степень каждой вершины (граф регулярный).
Подставим v = 15:
k(k-1) +1=15=>k(k-1) = 14.
Уравнение k2 — к — 14 = 0 не имеет целочисленных решений (дискриминант D = 57 не является полным квадратом).
Следовательно, для v = 15 не существует такого графа.
Ответ: нет
Arnfinn изменил статус на опубликованный