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. Решите уравнение: 21,3 – у = 9,7.
21,3 – у = 9,7
у = 21,3-9,7
у = 11,6
ответ: 11,6.
В2. Вычислите: 11 целых 2 девятых - ( 2 целых четыре девятых + 5 целых 8 девятых)
11 2\9 - (2 4\9 + 5 8\9) = 101\9 - (22\9 + 53\9) = 101\9 - 75\9 = 26\9
ответ: 26\9
В3. Сад прямоугольной формы имеет длину 40 м и ширину 30м. Сливы занимаю 5/12 сада. Какова площадь участка сада, засаженного сливами?
Сад имеет форму прямоугольника длина которого 40м, ширина 30м
Площадь прямоугольника S=a*b=30*40=1200 м²
Сливы занимают ⁵/₁₂ частей площади сада
Значит площадь нужно разделить на 12 частей и взять 5 таких части
1200:12*5=500 м²
ответ: Площадь занимаемая сливами 500 м².
С1. Миша шёл из одного села в другое 0,7 ч по полю и 0,9 ч через лес, пройдя всего 5,31 км. С какой скоростью шёл Миша через лес, если по полю он двигался со скоростью 4,5 км/ч?
1) 4,5*0,7=3,15(км по полю 2) 5,31-3,15=2,16(км через лес 3) 2,16:0,9=2,4(км/час) скорость Миши через лес
ответ: Миша шел по лесу со скоростью 2,4 км/ч.
С2* Найдите все натуральные значения а, при которых обе дроби a/5 и 9/a одновременно будут неправильными.
Неправильные дроби: 5/5 и 9/5; 6/5 и 9/6; 7/5 и 9/7; 8/5 и 9/8; 9/5 и 9/9.
ответ: а = 5, 6, 7, 8, 9
ответ будет равен самому себе. Тоесть это ответ с) (303003)