в стране Оз есть много городов некоторые из которых соединены дорогами. каждая из дорог вымощена либо жёлтым либо красным
Мы отправили письмо со ссылкой на смену пароля на username@mail.ru.
Если письма нет, проверь папку «Спам».
Чтобы вопрос опубликовался, войди или зарегистрируйся
Нужна регистрация на Учи.ру
«Ваш урок» теперь называется Учи.Ответы. Чтобы зайти на сайт, используй логин и пароль от Учи.ру. Если у тебя их нет, зарегистрируйся на платформе.
В стране имеются города некоторые из которых
В стране 100 городов, некоторые из которых соединены авиалиниями. Известно, что от каждого города можно долететь до любого другого (возможно, с пересадками). Докажите, что можно побывать во всех городах, совершив не более а) 198 перёлетов; б) 196 перелётов.
Решение
б) Рассмотрим соответствующий граф и выделим из него максимальное дерево (см. задачу 30789 а).
Докажем по индукции, что в дереве с n вершинами (n > 2) существует обходящий все вершины маршрут длины не более 2n – 4. База (n = 3) очевидна.
Шаг индукции. Рассмотрим висячую вершину А (см. задачу 30786) и удалим её и выходящее из неё ребро АВ. По предположению индукции в оставшемся дереве есть обходящий его маршрут длины 2n – 6. Вставив в него кусок ВАВ получим маршрут длины 2n – 4, обходящий исходное дерево.
В стране имеются города некоторые из которых
Определение. Путь, содержащий все ребра графа, называется эйлеровым путем.
4. Докажите, что если в графе более двух вершин с нечетными степенями, то в этом графе нет эйлерова пути. 5. Докажите, что если в графе степени всех вершин чётны, то в этом графе есть цикл. 6. Докажите, что если в графе степени всех вершин чётны, то рёбра этого графа можно разбить на несколько циклов. 7. Докажите, что если два цикла имеют общую вершину, то их можно объединить в один самопересекающийся цикл. 8. Докажите, что если в связном графе степени всех вершин чётны, то в этом графе есть эйлеров цикл. 9. Докажите, что если в связном графе ровно две вершины с нечетными степенями, то в этом графе есть эйлеров путь. 10. При каких n правильный n-угольник со всеми его диагоналями можно нарисовать не отрывая карандаша? 11. Город представляет из себя квадрат 3 на 3, в котором каждая сторона квартала-квадратика — участок улицы длиной 300 метров. Какой наименьший путь придётся проделать катку, чтобы заасфальтировать улицы?
В стране имеются города некоторые из которых
В стране 20 городов, некоторые из которых соединены авиалиниями. Беспосадочный перелёт из A в 5 назовём централизующим, если из 5 можно в большее, чем из A, число городов долететь без пересадки. Какое наибольшее число городов может насчитывать авиамаршрут, все перелёты на котором централизующие?
Через |A|, где A — произвольный город, обозначим число городов, соединённых беспосадочными авиалиниями с A. Будем рассматривать авиамаршрут, который проходит последовательно через города и все перелёты на котором централизующие. Ясно, что тогда
Равенство невозможно, поскольку имело бы своими следствиями взаимоисключающие равенства и
Допустим, что и Тогда то есть город A17 соединён либо с A1, либо с A2. Но A1 соединён с A2 и A18, а A2 — с A1, A3 и A18.
Наконец, предположим, что и Тогда A1 соединён с A2; A2 соединён с A1 и A3. Получается, что город A18 не соединён ни с A1, ни с A2, а тогда равенство невозможно. Итак, Приведём пример системы авиалиний, для которой все перелёты на маршруте, проходящем последовательно через города A1, A17, централизующие. Пусть города Ai и Aj соединены, если выполнено хотя бы одно из следующих трёх условий: