Математика: 15 2) х2 5 робів : сделайте умножение дробов

15
2)
х2 5
робів : сделайте умножение дробов

👇

Увидеть ответ

Ответ:

polina4673738

09.01.2020

напиши нормальне, а то непонятно

4,7(13 оценок)

Открыть все ответы

Ответ:

ekozhushkova

09.01.2020

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 вершинами, в кото

4,5(17 оценок)

Ответ:

masha1373

09.01.2020

Всего возможны две ситуации: из конверта в конверт будет переложена простая задача или задача повышенной сложности.

Рассмотрим случай, когда будет переложена простая задача.

Найдем вероятность того, что из первого конверта во второй будет переложена простая задача. Для этого разделим число простых задач на общее количество задач в первом конверте:

$P(A)=\dfrac{6}{6+6}= \dfrac{6}{12}= \dfrac{1}{2}$

После такого перекладывания во втором конверте окажется 5 простых задач и 8 задач повышенной сложности. Достать из такого конверта простую задачу можно с вероятностью:

$P(B)=\dfrac{5}{5+8}= \dfrac{5}{13}$

Но такой конверт получается только с вероятностью $P(A)=\dfrac{1}{2}$ . Значит итоговая вероятность достать простую задачу при условии, что переложена была простая задача равна:

$P_A(B)=P(A)\cdot P(B)=\dfrac{1}{2}\cdot\dfrac{5}{13}=\dfrac{5}{26}$

Рассмотрим случай, когда будет переложена задача повышенной сложности.

Найдем вероятность того, что из первого конверта во второй будет переложена задача повышенной сложности:

$P(C)=\dfrac{6}{6+6}= \dfrac{6}{12}= \dfrac{1}{2}$

После такого перекладывания во втором конверте окажется 4 простые задачи и 9 задач повышенной сложности. Достать из такого конверта простую задачу можно с вероятностью:

$P(D)=\dfrac{4}{4+9}= \dfrac{4}{13}$

Но такой конверт получается только с вероятностью $P(C)=\dfrac{1}{2}$ . Значит итоговая вероятность достать простую задачу при условии, что переложена была простая задача равна: