В стране имеются города некоторые из которых

В стране имеются города некоторые из которых

В стране 100 городов, некоторые из которых соединены авиалиниями. Известно, что от каждого города можно долететь до любого другого (возможно, с пересадками). Докажите, что можно побывать во всех городах, совершив не более а) 198 перёлетов; б) 196 перелётов.

Решение

б) Рассмотрим соответствующий граф и выделим из него максимальное дерево (см. задачу 30789 а).
Докажем по индукции, что в дереве с n вершинами (n > 2) существует обходящий все вершины маршрут длины не более 2n – 4. База (n = 3) очевидна.
Шаг индукции. Рассмотрим висячую вершину А (см. задачу 30786) и удалим её и выходящее из неё ребро АВ. По предположению индукции в оставшемся дереве есть обходящий его маршрут длины 2n – 6. Вставив в него кусок ВАВ получим маршрут длины 2n – 4, обходящий исходное дерево.

В стране имеются города некоторые из которых

В стра­не 20 го­ро­дов, не­ко­то­рые из ко­то­рых со­еди­не­ны авиа­ли­ни­я­ми. Бес­по­са­доч­ный перелёт из A в 5 назовём цен­тра­ли­зу­ю­щим, если из 5 можно в боль­шее, чем из A, число го­ро­дов до­ле­теть без пе­ре­сад­ки. Какое наи­боль­шее число го­ро­дов может на­счи­ты­вать авиа­марш­рут, все перелёты на ко­то­ром цен­тра­ли­зу­ю­щие?

Через |A|, где A  — про­из­воль­ный город, обо­зна­чим число го­ро­дов, со­единённых бес­по­са­доч­ны­ми авиа­ли­ни­я­ми с A. Будем рас­смат­ри­вать авиа­марш­рут, ко­то­рый про­хо­дит по­сле­до­ва­тель­но через го­ро­да и все перелёты на ко­то­ром цен­тра­ли­зу­ю­щие. Ясно, что тогда

Ра­вен­ство не­воз­мож­но, по­сколь­ку имело бы сво­и­ми след­стви­я­ми вза­и­мо­ис­клю­ча­ю­щие ра­вен­ства и

До­пу­стим, что и Тогда то есть город A₁₇ со­единён либо с A₁, либо с A₂. Но A₁ со­единён с A₂ и A₁₈, а A₂  — с A₁, A₃ и A₁₈.

На­ко­нец, пред­по­ло­жим, что и Тогда A₁ со­единён с A₂; A₂ со­единён с A₁ и A₃. По­лу­ча­ет­ся, что город A₁₈ не со­единён ни с A₁, ни с A₂, а тогда ра­вен­ство не­воз­мож­но. Итак, При­ведём при­мер си­сте­мы авиа­ли­ний, для ко­то­рой все перелёты на марш­ру­те, про­хо­дя­щем по­сле­до­ва­тель­но через го­ро­да A₁, A₁₇, цен­тра­ли­зу­ю­щие. Пусть го­ро­да A_i и A_j со­еди­не­ны, если вы­пол­не­но хотя бы одно из сле­ду­ю­щих трёх усло­вий:

В стране имеются города некоторые из которых

Определение. Путь, содержащий все ребра графа, называется эйлеровым путем.

4. Докажите, что если в графе более двух вершин с нечетными степенями, то в этом графе нет эйлерова пути. 5. Докажите, что если в графе степени всех вершин чётны, то в этом графе есть цикл. 6. Докажите, что если в графе степени всех вершин чётны, то рёбра этого графа можно разбить на несколько циклов. 7. Докажите, что если два цикла имеют общую вершину, то их можно объединить в один самопересекающийся цикл. 8. Докажите, что если в связном графе степени всех вершин чётны, то в этом графе есть эйлеров цикл. 9. Докажите, что если в связном графе ровно две вершины с нечетными степенями, то в этом графе есть эйлеров путь. 10. При каких n правильный n-угольник со всеми его диагоналями можно нарисовать не отрывая карандаша? 11. Город представляет из себя квадрат 3 на 3, в котором каждая сторона квартала-квадратика — участок улицы длиной 300 метров. Какой наименьший путь придётся проделать катку, чтобы заасфальтировать улицы?

Как решить: в стране 11 городов, некоторые сединены дорогами (см.внутри)?

Залача из Всероссийской олимпиады школьников, математика 7 класс.

В стране 11 городов, некоторые соединены дорогами (каждая дорога соединчет два различных города, никакие два города не соединены больше, чем одной дорогой). Всего в стране 29 дорог. Известно, что из всех городов выходит одинаковое количество дорог, а из столицы — другое.

1. Сколько дорог выходит из столицы?
2. Сколько дорог выходит из нестоличного города?

Есть 10 обычных городов и столица — 11-ый город.

Из столицы выходит n дорог в другие города, n <= 10.

А из других 10 городов выходит 10k дорог, по k дорог из каждого города.

Из n городов идет n дорог в столицу (по 1 дороге из каждого города), а остальные 10k-n дорог идут в другие города.

Но каждая дорога соединяет два города, поэтому дорог, соединяющих нестоличные города, всего должно быть:

А всего дорог 29

(10k — n) : 2 + n = 29

Из столицы выходит 8 дорог.

Из каждого нестоличного города выходит по 5 дорог.

Вот я нарисовал схему. Всего 29 дорог, они перенумерованы.

Из каждого города выходит по 5 дорог (черные), а из столицы 8 дорог (красные).

Дети решают такие задачи методом подбора.

Вот пример решения этой задачи одним моим учеником. Так как из каждого нестоличного города (их всего 11-1=10) выходит одинаковое количество дорог, то начнем с того, пусть из каждого из них выходит 1 дорога. Значит всего 10 дорог из обычных городов. По условию всего в стране 29 дорог. Тогда получается, что из столицы выходят 19 дорог (29-10=19). Но это невозможно, так как всего городов 11, значит из столицы может максимум 10 дорог. Проверим 2, пусть из каждого из нестоличного города выходят 2 дороги, всего 20 дорог из обычных городов. По условию всего в стране 29 дорог. Тогда получается, что из столицы выходят 9 дорог (29-20=9). Вот и ответ.

Но на самом деле дети не учитывают того, что одна дорога учитывается дважды. То есть 20 дорог, это фактически 10. Поэтому если из каждого обычного города выходят 4 дороги, то всего дорог будет не 40, а 20. Если из столицы выходят 9 дорог, то при суммировании это будет 4,5. Что невозможно.

Значит из столицы должны выходит четное количество дорог. Продолжим. Пусть из каждого из обычных городов выходят 5 дорог. Значит всего 25 (50/2=25). По условию всего в стране 29 дорог. Тогда получается, что из столицы выходят 4 дороги (29-25=8, 8/2=4). Ответ: 4 и 5.