В стране каждые два города соединены дорогой с односторонним движением.
Доказать, что существует город, из которого можно проехать в любой другой не более чем по двум дорогам.

   Решение

Страница: << 13 14 15 16 17 18 19 >> [Всего задач: 390]      

В стране Ориентация на всех дорогах введено одностороннее движение, причём из каждого города в любой другой можно добраться, проехав не более чем по двум дорогам. Одну дорогу закрыли на ремонт так, что из каждого города по-прежнему можно добраться до любого другого. Докажите, что для каждых двух городов это можно сделать, проехав не более чем по трём дорогам.

Прислать комментарий

Решение

В кружке у каждого члена имеется один друг и один враг. Доказать, что
  а) число членов чётно.
  б) кружок можно разделить на два нейтральных кружка.

Прислать комментарий

Решение

Из полного 100-вершинного графа выкинули 98 рёбер. Доказать, что он остался связным.

Прислать комментарий

Решение

В стране каждые два города соединены дорогой с односторонним движением.
Доказать, что существует город, из которого можно проехать в любой другой не более чем по двум дорогам.

Прислать комментарий

Решение

Доказать, что в двудольном плоском графе  E ≥ 2F,  если  E ≥ 2  (E – число рёбер, F – число областей).

Прислать комментарий

Решение

Страница: << 13 14 15 16 17 18 19 >> [Всего задач: 390]