Деревья и остовные деревья
Ошибка.
Попробуйте повторить позже
Дан граф 
на 
вершинах: сопоставим каждой вершине 
переменную 
. Пусть 
— множество остовных
деревьев графа 
(то есть поддеревьев, содержащих все вершины). Рассмотрим остовный многочлен от 
переменных
Назовем связный граф хорошим, если 
раскладывается на линейные множители (в частности, если 
— тождественный
ноль), иначе плохим.
1. Найдите 
, где 
— полный граф на 4 вершинах.
2. Докажите, что цикл на пяти вершинах является плохим графом.
3. Пусть 
— хороший граф, 
— некоторое подмножество его вершин. Граф 
состоит из всех вершин, лежащих в 
, и всех ребер
графа 
, соединяющих эти вершины. Докажите, что граф 
тоже хороший.
4. Назовём раздвоением вершины 
операцию, добавляющую в граф вершину 
, соединенную ровно с теми же вершинами, что и 
.
Докажите, что граф, получающийся из одной вершины операциями добавления висячей вершины, раздвоения вершины с добавлением ребра
и раздвоения вершины без добавления ребра 
, является хорошим.
Источники:
Пункт 1, подсказка 1
Нас просят найти значения многочлена для графа К₄. Может, стоит подумать о его остовных деревьях?
Пункт 1, подсказка 2
В К₄ бывает только 2 вида остовных деревьев. Это либо цепь длины 4, либо три вершины, "висящие" на четвертой. А что нам дадут данные деревья в основный многочлен?
Пункт 1, подсказка 3
Остовные деревья первого вида дадут xᵢxⱼ, а второго - (xᵢ)², где i - вершина остова. Осталось только аккуратно записать искомый многочлен.
Пункт 2, подсказка 1
Для начала, как и в прошлом пункте, рассматриваем остовные деревья и записываем многочлен.
Пункт 2, подсказка 2
Проверьте, у Вас должен был получиться такой многочлен: x₁x₂x₃ + x₂x₃x₄ + x₃x₄x₅ + x₄x₅x₁ + x₅x₁x₂. Вспомните, какой граф мы называем "плохим"?
Пункт 2, подсказка 3
Заметим, что наш многочлен линеен по каждой переменной. Попробуйте показать, что у нас каждая переменная будет "жить" лишь в одной из скобок.
Пункт 2, подсказка 4
Убедитесь, что переменные разбиваются только на скобки вида 2-2-1 и 3-1-1. Что из этого следует?
Пункт 3, подсказка 1
Давайте подумаем, как связность U будет влиять на остовный многочлен?
Пункт 3, подсказка 2
Если U несвязно, то в качестве многочлена мы получим 0. А можем ли мы при связном U выкидывать по одной вершины с сохранением связности?
Пункт 3, подсказка 3
Давайте "подвесим" граф за множество U и будем удалять вершины, начиная с самого нижнего уровня. Что тогда получится?
Пункт 3, подсказка 4
Удалим вершину v. Это равносильно подстановке 0 в xᵥ. Какой вывод можно получить?
Пункт 3, подсказка 5
У нас получится, что все слагаемые c xᵥ обнуляются, следовательно, останутся лишь те, где v - висячая вершина. Как устроены такие деревья?
Пункт 3, подсказка 6
Мы выбираем дерево в графе G\{v}, а потом одна из вершин окрестности v соединяется с v. Какой вид у нас примет тогда остовный многочлен?
Пункт 3, подсказка 7
Докажите, что многочлен останется раскладываемым на множители.
Пункт 4, подсказка 1
Пусть G₁ - граф, получаемый из G на n вершинах добавлением вершины vₙ₊₁, как в операции раздвоения вершины. Давайте для начала подумаем про остовный многочлен графа G. Надо понять, как устроены деревья этого графа.
Пункт 4, подсказка 2
Возьмем лес на всех вершинах, кроме vₙ. Что обязательно должно быть в каждой его компоненте?
Пункт 4, подсказка 3
В каждой компоненте должна быть хотя бы одна вершина из окрестности vₙ в графе G. Как должна быть связана вершина vₙ с этим множеством?
Пункт 4, подсказка 4
vₙ будет соединена ровно с одной такой вершиной из каждой компоненты. Как тогда может быть представлен наш остовный многочлен?
Пункт 4, подсказка 5
Обозначьте за L множество таких лесов, за t(K) - число компонент связности в лесу K, за A₁, A₂, ... , Aₜ - множества пересечений окрестности вершины v в графе G с компонентами связности леса K. Запишите многочлен, пользуясь этими обозначениями.
Пункт 4, подсказка 6
Теперь посмотрим на деревья в графе G₁. Какой лес мы возьмем там?
Пункт 4, подсказка 7
Мы вновь возьмем лес, содержащий все вершины, кроме vₙ, но теперь еще не будем брать вершину vₙ₊₁. Снова подумаем, что должно быть в каждой его компоненте.
Пункт 4, подсказка 8
Как и ранее, в каждой компоненте должна быть хотя бы одна вершина из окрестности vₙ в графе G, после чего одна из долей будет соединена с вершинами vₙ и vₙ₊₁, а все остальные доли - лишь с одной из них. Теперь запишите и преобразуйте остовный многочлен графа G₁, используя те же обозначения, что и для графа G.
Пункт 4, подсказка 9
У Вас должно получиться, что для графа G₁ остовный многочлен от (x₁, x₂, ..., xₙ₊₁) равен остовному многочлену для графа G от (x₁, x₂, ..., xₙ + xₙ₊₁), умноженному на сумму вершин из окрестности vₙ в графе G.
Пункт 4, подсказка 10
Давайте теперь рассмотрим граф G₂, получаемый из G₁ соединением вершин vₙ и vₙ₊₁. Может быть, леса G₁ и G₂ похожи?
Пункт 4, подсказка 11
Мы снова рассмотрим лес, как с графом G₁, но теперь либо не будем проводить ребро между vₙ и vₙ₊₁, либо проведем и соединим каждую из долей ровно с одной из вершин. Какие выводы можно сделать из этих построений?
Пункт 4, подсказка 12
В первом случае мы получим такое же слагаемое, как в G₁. Тогда что нам дает сумма таких слагаемых?
Пункт 4, подсказка 13
Эти слагаемые дадут нам остовный многочлен графа G₁. Осталось только разобраться с суммой вторых слагаемых. Это можно сделать при помощи тех же обозначений, что и для графа G.
1. В полном графе на четырех вершинах есть только 2 вида остовных деревьев: 1) цепь длины 4; 2) три вершины, "висящие"на четвертой.
Каждое дерево первого вида даст в остовный многочлен одночлен 
, 
, причем каждый одночлен будет представлен 2
раза.
Каждое дерево второго вида даст в остовный многочлен одночлен 
, где 
— "вершина"остова.
В итоге получим многочлен:
________________________________________________________________________________________________________________________________________________________________________________________________________
2. Распишем 
. Поскольку многочлен 
линеен по каждой переменной, получаем,
что каждая из переменных живет только в одной из скобок. Тогда переменные вынуждены разбиться на скобки 2-2-1 или 3-1-1, что дает нам
не более четырех мономчиков, противоречие.
_________________________________________________________________________________________________________________________________________________________________________________
3. Давайте сначала заметим, что можно последовательно выкидывать вершины по одной с сохранением связности, если 
связно. (Если
несвязно, то просто 0 получится и все).
Для этого нужно подвесить за 
и поочередно удалять вершины с самого нижнего уровня. Теперь нужно понять, что при удалении
только одной вершины 
граф остается хорошим. Для этого подставим 0 в 
. Получим, что все слагаемые, в которые 
входило в хотя
бы первой степени, обнулились, а значит остались в точности те, где 
— висячая вершина. А все такие деревья устроены так: выбрано
дерево в графе 
, и потом одна из вершин из окрестности 
соединена с 
. Тогда многочлен после подстановки нуля равен
. Подстановка нуля сохраняет раскладываемость на множители, значит 
тоже раскладываемый,
значит, при удалении вершины 
граф останется хорошим.
_________________________________________________________________________________________________________________________________________________________________________________
4. Сначала докажем вспомогательный факт про такой тип графов.
Лемма о раздвоении без добавления ребра. Пусть дан граф 
на 
вершинах. Рассмотрим граф 
, полученный из 
добавлением вершины 
и соединением ее со всеми вершинами из 
, но не самой 
. Тогда
Доказательство. Давайте заметим, что любое дерево в графе 
устройство следующим образом — на всех вершинах, кроме 
,
берется некоторый лес, такой, что в каждой компоненте есть хотя бы одна вершина из 
, и потом вершина 
соединяется с ровно
одной вершиной из каждой компоненты. Обозначим за 
множество всех таких лесов, за 
— число компонент связности в лесу
, и назовем 
пересечения множеств 
с компонентами связности леса 
. Тогда из рассуждений
выше
Теперь давайте поймём, как устроены деревья в 
. Там мы тоже берём лес, который содержит все вершины, кроме 
, 
, и
такой, что каждая его компонента содержит хотя бы одну вершину из 
, после чего одна из долей соединяется с обеими вершинами
из 
и 
, а каждая из остальных 
долей — с ровно одной из этих вершин. Тогда в тех же обозначениях получается,
что
Теперь очевидно, что второй сомножитель равен 
, и лемма доказана.
Лемма 2 (Лемма о раздвоении с добавлением ребра). Пусть дан граф 
. Рассмотрим граф 
, получаемый из 
добавлением вершины 
и соединением её со всеми вершинами из 
, а также с самой 
. Тогда
Доказательство. Пусть 
— граф из леммы 
Мы в лемме 
уже выяснили как устроены деревья в графе 
поэтому нужно
разобраться с тем, как они устроены в 
. Заметим, что они устроены так: мы снова берем лес с такими же условиями, а дальше делаем
одно из двух — либо не проводим ребро между 
и 
, и это слагаемое такое же как в 
, либо проводим, и тогда каждую из
долей соединяем с ровно одной из этих вершин. Стало быть, сумма всех первых слагаемых даст нам 
, а сумма вторых
равна
Тогда получается, что
доказали требуемое.
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
