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)
Проверьте, являются ли следующие последовательности графическими, обоснуйте ответ
Решение в приложении к ответу
Пошаговое объяснение:
ответ: b4.
По условиям задачи, ни боцман, ни кок до разговора не знали, где закопан клад. Значит столбцами 5 и 6 можно пренебречь, так как в них есть однозначный ответ у кока, что противоречит условиям задачи. После разговора и коку и боцману стало известно, где клад. Значит надо искать такую пару значений, в которой одно из них после разговора утрачивает актуальность. Из пар a2 a3, b4 b5, c1 c3 такой является только вторая, поскольку 5 и 6 столбец не принимаются во внимание по причине, изложенной выше. Строкой d можно пренебречь, так как после разговора боцмана и кока в ней остаётся все так же 3 переменных.
В северной части области на поверхность выходят изверженные и метаморфические породы протерозоя: граниты, габбро, гнейсы и гранито-гнейсы. В южном направлении они погружаются под песчаники, пески, глины, и конгломераты рифея и венда, которые в свою очередь перекрываются отложениями палеозоя. В составе палеозоя выделяются отложения кембрия, ордовика, девона, и карбона. Синие кембрийские глины образу-ют пласт мощностью более 130 м, к которому приурочены месторождения кембрийских глин, используемые для изготовления изделий из грубой керамики.Выше залегают карбонатные и терригенные породы ордовика, с которыми связаны место-рождения фосфоритов, горючих сланцев, карбонатных пород. Большую часть территории области занимают девонские пески, песчаники с прослоями глин, с которыми связаны месторождения стекольных песков и глин.В Ленинградской области создан огромный сырьевой потенциал торфа и сапропеля, который позволяет обеспечить производство разнообразной торфяной продукции в необходимых объёмах.
Существуют компании занимающиеся полезными ископаемыми
ОАО «Гранит-Кузнечное»ООО «Цементно-бетонные изделия»ЗАО «Каменногорское карьероуправление»ЗАО «Каменногорский комбинат нерудных материалов»ЗАО «Выборгское карьероуправление»ЗАО «Семиозерское карьероуправление»