6 - сынып БЖБ І нұсқа1. Тіктөртбұрыштың қабырғалары 4, 3 <a< 8; 5, 2 < в<9.2.Тіктөртбұры - Дудина895

Математика

Ответить

Ответы

nofate1016585

15.03.2022

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 компонентами связности верно неравенство $|V|-k\leq |E|\leq \left(\begin{array}{c}|V|-k\\2\end{array}\right)$

Введем обозначения |V|=n, |E|=m

Разобьем граф на компоненты связности. Для каждой компоненты, очевидно, верно неравенство $m_i\geq n_i-1$ . Просуммировав неравенства для каждой из k компонент, получим $m\geq n-k$ .

Оценка снизу получена.

Лемма: Граф имеет максимальное число ребер, если он имеет k-1 тривиальную компоненту связности и 1 компоненту, являющуюся полным графом. И действительно. Пусть $K_{n_1}, K_{n_2}$ – компоненты связности, . Тогда при "переносе" одной вершины из $K_{n_1}$ в $K_{n_2}$ число ребер увеличится на n_2-(n_1-1)0 – а значит такая "конфигурация" неоптимальная, и несколькими преобразованиями сводится к указанной в лемме. А тогда максимальное число ребер в графе равно $\left(\begin{array}{c}|V|-k\\2\end{array}\right)$ Оценка сверху получена.

Zadanie 6 (Задание 6)

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

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

Плата Очень нужна математика дискретная Задание 4).Найдите количество деревьев с n вершинами, в кото

Ответить на вопрос

Поделитесь своими знаниями, ответьте на вопрос:

6 - сынып БЖБ І нұсқа1. Тіктөртбұрыштың қабырғалары 4, 3 <a< 8; 5, 2 < в<9.2.Тіктөртбұрыштың ауданын бағала.[2]2. Теңдеуді шешіңіз:8x - 15+ 7x = 2х+ 50[3]3. Теңсіздікті шешіңіз4(x-1)-(9x-5263. Теңсіздіктердің бүтін шешімін табыңыз:[3](2x-3<17, 14x+6 >8.[4]

Ответы

Ответить на вопрос

Ваше имя (никнейм)*

Email*

Комментарий*

Популярные вопросы в разделе

Решите б Остальное не надо..

Яне могу найти изложение по татарскому, на тему "родная школа" напишите , буду вам.

Реши уравнение:— 4у – 20 = 6y + 40.Умоляю, очень

Из 60 семян взошли 55 растений. найдите процент всхожести семян.

Стороны прямоугольника15см. и у см.запиши выражение для вычисления периметра прямоугольника.найди периметр, если у равен 10и1

9 + 2 ( 2 х + 1) = 1 Решите

Найдите десятичное приближение частного до указанного разряда: 1) 43, 3 : 9 - до десятых; 2) 78, 32 : 18 - до десятых; 3) 38 : 11 - до сотых; 4) 10 : 18 - до сотых;

Всадовом питомнике было 700 саженцев. 3 магазина купили по 70 саженцев, а 2 магазина по 90. сколько ещё саженцев осталось в питомнике?

Встоловую 150 кг картофеля. картофеля в 3 раза больше, чем моркови. сколько всего килограммов картофеля и моркови в столовую?

Уравнение кривой второго порядка 2у^2+3x-2у-2, 5=0 путем выделения полного квадрата к каноническому виду. построить кривую.