2019-gate-computer-science-and-it-practice.pdf/Q18-alg5 — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Новая страница: « == Вопрос: Q18-alg5-31d68c == <blockquote> Вопрос из «Algorithms Test 5» где-то со страницы 243. Тут вставьте пер…») |
StasFomin (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
| − | |||
== Вопрос: Q18-alg5-31d68c == | == Вопрос: Q18-alg5-31d68c == | ||
| − | + | Предположим, что ''G'' — это связный неориентированный граф, ребра которого имеют положительные веса. | |
| − | + | Пусть ''M'' — минимальное остовное дерево этого графа. | |
| − | + | Мы модифицируем граф, добавляя «6» к весу каждого ребра, какое из следующих утверждений верно? | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
=== Ответы === | === Ответы === | ||
| − | + | * Порядок ребер, добавляемых к минимальному остовному дереву с использованием алгоритма Крускала, изменится. | |
| − | + | * Правильный ответ: Модификация добавляет <m>6(|V|-1)</m> к общему весу всех остовных деревьев. | |
| − | + | * Порядок ребер, добавляемых к минимальному остовному дереву с использованием алгоритма Прима, изменится. | |
| − | * | + | * Ничего из вышеперечисленного. |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
=== Объяснение === | === Объяснение === | ||
| − | + | Порядок добавления ребер при построении минимального остова не изменится. При добавлении 6 к весу каждого ребра, веса всех ребер в остовных деревьях увеличатся на 6. Поэтому общий вес всех остовных деревьев увеличится на <m>6(|V|-1)</m>, так как каждое остовное дерево имеет <m>|V|-1</m> ребер. | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | </ | + | |
| − | {{ | + | {{cstest-source|2019-gate-computer-science-and-it-practice.pdf|244|18}} |
| − | {{ | + | {{question-ok|[[Участник:StasFomin|StasFomin]] 16:21, 25 декабря 2024 (UTC)}} |
| − | [[ | + | [[Категория:Алгоритмы на графах]] |
Текущая версия на 16:21, 25 декабря 2024
Вопрос: Q18-alg5-31d68c
Предположим, что G — это связный неориентированный граф, ребра которого имеют положительные веса. Пусть M — минимальное остовное дерево этого графа. Мы модифицируем граф, добавляя «6» к весу каждого ребра, какое из следующих утверждений верно?
Ответы
- Порядок ребер, добавляемых к минимальному остовному дереву с использованием алгоритма Крускала, изменится.
- Правильный ответ: Модификация добавляет к общему весу всех остовных деревьев.
- Порядок ребер, добавляемых к минимальному остовному дереву с использованием алгоритма Прима, изменится.
- Ничего из вышеперечисленного.
Объяснение
Порядок добавления ребер при построении минимального остова не изменится. При добавлении 6 к весу каждого ребра, веса всех ребер в остовных деревьях увеличатся на 6. Поэтому общий вес всех остовных деревьев увеличится на , так как каждое остовное дерево имеет ребер.
Исходники — вопрос 18 на 244 странице книги «2019-gate-computer-science-and-it-practice.pdf»