В стране 100 городов некоторые из которых соединены авиалиниями
В стране 100 городов, некоторые из которых соединены авиалиниями. Известно, что от каждого города можно долететь до любого другого (возможно, с пересадками). Докажите, что можно побывать во всех городах, совершив не более а) 198 перёлетов; б) 196 перелётов.
Решение
б) Рассмотрим соответствующий граф и выделим из него максимальное дерево (см. задачу 30789 а).
Докажем по индукции, что в дереве с n вершинами (n > 2) существует обходящий все вершины маршрут длины не более 2n – 4. База (n = 3) очевидна.
Шаг индукции. Рассмотрим висячую вершину А (см. задачу 30786) и удалим её и выходящее из неё ребро АВ. По предположению индукции в оставшемся дереве есть обходящий его маршрут длины 2n – 6. Вставив в него кусок ВАВ получим маршрут длины 2n – 4, обходящий исходное дерево.
Источники и прецеденты использования
книга | |
Автор | Генкин С.А., Итенберг И.В., Фомин Д.В. |
Год издания | 1994 |
Название | Ленинградские математические кружки |
Издательство | Киров: «АСА» |
Издание | 1 |
глава | |
Номер | 13 |
Название | Графы-2 |
Тема | Теория графов |
задача | |
Номер | 016 |
В стране 100 городов некоторые из которых соединены авиалиниями
Руководитель Марачев Алексей
2007/2008 учебный год
Бонусные задачи 1.
- ЗАДАЧИ
- 6 класс
- Бонусные задачи 1
- Занятие 1
- Домашнее задание 1
- Занятие 2
- Домашнее задание 2
- Занятие 3
- Домашнее задание 3
- Занятие 4
- Домашнее задание 4
- Занятие 5
- Домашнее задание 5
- Занятие 6
- Домашнее задание 6
- Занятие 7
- Домашнее задание 7
- Занятие 8
- Домашнее задание 8
- Занятие 9
- Домашнее задание 9
- Занятие 10
- Домашнее задание 10
- Занятие 11
- Домашнее задание 11
- Занятие 12
- Занятие 14
- Домашнее задание 14
- Занятие 15
- Домашнее задание 15
- Занятие 16
- Домашнее задание 16
- Занятие 17
- Домашнее задание 17
- Занятие 18
- Домашнее задание 18
- Занятие 19
- Занятие 20
- Занятие 23
- Домашнее задание 23
- Занятие 24
- Домашнее задание 24
- Занятие 25
- Домашнее задание 25
Вы видите ошибку? Выделите её и нажмите Ctrl+Enter! | | | |
Задача о городах
В стране 100 городов, некоторые из которых соединены авиалиниями. Известно, что от любого города можно долететь до любого другого (возможно, с пересадками). Докажите, что можно побывать в каждом городе, совершив не более а) 198 перелетов; б) 196 перелетов.
Решение нашёл только такое:
а), б) Поставим в соответствие каждому городу вершину графа, причем вершины, соответствующие городам между которыми есть прямое авиасообщение, соединим отрезком. По условию полученный граф связен. Теперь достаточно рассмотреть максимальное дерево (конечно, таких деревьев несколько), содержащееся в этом графе, и выбрать путь, соединяющий две висячие вершины дерева. Дальнейшее очевидно.
Как вы сами понимаете, это не решение, а мазня. Не могли бы вы предложить более корректное решение задачи?
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
Ответы с готовыми решениями:
Задача о трех городах
Такая задача. Есть 3 города А,Б,В. Расстояние между городами известно и города расположены не на.
Задача о дорогах и городах
Ввод: input.txt Вывод: output.txt Есть K городов, соединенных между собой N.
Работа с классами и пересечение их между собой (задача о городах и поездах)
Здравствуйте. Тут попалась в руки задачка, вкратце суть: Есть города, в каждом городе есть.
Реки в городах
1)Программа, которая на запрос реки(,P) выводила P = . 2)Как известно, n! = 1*2*3*…*n.
В стране 100 городов некоторые из которых соединены авиалиниями
Задача по математике — 3384
2019-06-03
В стране 15 городов, некоторые из них соединены авиалиниями, принадлежащими трем авиакомпаниям. Известно, что даже если любая из авиакомпаний прекратит полеты, можно будет добраться из любого города в любой другой (возможно, с пересадками), пользуясь рейсами оставшихся двух компаний. Какое наименьшее количество авиалиний может быть в стране?
Докажем, что меньше, чем 21 авиалинией не обойтись. Вначале заметим, что если 15 городов соединены авиалиниями так, что можно добраться от любого города до любого другого, то авиалиний не меньше 14. Действительно, вылетим из произвольного города, и попробуем объехать все остальные, при этом, посещение каждого следующего города будет требовать не менее одной новой авиалинии.
Обозначим количество линий у авиакомпаний через $a, b$ и $c$. По доказанному, у любых двух компаний вместе не менее 14 линий, т. е. $a + b \geq 14, b + c \geq 14, c + a \geq 14$. Складывая эти неравенства, получаем: $2 (a + b + c) \geq 42$, т. е. у трех компаний в сумме не менее 21 авиалинии.
Осталось привести пример с 21 авиалинией. Два таких примера показаны на рис.
Ответ: 21 авиалиния.