Индукция в графах и теорема Турана
Готовиться с нами - ЛЕГКО!
Ошибка.
Попробуйте повторить позже
В стране из 
городов некоторые города соединены дорогами, по которым можно двигаться в обе стороны. Известно, что в этой стране
нет циклического маршрута. При каком наибольшем 
всегда можно выбрать 
городов так, чтобы каждый выбранный город был
соединен не более чем с двумя из остальных выбранных?
Подсказка 1
Пусть города будут вершинами, а дороги ребрами в графе. В этой задаче сначала удобно понять, каким k быть не может. Для этого достаточно построить пример, который не работает для большого k. Какой подграф мешает данному k быть ответом?
Подсказка 2
Верно! Мешает подграф, который соединен с тремя вершинами. Если весь граф — это 250 таких подграфов, то при каком k условие задачи не выполнится?
Подсказка 3
Точно, при k ≥ 751! Итак, надо доказать, что k = 750. Если граф несвязен, то сделать его связным легко, поэтому можно считать, что он связный. Заметим, наше k — это три четверти числа вершин. Попробуем индукцией по числу вершин n показать, что k ≥ 3n/4. Как это сделать?
Подсказка 4
Мы выяснили, что граф можно считать связным. На самом деле понятно, что можно даже считать его деревом. При n = 1, 2, 3, 4 база индукции очевидна. Для перехода сначала подвесим наше дерево. Что можно сказать про самую глубокую вершину в дереве?
Подсказка 5
Верно! Если у ее предка хотя бы три потомка, то можно выкинуть этого предка и всех его потомков. В этом случае переход очевиден. А что можно сделать, если потомков ровно 2?
Подсказка 6
Верно! Можно посмотреть на предка этого предка. Удаляем двух потомков и двух предков (можно добавить ребра после удаления, если нужно). Тогда по предположению индукции можно получить хорошее множество вершин. Как теперь получить хорошее множество с нужным k в нашем графе?
Подсказка 7
Верно! У нас нашлось хорошее множество, в котором хотя бы 3(n-4)/4 вершин, а из удаленных ранее можно к нему добавить еще 3. Остается случай, когда степени предков вершин нижнего уровня равны 2. Как можно доказать нужное неравенство в этом случае?
Подсказка 8
Посмотрим снова на вершину нижнего уровня v, предка v — вершину u, и предка u - вершину w. Что можно сказать о графе, если удалить w с потомками (не обязательно прямыми)?
Подсказка 9
Точно! Если этих потомков было k, то хорошее множество в новом графе содержит хотя бы 3(n-k-1)/4 вершин. К нему можно добавить k потомков w, и в случае k ≥ 3 все получится. А на какой уже рассмотренный случай похож случай k ≤ 2?
Пример. Назовем пауком город, соединенный ровно с тремя другими, попарно не соединенными дорогами. Рассмотрим 
пауков (всего
1000 городов). Если 
то в одном из пауков выбраны все 4 города, что противоречит условию.
Оценка. Рассмотрим граф: вершины — города, рёбра — дороги. Если граф не связный, будем проводить по ребру между
компонентами связности, пока он не станет связным. Ясно, что такая процедура не увеличит искомое число 
и не добавит в граф
циклы.
Итак, мы можем считать, что рассматриваемый граф — дерево. Индукцией по 
докажем, что в дереве на 
вершинах можно выбрать
вершин так, чтобы выполнялось условие задачи. Такое множество вершин будем называть хорошим.
База: 
очевидна.
Переход: от всех меньших 
к 
Подвесим дерево за вершину и рассмотрим вершину 
самого нижнего уровня. Если у ее
предка 
не менее трёх потомков, то выкинем 
и всех ее потомков. В оставшемся дереве выберем хорошее множество и
добавим всех потомков 
Полученное множество будет хорошим для исходного дерева, и в нём не менее 
вершины.
Если у вершины 
ровно 
потомка 
и 
то рассмотрим её предка 
Выкинем вершины 
и 
и, если понадобится,
добавим рёбра для того, чтобы получилось дерево. В получившемся дереве выберем хорошее множество из не менее 
вершин, после
чего добавим к нему вершины 
и 
Итак, мы можем считать, что у любой вершины с нижнего уровня предок имеет степень ровно 
Пусть 
— вершина нижнего уровня,
— её предок, 
— предок 
У всех потомков (не обязательно прямых) 
степень 
или 
Если у 
всего 
потомков (не
обязательно прямых). Выкинем 
и всех её (не обязательно прямых) потомков. В оставшемся графе хорошее множество содержит не менее
вершин. Добавим в ним всех 
потомков 
Получим хорошее множество из не менее 
вершин в
исходном дереве.
Наконец, если 
то единственные потомки 
— это 
и 
Пусть 
— предок 
Выкинем вершины 
и 
В
получившемся графе выберем хорошее множество из не менее 
вершин, после чего добавим к нему вершины 
и
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
