2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Король и дороги
Сообщение04.01.2015, 18:56 
Во владении короля имеется $100$ городов, которые не соединены дорогами. Король захотел построить дороги между некоторыми парами городов так, что если два города не связаны новой дорогой, то из одного города в другой можно добраться по крайней мере двумя разными маршрутами по новым дорогам, дополнительно проезжая ровно через один город. Какое наименьшее количество дорог может быть построено?

Вот такая задача! Пожалуйста, подскажите, направьте на путь решения :)

 
 
 
 Re: Король и дороги
Сообщение04.01.2015, 19:54 
Аватара пользователя
Пусть города $\mathrm A$ и $\mathrm B$ не соединены дорогами, а каждый из них соединён со всеми остальными городами. Можно ли убрать хотя бы одну любую дорогу, чтобы не нарушить условие задачи?

 
 
 
 Re: Король и дороги
Сообщение04.01.2015, 22:26 
Сначала решите такую задачу.
Соединяете дорогами все города последовательно. Сколько новых дорог надо проложить для связности городов, если убрать одну дорогу?
Затем распространиете решение на параллельные пути.

 
 
 
 Re: Король и дороги
Сообщение04.01.2015, 22:36 
Аватара пользователя
Раз все города попарно связаны, то граф связный. Если не каждый город связан с каждым, то в нем есть циклы.

Вообще-то задачка по типу олимпиадная. Это не с текущей олимпиады какой-нибудь?

 
 
 
 Re: Король и дороги
Сообщение05.01.2015, 09:41 
Граф должен быть связан.
На циклы нет ограничений. Требуется только существование не менее двух путей между любыми городами.

 
 
 
 Re: Король и дороги
Сообщение05.01.2015, 09:48 
Аватара пользователя
Что значит "на циклы нет ограничений"? Если есть два разных пути из $A$ в $B$, они и образуют цикл.
Теперь из каждого пункта можно сделать выводы: какое наименьшее число ребер может быть у графа?

Собственно, мы кому подсказываем? Где ТС?

 
 
 [ Сообщений: 6 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group