2011-gre-cs-practice-book.pdf/Q43 — различия между версиями
Материал из DISCOPAL
Urmat A (обсуждение | вклад) |
Urmat A (обсуждение | вклад) |
||
| Строка 2: | Строка 2: | ||
== Вопрос: Q43-08c765 == | == Вопрос: Q43-08c765 == | ||
| − | + | Какое из следующих свойств должно быть верным для минимального остовного дерева (MST) связного графа G с не менее чем 3 ребрами? | |
| − | + | *I. MST должно содержать самое минимальное ребро G. | |
| − | + | *II. MST должно содержать второе минимальное ребро G. | |
| − | + | *III. MST никогда не может содержать самое длинное ребро G | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
=== Ответы === | === Ответы === | ||
| − | + | *Ни одно | |
| − | + | *Только I | |
| + | *Правильный ответ: Только I и II | ||
| + | *Только I и III | ||
| + | *I,II и III | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | + | === Объяснение === | |
| − | + | {{cstest-source|2011-gre-cs-practice-book.pdf|36|43}} | |
| − | + | ||
| + | * Обозначим первое и второе минимальные по весу(не обязательно разных) ребра m1 и m2. | ||
| − | + | Допустим, у нас уже есть MST. У графа по условию минимум 3 ребра, значит минимум 3 вершины. | |
| − | + | Рассмотрим случай с 3 вершинами: | |
| − | + | *Пусть это цикл-треугольник. Очевидно, что два минимальных по весу ребра создадут MST. | |
| − | + | *Если же это граф-путь, то очевидно, что все рёбра, включая m1 и m2, войдут в MST. | |
| − | Если все | + | |
| − | + | Пусть у графа n>3 ребер, m>3 вершин. Пусть для него построили MST, в который не вошли m1 и m2. Тогда добавим в него m1, получим цикл. Из цикла можно убрать самое тяжёлое по весу ребро, так чтобы не потерять связности. Точно также можно проделать и с m2. Всё-таки для цикла нужно минимум три ребра, поэтому совсем необязательно в MST войдет третье по весу минимальное ребро. Приведём пример: | |
| − | + | <graph> | |
| − | + | digraph G{ | |
| + | rankdir=LR; | ||
| + | edge [color=blue]; | ||
| + | 1 -> 2 [label="1"] | ||
| + | 1 -> 3 [label="2"] | ||
| + | 2 -> 3 [label="3"] | ||
| + | 3 -> 4 [label="4"] | ||
| + | } | ||
| + | </graph> | ||
| − | |||
{{question-ok|}} | {{question-ok|}} | ||
Версия 10:46, 20 декабря 2024
Задача зарезервирована: Urmat A 10:28, 20 декабря 2024 (UTC)
Вопрос: Q43-08c765
Какое из следующих свойств должно быть верным для минимального остовного дерева (MST) связного графа G с не менее чем 3 ребрами?
- I. MST должно содержать самое минимальное ребро G.
- II. MST должно содержать второе минимальное ребро G.
- III. MST никогда не может содержать самое длинное ребро G
Ответы
- Ни одно
- Только I
- Правильный ответ: Только I и II
- Только I и III
- I,II и III
Объяснение
Исходники — вопрос 43 на 36 странице книги «2011-gre-cs-practice-book.pdf»
- Обозначим первое и второе минимальные по весу(не обязательно разных) ребра m1 и m2.
Допустим, у нас уже есть MST. У графа по условию минимум 3 ребра, значит минимум 3 вершины. Рассмотрим случай с 3 вершинами:
- Пусть это цикл-треугольник. Очевидно, что два минимальных по весу ребра создадут MST.
- Если же это граф-путь, то очевидно, что все рёбра, включая m1 и m2, войдут в MST.
Пусть у графа n>3 ребер, m>3 вершин. Пусть для него построили MST, в который не вошли m1 и m2. Тогда добавим в него m1, получим цикл. Из цикла можно убрать самое тяжёлое по весу ребро, так чтобы не потерять связности. Точно также можно проделать и с m2. Всё-таки для цикла нужно минимум три ребра, поэтому совсем необязательно в MST войдет третье по весу минимальное ребро. Приведём пример: