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

задан 7 Мар 10:31

Никаких идей если честно.

(7 Мар 10:31) RGubareva
10|600 символов нужно символов осталось
0

Контрпример. Нарисуйте пятиугольник АВСDЕ. Каждая сторона пятиугольника - это два моста в два направления (например АВ - это мост из А в В и одновременно из В в А). Тогда в соседние вершины проходили по одному мосту, а в несоседние - по двух мостах. Граф удовлетворяет условию. Пусть перекрыли мост, которым можно было доехать из А в В. Тогда сейчас длина пути из А в В будет равна 4 (АЕ+ЕD+DC+СВ).

Р.S. Условие задачи не запрещает два острова соединять двумья мостами (для ориентированных графов это естественно), а если бы запрещало, то условие задачи никогда не имело бы места. Доказательство. Допустим, я неправильно понял условие и максимум один мост между двумья островами. Пусть у нас четыри острова. Тогда максимум 6 мостов. Рисуем все шесть. Каждый остров имеет ровно 3 моста. Входящими мостами острова назовьем те, по которых можна заехать на остров. Допустим, каждый остров имеет не более одного входящего моста. Тогда всех мостов не более четырех. Противоречие, ибо их 6. Следовательно, найдется остров со двумья входящими мостами. Пусть это остров А, а эти входящие мосты входят в него с островов С и D. Из острова А можна уехать только по одному мосту. Пусть этот мост соединяет А и В. Чтобы из А попасть в С и D должны из В выходить два моста - один в С, другой - в D. Мы уже построили 5 мостов, кроме моста между С и D. Нарисуйте это и увидите, что нельзя обеспечить переезд из С в D и одновременно из D в С. Пришли к противоречию. И зачем я столько доказываю очевидное понимание условия задачи?

ссылка

отвечен 7 Мар 14:42

изменен 7 Мар 20:34

1

Тут, я думаю, другое имеется ввиду. Любые два острова соединены ОДНИМ мостом, по которому можно ехать только в одну сторону. С любого острова можно попасть на любой другой не болеее чем по двум мостам -- это означает попасть из острова А в В можно либо сразу, либо сначала из А в С, а потом с С в В (всего два моста)

(7 Мар 15:03) Роман83

Спасибо, пример очень понятный.

(7 Мар 15:06) RGubareva
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×585
×133

задан
7 Мар 10:31

показан
201 раз

обновлен
7 Мар 20:34

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru