11 класс

Для начала рассмотрите вершины, у которых много соседних висячих вершин.

Разумеется, достаточно доказать теорему для случая, когда — дерево. Длиной ребра в графе мы назовем расстояние между его концами в исходном графе . Так, у графа бывают рёбра длин 1,2 и 3 . Доказательство будет индукцией по количеству вершин. База для дерева из трех вершин очевидна. Пусть для всех деревьев, имеющих меньше вершин, чем (и хотя бы три вершины), теорема уже доказана. Рассмотрим два случая.
а) В дереве существует вершина w, смежная хотя бы с двумя висячими вершинами. Пусть и — две висячие вершины, смежные с и . Можно считать, что , иначе утверждение для графа доказано в базе. В гамильтоновом цикле графа есть участок , который, очевидно, можно заменить на и получить гамильтонов цикл графа .
б) Любая невисячая вершина смежна не более, чем с одной висячей.

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

Назовем невезучими детей, которые ни разу еще не побывали в хорошей команде. Стратегия Дмитрия Андреевича состоит в том, чтобы каждый раз называть хорошей команду, куда попала большая часть невезучих.

Ответ: 5.

Решение. Назовем невезучими детей, которые ни разу еще не побывали в хорошей команде. Стратегия Дмитрия Андреевича состоит в том, чтобы каждый раз называть хорошей команду, куда попала большая часть невезучих. Так ему после первого боя удастся сделать так, чтобы невезучих было не более 15, после второго — не более 7 , после третьего — не более 3 , после четвертого — не более одного. С другой стороны, если дети каждый раз будут делиться так, чтобы количества невезучих в двух командах отличались не более, чем на 1 , Дмитрию Андреевичу не удастся сделать всех везучими за 4 боя.

Все маршруты образуют полный граф на 21 вершине, рёбра которого раскрашены в 4 цвета. Если искомого замкнутого маршрута нет, любые две вершины этого графа связаны не более чем одним одноцветным маршрутом длины 2.

Все маршруты образуют полный граф на 21 вершине, рёбра которого раскрашены в 4 цвета. Если искомого замкнутого маршрута нет, любые две вершины этого графа связаны не более чем одним одноцветным маршрутом длины 2. Стало быть, всего таких маршрутов не более, чем . С другой стороны, пусть из данной вершины выходит и рёбер первого, второго, третьего и четвёртого цветов соответственно. Тогда число одноцветных маршрутов длины 2 , для которых эта вершина — средняя, равно . По неравенству между средним арифметическим и средним квадратическим имеем: . Таким образом, каждая вершина нашего графа является средней минимум для одноцветных маршрутов, причём минимум достигается только в случае, когда из вершины выходит ровно по 5 маршрутов каждого цвета. И только в этом случае сумма количеств одноцветных маршрутов длины 2 по всем вершинам равна 840, в остальных — больше. Но такой случай невозможен, потому что тогда, оставив в нашем графе только рёбра одного какого-то цвета, мы получили бы граф с нечётным числом нечётных вершин.

Всего из дерева получается нечётное число графов, в которых добавлено ещё одно ребро.

Пусть — наш граф, — множество всех остовных деревьев графа , а М( ) — множество всех остовных подграфов графа , имеющих ровно один цикл. Рассмотрим произвольное дерево . В нем нечетное число ребер, следовательно, количество не вошедших в ребер графа также нечетно. Если к дереву добавить любое не вошедшее в него ребро графа , то получится граф из . Всего таким образом из дерева получается нечетное число графов из . Наоборот, рассмотрим любой граф и его единственный цикл . Граф может быть получен добавлением ребра к тем деревьям, которые получаются из удалением одного из ребер цикла . Так как граф двудольный, то в цикле — четное число ребер, следовательно, у графа — четное число остовных деревьев-«»предков»». Отсюда следует, что в множестве четное число остовных деревьев.

Покажите, что в цвет правильно раскрасить все вершины можно всегда.

Ответ. В цвет.

Решение: Покажем, что в цвет правильно раскрасить все вершины можно всегда. Раскрасим в цветов, назовём один из этих цветов первым, и пусть — совокупность всех вершин из , покрашенных в первый цвет. Теперь раскрасим в цветов, использовав в качестве одного из них первый цвет (а остальные цветов взяв отличными от уже использованных цветов). У вершин, не входящих в , сохраним прежнюю раскраску. Поскольку никакие вершины из не связаны рёбрами с вершинами из , покрашенными в первый цвет (из — в силу правильности раскраски в цветов, из — по условию), получится правильная раскраска графа в цвет.

Теперь покажем, что меньшего числа цветов может и не хватить. Расположим точек в виде прямоугольника из строк и столбцов. Примем это множество за . Снизу добавим нулевую строку из точек, примем ее за , слева нулевой столбец, примем его за . Ребрами в соединим любые две точки, не лежащие ни в одной строке, ни в одном столбце. В соединим рёбрами каждые две точки, в — тоже. Кроме того, соединим рёбрами каждую точку из со всеми точками из , не лежащими с ней в одном столбце, и каждую точку из со всеми точками из , не лежащими с ней в одной строке. Очевидны правильные раскраски в цветов (по столбцам) и в цветов (по строкам). Покажем, что полученный граф нельзя раскрасить меньше, чем в цвет. Допустим, есть правильная раскраска в цвета. Поскольку точки множества раскрашены в различных цветов, а точки множества — в различных цветов, то есть цветов (назовём их общими), в которые покрашены точки обоих этих множеств. Отметим строки и столбцы, в которых находятся такие точки; на их пересечении находится точек множества . Заметим, что в каждый из общих цветов может быть покрашено не больше одной из этих точек, а именно, точка, стоящая на пересечении соответствующих столбца и строки. Стало быть, среди этих точек есть точек, раскрашенных в другие цвета. Это не могут быть общие цвета, но не могут быть и другие цвета, использованные при раскраске точек множеств и , потому что со всеми точками таких цветов точки из отмеченных строк и столбцов связаны рёбрами. Всего при раскраске точек из и было использовано цветов. Из упомянутых выше точек можно выбрать точек, никакие две из которых не лежат в одной строке или одном столбце. Каждые две из этих точек связаны ребром, поэтому они раскрашены не менее, чем в цветов. Получается, что всего использовано не менее, чем цветов. Противоречие.

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

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

Пусть при проезде самым дешевым путем между городами и множества мы сначала доезжаем из до , потом летим из в по удешевленному рейсу, а затем долетаем из в . Тогда, если из сразу полететь в по пути наименьшей стоимости, мы заплатим меньшую цену за весь путь: ведь цена перелета между и все равно осталась положительной, и хотя бы эту цену мы сэкономим. Аналогичны рассуждения для двух вершин из множества . Поэтому путь минимальной стоимости между двумя вершинами одного множества не содержит рейс из в .

Обозначим количество городов в множестве через . Тогда в множестве всего городов. Стоимость самого дешевого пути между городами одного множества, как было показано выше, не уменьшилась. Значит, лишь между парами городов из разных множеств стоимость самого дешевого пути могла уменьшиться. Это количество пар не больше , по неравенству между средними арифметическим и геометрическим.

Новый самый дешевый путь между городами из разных множеств проходит по удешевленному ребру не более одного раза, а до удешевления стоимость такого же пути была не ниже стоимости самого дешевого пути между этими городами. Поэтому для каждой пары городов из разных множеств стоимость самого дешевого пути уменьшилась не более, чем на 1000. Значит, итоговая сумма будет отличаться от старой не более, чем на рублей.

Пронумеруем вершины, кроме Москвы, произвольным образом.
Будем красить города из большой Москвы в красный цвет, а их соседей в зелёный цвет. То есть мэру нужно покрасить городов в красный, а других городов в зелёный.

Теперь построим соответствие способу покраски способ расставить в ряд зелёных и красных символов (способов сделать это ). Для удобства сначала будем писать не просто символы, а номера городов, после чего забудем сами номера, оставив только строчку цветных символов.

Пронумеруем вершины, кроме Москвы, произвольным образом.
Будем красить города из большой Москвы в красный цвет, а их соседей в зелёный цвет. То есть мэру нужно покрасить городов в красный, а других городов в зелёный.

Теперь построим соответствие способу покраски способ расставить в ряд зелёных и красных символов (способов сделать это ). Для удобства сначала будем писать не просто символы, а номера городов, после чего забудем сами номера, оставив только строчку цветных символов.

На первом этапе алгоритма выпишем в возрастающем порядке номера городов, соседних с Москвой (все они покрашены!). При этом мы покрасим красные в розовый, а зелёные так и оставим зелёными. На очередном шаге будем брать строчку, брать в ней самый левый розовый номер , и записывать в конец строки номера всех его ещё не выписанных соседей (все они покрашены!) в порядке возрастания номеров, причём номера красных городов запишем розовым, а зелёных — зелёным. После чего поменяем цвет номера на красный.

Так как на каждом шаге количество красных номеров увеличивалось на 1 , то процесс закончится.
Докажем, что полученное отображение инъективно. Предположим, есть две покраски городов, дающие одну и ту же последовательность. Тогда существует символ, который соответствует разным номерам в раскрасках; рассмотрим самый левый такой символ. Пусть до него последовательности имели вид и . В каждой из раскрасок номера и появились как соседи красных вершин с выписанными ранее номерами. Но поскольку предыдущие символы совпадали, то должен был совпасть и номер на месте .

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

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

Докажем, что в графе для доли выполнено условие леммы Холла. Предположим противное. Рассмотрим в минимальное по включению множество , для которого условие леммы Холла не выполнено. То есть у вершин из количество соседей меньше, чем , а для любого подмножества множества количество соседей у вершин из хотя бы . Отсюда следует, что у ровно соседних вершин. Без ограничения общности будем считать, что , а это соседние вершины множества . Тогда для множества выполнена лемма Холла. Пусть без ограничения общности существует паросочетание . Значит, в словах , на местах соответственно стоят не звёздочки (пусть без ограничения общности там стоят нули). Рассмотрим маски . По построению в этих масках на местах с 1 по стоят звёздочки. Так как каждое слово можно получить из масок ровно одним способом, то из масок получаются не все слова. Значит, существует множество слов (на первых позициях стоит что угодно, а затем идёт слово длины ), которое нельзя получить из масок . Тогда слово нельзя получить ни из какой маски. Противоречие.

Следовательно, для доли выполнено условие леммы Холла. Рассмотрим любое паросочетание, покрывающее долю . Пусть это паросочетание , а в словах на местах соответственно стоят нули. Тогда чтобы получить слово нам нужна ещё хотя бы одна маска. Откуда и получаем оценку на .

Пусть минимум автобусной мобильности дает регион , а железнодорожной — регион . Пусть , а — совокупность всех городов, не входящих ни в , ни в .

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

Ответ. 1.

Решение: Оченка. Пусть минимум автобусной мобильности дает регион , а железнодорожной — регион . Пусть , а — совокупность всех городов, не входящих ни в , ни в .

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

Если ни один из сомножителей и не равен 0 , то , откуда .

Пусть . Тогда во множестве а элементов, откуда . При этом , откуда и . Случай аналогичен.

Пусть, наконец, , но . Если , то , откуда , противоречие. Итак, . Значит, любой из маршрутов между и учитывается в одной из мобильностей с коэффициентом, не меньшим , поэтому .

Пример. Пусть город связан с остальными только железнодорожными маршрутами, а город со всеми остальными, кроме , связан только автобусными маршрутами. Тогда автобусная мобильность города равна 0 , а железнодорожная мобильность города равна 1.

Лемма 1. (В.Л. Дольников). В графе вершин. Оказалось, что после выкидывания любой вершины графа найдется полный подграф с вершинами. Тогда в исходном графе найдется полный подграф с вершиной.

Лемма 2. Пусть — пересечение нескольких блоков графа , причем непусто. Тогда содержит не менее вершин.

Лемма 1. (В.Л. Дольников). В графе вершин. Оказалось, что после выкидывания любой вершины графа найдется полный подграф с вершинами. Тогда в исходном графе найдется полный подграф с вершиной.

Доказательство. Пусть утверждение леммы неверно. Будем считать наименьшим натуральным числом, для которого существует граф, не удовлетворяющий условию задачи. Рассмотрим граф , дополнительный к графу из условия. Рассмотрим любой пустой подграф графа с вершинами, множество его вершин обозначим через , а множество остальных вершин через . Назовем подмножество плохим, если количество вершин в нем больше количества вершин в , смежных хотя бы с одной вершиной из этого подмножества. Обозначим через максимальное плохое подмножество (оно может быть и пустым), пусть оно содержит вершин, тогда в нет плохих подмножеств, поэтому, в силу леммы Холла, каждой вершине можно сопоставить смежную с ней вершину таким образом, чтобы все эти вершины были различны и не смежны с вершинами из Y A. Множество не сопоставленных вершин обозначим через . Рассмотрим граф , образованный вершинами и ребрами графа , соединяющими эти вершины. Заметим, что при выкидывании любой вершины в графе должен был найтись пустой подграф с вершинами, но в него могло входить не более, чем вершина из ( ) , следовательно, остальные вершин должны быть из , поэтому в после выкидывания любой вершины найдется пустой подграф с вершинами, но тогда, в силу минимальности либо в найдется пустой подграф с вершинами, либо . В первом случае, добавляя к вершинам этого подграфа вершины из , получим пустой подграф с вершинами, во втором — выкинем вершину из , несмежную ни с одной вершиной , найдем пустой подграф с вершинами и добавим к нему эту вершину, получим пустой подграф с вершинами. Полученное противоречие доказывает утверждение леммы.

Обозначим через разность максимальной степени графа и . Из условия следует, что .

Лемма 2. Пусть — пересечение нескольких блоков графа , причем непусто. Тогда содержит не менее вершин.

Доказательство. Пусть — объединение всех блоков, содержащих . Тогда , поскольку любая вершина из смежна с любой вершиной из . Ясно, что любой блок, содержащий , имеет не менее вершин в . Пусть . Заметим, что при выкидывании любой вершины из найдется блок, содержащий , но не содержащий выкинутой вершины (поскольку — пересечение всех блоков, содержащих ). Но в нет подграфов, содержащих более вершин (иначе объединение такого подграфа с будет полным подграфом графа , содержащим более вершин). Тогда содержит не менее вершин в силу леммы 1 . Следовательно, , откуда . Лемма доказана.

Завершение доказательства. Рассмотрим любой блок. Назовем его Н. Рассмотрим пересечение всех блоков, имеющих непустое пересечение с (включая ). Будем добавлять эти блоки по одному и следить за пересечением. До тех пор, пока оно непусто, оно содержит не менее вершин, в силу леммы 2 . Но тогда следующий добавляемый подграф должен иметь не менее общих вершин с (в силу леммы 2 ), но (по условию ), следовательно новый блок имеет непустое пересечение с пересечением старых.