Трава молодіє на очах, набирає зеленої сили. Усе навкруги звеселяє веселий щебет птахів. Вони повернулись із теплих країв. Більшість дерев вкриваються дрібним білим цвітом. Тільки грушка вносить рожеві барви у біле покривало. Ароматними квітковими пахощами наповнюється весняне повітря. У цю пору дбайливі господарі замалюють білилом частину стовбурів, щоб захистити дерева від шкідників. З трави піднімають свої голівки ранні квіти.
Зеленими, білими, рожевими барвами та милою мелодією звеселяє нас весняний сад.
Найдите количество деревьев на n вершинах, в которых степень каждой вершины не больше 2.
n=1 => дерево состоит из одной вершины степени 0.
n>=2 => 1] Вершины степени 0 быть не может (иначе граф несвязный). Значит степень вершин либо 1, либо 2. 2] существует простая цепь, являющаяся подграфом дерева.
Тогда будем достраивать дерево из цепи. Ребро - простая цепь.
Алгоритм:
Изначально есть ребро <u,v>. Степени концов цепи - вершин u и v - равны 1.
Если на данном шаге число вершин в графе равно n - получен один из искомых графов, больше его не изменяем.
Если же число вершин < n, добавляем ребро.
На 1ом шаге мы можем добавить либо ребро <u,a>, либо ребро <a,v>. Без нарушения общности, добавим <u,a>. У нас все еще простая цепь. При этом у концов a и v степень 1, а у всех остальных вершин, здесь это вершина u, - 2, и к ним ребра присоединить уже нельзя. Повторяя подобные операции, будем получать на каждом шаге простую цепь.
На n вершинах можно построить ровно одну простую цепь. А значит и число искомых деревьев равно 1 .
Zadanie 5 (Задание 5)
Покажите, что для графа G=[V,E] с k компонентами связности верно неравенство
Введем обозначения
Разобьем граф на компоненты связности. Для каждой компоненты, очевидно, верно неравенство . Просуммировав неравенства для каждой из k компонент, получим .
Оценка снизу получена.
Лемма: Граф имеет максимальное число ребер, если он имеет k-1 тривиальную компоненту связности и 1 компоненту, являющуюся полным графом. И действительно. Пусть – компоненты связности, . Тогда при "переносе" одной вершины из в число ребер увеличится на – а значит такая "конфигурация" неоптимальная, и несколькими преобразованиями сводится к указанной в лемме. А тогда максимальное число ребер в графе равно Оценка сверху получена.
Zadanie 6 (Задание 6)
Проверьте, являются ли следующие последовательности графическими, обоснуйте ответ
Навесні пробуджується садок біля мого будинку.
Трава молодіє на очах, набирає зеленої сили. Усе навкруги звеселяє веселий щебет птахів. Вони повернулись із теплих країв. Більшість дерев вкриваються дрібним білим цвітом. Тільки грушка вносить рожеві барви у біле покривало. Ароматними квітковими пахощами наповнюється весняне повітря. У цю пору дбайливі господарі замалюють білилом частину стовбурів, щоб захистити дерева від шкідників. З трави піднімають свої голівки ранні квіти.
Зеленими, білими, рожевими барвами та милою мелодією звеселяє нас весняний сад.
Zadanie 4 (Задание 4)
Найдите количество деревьев на n вершинах, в которых степень каждой вершины не больше 2.
n=1 => дерево состоит из одной вершины степени 0.
n>=2 => 1] Вершины степени 0 быть не может (иначе граф несвязный). Значит степень вершин либо 1, либо 2. 2] существует простая цепь, являющаяся подграфом дерева.
Тогда будем достраивать дерево из цепи. Ребро - простая цепь.
Алгоритм:
Изначально есть ребро <u,v>. Степени концов цепи - вершин u и v - равны 1.
Если на данном шаге число вершин в графе равно n - получен один из искомых графов, больше его не изменяем.
Если же число вершин < n, добавляем ребро.
На 1ом шаге мы можем добавить либо ребро <u,a>, либо ребро <a,v>. Без нарушения общности, добавим <u,a>. У нас все еще простая цепь. При этом у концов a и v степень 1, а у всех остальных вершин, здесь это вершина u, - 2, и к ним ребра присоединить уже нельзя. Повторяя подобные операции, будем получать на каждом шаге простую цепь.
На n вершинах можно построить ровно одну простую цепь. А значит и число искомых деревьев равно 1 .
Zadanie 5 (Задание 5)
Покажите, что для графа G=[V,E] с k компонентами связности верно неравенство
Введем обозначения
Разобьем граф на компоненты связности. Для каждой компоненты, очевидно, верно неравенство
. Просуммировав неравенства для каждой из k компонент, получим 
.
Оценка снизу получена.
Лемма: Граф имеет максимальное число ребер, если он имеет k-1 тривиальную компоненту связности и 1 компоненту, являющуюся полным графом. И действительно. Пусть
– компоненты связности, 
. Тогда при "переносе" одной вершины из 
в 
число ребер увеличится на 
– а значит такая "конфигурация" неоптимальная, и несколькими преобразованиями сводится к указанной в лемме. А тогда максимальное число ребер в графе равно 
Оценка сверху получена.
Zadanie 6 (Задание 6)
Проверьте, являются ли следующие последовательности графическими, обоснуйте ответ
Решение в приложении к ответу