Главная /
Основы дискретной математики /
Построить для заданного нагруженного неориентированного графа G=(V,E) минимальный остов. V= {a, b, c, d, e, f, g, h, k },E= {(a,b; 10), (a,c; 9),(a,f; 20), (a,k; 7), (b, d; 17), (b,f; 27), (b,g; 10), (c, d; 17), ( c,g; 3), (c, h; 9), (d, e; 5), (d,f; 20),
Построить для заданного нагруженного неориентированного графа G=(V,E) минимальный остов.
V= {a, b, c, d, e, f, g, h, k }
,E= {(a,b; 10), (a,c; 9),(a,f; 20), (a,k; 7), (b, d; 17), (b,f; 27), (b,g; 10), (c, d; 17), ( c,g; 3), (c, h; 9), (d, e; 5), (d,f; 20), (h,g; 10), (h,k; 12) }
.
(здесь каждая скобка (u,v; D)
задает ребро (u,v)
из E
и его "вес" c(u,v)=D
).
Каков вес этого остова?
вопрос
V= {a, b, c, d, e, f, g, h, k }
,E= {(a,b; 10), (a,c; 9),(a,f; 20), (a,k; 7), (b, d; 17), (b,f; 27), (b,g; 10), (c, d; 17), ( c,g; 3), (c, h; 9), (d, e; 5), (d,f; 20), (h,g; 10), (h,k; 12) }
.Правильный ответ:
80
77
82
85
78
Сложность вопроса
93
Сложность курса: Основы дискретной математики
82
Оценить вопрос
Комментарии:
Аноним
Если бы не опубликованные подсказки - я бы сломался c этими тестами интуит.
14 фев 2020
Аноним
Если бы не опубликованные подсказки - я бы не справился c этими тестами intuit.
05 мар 2019
Другие ответы на вопросы из темы алгоритмы и дискретные структуры интуит.
- # При игре в преферанс колоду из 32 карт раздают трем игрокам – каждому по 10 карт, а оставшиеся 2 карты оставляют в прикупе. Каким числом способов можно произвести такую раздачу? (В вариантах ответов A(n,k) – число размещений из n по k, P(n) – число перестановок из n элементов ,C(n,k) – число сочетаний из n по k).
- # Какие из следующих монотонных элементарных конъюнкций входят в многочлен Жегалкина для функции f(X,Y,Z), заданной следующей последовательностью 8 нулей и единиц: f= (0001 0111). I) X*Y, II) X, III) Y, IV) X*Z, V) X*Y*Z, VI) Y*Z
- # Какие из следующих формул задают несамодвойственные функции: A= (Y ∧¬ Z) ∨ (X ∧ ¬Z) ∨( X ∧ Y), B =(¬ X∧ (Y|Z)) ∨(¬ Y ∧¬ Z) , C= Z ∨(Y ∧¬ X)
- # Для следующей формулы определить, какие из занумерованных вхождений переменных свободны (F), а какие являются связанными (C). \begin{array}{llllllllll} (\forall x(P(x,y) & \rightarrow & \exists y(\forall z(Q(x,y,z) &\rightarrow & P(x,z)) &\rightarrow & P(z,y))) & \rightarrow & Q(x,y,z)) \\ \phantom{ (\forall x(P(}1\phantom{,}2 & & \phantom{\exists y(\forall z(Q(}3\phantom{,y,}4 & & \phantom{P(x,}5 & & \phantom{P(}6\phantom{,} 7& & \phantom{Q(}8\phantom{,}9\end{array}
- # Чему равно число связных компонент неориентированного графа G=(V,E), где V={1, 2, 3, 4, 5, 6, 7, 8, 9}, E={(1,4), (2,7), (3,9), (5,4), (1,5), (6,7)}?