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)
Проверьте, являются ли следующие последовательности графическими, обоснуйте ответ
Решение в приложении к ответу
если квадратный трехчлен aх2+bx+c представлен в виде a(х+p)2+q, где p и q — действительные числа, то говорят, что из квадратного трехчлена выделен квадрат двучлена.
покажем на примере как это преобразование делается.
выделим из трехчлена 2x2+12x+14 квадрат двучлена.
вынесем за скобки коэффициент a, т.е. 2:
2
x
2
+
12
x
+
14
=
2
(
x
2
+
6
x
+
7
)
преобразуем выражение в скобках.
для этого представим 6х в виде произведения 2*3*х, а затем прибавим и вычтем 32. получим:
2
(
x
2
+
2
⋅
3
⋅
x
+
3
2
−
3
2
+
7
)
=
2
(
(
x
+
3
)
2
−
3
2
+
7
)
=
=
2
(
(
x
+
3
)
2
−
2
)
=
2
(
x
+
3
)
2
−
4
т.о. мы выделили квадрат двучлена из квадратного трехчлена, и показоли, что:
2
x
2
+
12
x
+
14
=
2
(
x
+
3
)
2
−
4
разложение на множители квадратного трехчлена
если квадратный трехчлен aх2+bx+c представлен в виде a(х+n)(x+m), где n и m — действительные числа, то говорят, что выполнена операция разложения на множители квадратного трехчлена.
покажем на примере как это преобразование делается.
разложим квадратный трехчлен 2x2+4x-6 на множители.
вынесем за скобки коэффициент a, т.е. 2:
2
x
2
+
4
x
−
6
=
2
(
x
2
+
2
x
−
3
)
преобразуем выражение в скобках.
для этого представим 2х в виде разности 3x-1x, а -3 в виде -1*3. получим:
=
2
(
x
2
+
3
⋅
x
−
1
⋅
x
−
1
⋅
3
)
=
2
(
x
(
x
+
3
)
−
1
⋅
(
x
+
3
)
)
=
=
2
(
x
−
1
)
(
x
+
3
)
т.о. мы разложили на множители квадратный трехчлен, и показоли, что:
2
x
2
+
4
x
−
6
=
2
(
x
−
1
)
(
x
+
3
)
заметим, что разложение на множители квадратного трехчлена возможно только тогда, когда, квадратное уравнение, соответсвующее этому трехчлену имеет корни.
т.е. в нашем случае разложить на множители трехчлен 2x2+4x-6 возможно, если квадратное уравнение 2x2+4x-6 =0 имеет корни. в процессе разложения на множители мы установили, что уравнение 2x2+4x-6 =0 имеет два корня 1 и -3, т.к. при этих значениях уравнение 2(x-1)(x+3)=0 обращается в верное равенство
