6ч 10 мин - 2 ч 45 мин + 8 ч 12 мин

Решение смотри в приложении

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)

Проверьте, являются ли следующие последовательности графическими, обоснуйте ответ​

Решение в приложении к ответу

Примеров множество. Один из них - дробь 1/2.

Пошаговое объяснение:

1/2 - первоначальная дробь.

1 + 30 = 31 - числитель новой дроби.

2 + 40 = 42 - знаменатель новой дроби.

Сама дробь примет вид 31/42.

1/2 = 21/42.

21/42 < 31/42.

Новая дробь 31/42 не равна первоначальной дроби 1/2.

Если в условии ошибка, если дробь при увеличении числителя и знаменателя даст равную ей дробь, то решение следующее:

Пусть а - числитель дроби, b - eё знаменатель. По условию задачи (а+30)/(b+40) - новая дробь.

Зная, что полученная и первоначальная дробь равные, составим и решим уравнение:

(а+30)/(b+40) = а/b

(а+30)•b = (b+40)•a

ab + 30b = ab + 40a

30b = 40a

a = 3/4•b, тогда первоначальная дробь

а/b = (3/4•b)/b = 3/4.

Проверим полученный результат:

3/4 - первоначальная дробь;

(3+30)/(4+40) = 33/44 = 3/4 - верно.

ответ : 3/4.