0

решала такую задачу на графы:

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

Мои рассуждения:

Нарисуем схему в виде графа, в котором города-это вершины, а дороги-ребра.
Так как получившийся граф связен(что видно из условия, ведь 
"...При этом из любого города до любого существует путь..."), то в нем 
заведомо минимум 76 ребер(доказывается по индукции, то есть с компонентой связности
из двух вершин должна соединяться третья, они образуют новую компоненту,
далее с ней должна быть соединена четвертая вершина и т.д.). 
Если вершин 76, то 2 вершины имеют степень 1, назовем их А и В. Но тогда
есть один, как вариант добраться до соседней с А вершиной, причем он состоит из 
1 ребра, нам такое не подходит. Аналогично опровергается возможность существования 77 ребер,
только здесь мы берем единственную вершину со степенью 1. 

Но теперь я зашла в тупик, я не знаю, существует ли пример на 78 вершин, или есть опровержение... Думаю, если примера на 78 ребер нет, то на 79 ребер он существует точно... Помогите пожалуйста!!! Заранее спасибо за помощь:)

2
  • Я догадываюсь, что раз количество дорог от любого до любого может делиться на 3, каджый город должен соединяться котя бы с 3 другими, отсюда и делитель 3. Но это не точно.
    – megorit
    11 мая в 18:26
  • Не спрашивайте как я посчитал, но я предполагаю, что ответ 152 =) Я просто методом тыка соединял вершины в разных количествах и пытался найти закономерности =) Итого моя формула выглядит так: 3 + (x-3)*2 + xmod2, где x - кол-во городов (вершин)
    – megorit
    11 мая в 19:22

1 ответ 1

3

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

Рассмотрите связный граф из 77 рёбер в котором нет вершин степени один (листьев). Докажите что любой такой граф - цикл. Покажите что цикл из 77 рёбер не подходит.

Рассмотрите граф из 78 рёбер в котором два цикла, которые имеют единственное общее ребро. Подберите длины циклов так чтобы из любой вершины в любую можно было добраться по пути с длиной кратной три.

Так как вы доказали что графы с числом рёбер менее 78 не подходят и привели пример для 78 рёбер - задача решена полностью.

11
  • почему решена? А если нельзя подобрать длины циклов так чтобы из любой вершины в любую можно было добраться по пути с длиной кратной три, учитывая, что в пути вершины не могут повторяться
    – Grundy
    11 мая в 17:40
  • @Grundy, я подобрал. Два цикла означают, что из любой вершины в любую есть три разных пути. Длины циклов подбираются так чтобы эти пути имели разные остатки по модулю три. 11 мая в 18:03
  • но ведь остаток должен быть 0?
    – Grundy
    11 мая в 18:05
  • @Grundy, три пути - три разных остатка. Один должен быть нулём. 11 мая в 18:06
  • 1
    @Grundy, каждый цикл должен быть не кратен тройке. Циклы должны давать различные остатки при делении три. Этого достаточно, чтобы доказать что три пути дадут три различных остатка. Не совсем подбор. 11 мая в 20:38

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.