Top.Mail.Ru

Часто ищут

Разделы

Бесплатно

Тема . Графы и турниры

Деревья и остовные деревья

Вспоминай формулы по каждой теме
Решай новые задачи каждый день
Вдумчиво разбирай решения
ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!
Подтемы раздела графы и турниры
Решаем задачу:

Ошибка.
Попробуйте повторить позже

Задача 1#83388

Дан граф G =(V,E)  на n  вершинах: сопоставим каждой вершине v  переменную x
 v  . Пусть T  — множество остовных деревьев графа G  (то есть поддеревьев, содержащих все вершины). Рассмотрим остовный многочлен от n  переменных x1,...,xn

                ∑  ∏  deg v−1
PG(x1,x2,...,xn)=       xv  S  .
               S∈Tv∈V

Назовем связный граф хорошим, если PG (x1,...,xn)  раскладывается на линейные множители (в частности, если PG  — тождественный ноль), иначе плохим.

1. Найдите PK4(1,2,3,4)  , где K4  — полный граф на 4 вершинах.

2. Докажите, что цикл на пяти вершинах является плохим графом.

3. Пусть G  — хороший граф, U  — некоторое подмножество его вершин. Граф H  состоит из всех вершин, лежащих в U  , и всех ребер графа G  , соединяющих эти вершины. Докажите, что граф H  тоже хороший.

4. Назовём раздвоением вершины v  операцию, добавляющую в граф вершину v′ , соединенную ровно с теми же вершинами, что и   v  . Докажите, что граф, получающийся из одной вершины операциями добавления висячей вершины, раздвоения вершины с добавлением ребра   ′
vv и раздвоения вершины без добавления ребра   ′
vv , является хорошим.

Источники: ЮМШ - 2024, сюжет 2 (см. yumsh.ru)

Подсказки к задаче

Пункт 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.

Сообщить об ошибке
Подсказки
Ответ и решение
Сообщить об ошибке

Специальные программы

Все специальные программы

Программа
лояльности вер. 2.0

Приглашай друзей в Школково и получай вознаграждение до 10%!

Крути рулетку
и выигрывай призы!

Крути рулетку и покупай курсы со скидкой, которая привязывается к твоему аккаунту.

Бесплатное онлайн-обучение

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

Налоговые вычеты

Узнай, как получить налоговый вычет при оплате обучения в «Школково».

Специальное предложение
для учителей

Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас важно быть полезными учителям по всей России!

Вернём деньги за курс
за твою сотку на ЕГЭ

Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!

cyberpunkMouse
cyberpunkMouse
Рулетка
Вы можете получить скидку в рулетке!