решала такую задачу на графы:
В стране 77 городов, некоторые из которых соединены дорогами. При этом из любого города до любого существует путь, в котором ни один город не повторяется, а количество пройденных дорог делится на три. Какое минимальное количество дорог может быть в стране?
Мои рассуждения:
Нарисуем схему в виде графа, в котором города-это вершины, а дороги-ребра.
Так как получившийся граф связен(что видно из условия, ведь
"...При этом из любого города до любого существует путь..."), то в нем
заведомо минимум 76 ребер(доказывается по индукции, то есть с компонентой связности
из двух вершин должна соединяться третья, они образуют новую компоненту,
далее с ней должна быть соединена четвертая вершина и т.д.).
Если вершин 76, то 2 вершины имеют степень 1, назовем их А и В. Но тогда
есть один, как вариант добраться до соседней с А вершиной, причем он состоит из
1 ребра, нам такое не подходит. Аналогично опровергается возможность существования 77 ребер,
только здесь мы берем единственную вершину со степенью 1.
Но теперь я зашла в тупик, я не знаю, существует ли пример на 78 вершин, или есть опровержение... Думаю, если примера на 78 ребер нет, то на 79 ребер он существует точно... Помогите пожалуйста!!! Заранее спасибо за помощь:)
3 + (x-3)*2 + xmod2
, где x - кол-во городов (вершин)