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)
Проверьте, являются ли следующие последовательности графическими, обоснуйте ответ
Решение в приложении к ответу
Всего существует 18 000 пятизначных чисел, сумма цифр которых делится на 5
Пошаговое объяснение:
* * * * * - пятизначное число.
Цифр всего десять: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
На первое место (на место десятков тысяч) можно поставить любую цифру из десяти (10 вариантов), на второе (на место тысяч) можно поставить любую цифру из десяти (10 вариантов), на третье место (на место сотен) можно поставить любую цифру из десяти (10 вариантов), на четвертое место (на место десятков), также, можно поставить любую цифру из десяти (10 вариантов).
Теперь главное - пятое место (место единиц). Чтобы сумма цифр числа делилась на пять, существует лишь два варианта.
Обоснование: Если сумма первых четырёх цифр уже делится на 5, то последнее число должно быть равно 5 или 0; если сумма первых четырёх цифр при делении на 5 даёт нам остаток 1, то последняя цифра должна быть 4 или 9; если сумма первых четырёх цифр при делении на 5 даёт нам остаток 2, то последняя цифра должна быть 3 или 8; при остатке три - это 2 или 7, при остатке 4 - это 1 или 6. Т.е. всегда лишь 2 варианта.
Перемножив все полученные варианты, получаем общее количество чисел 9*10*10*10*2=18 000
