2011-gre-cs-practice-book.pdf/Q43 — различия между версиями
Материал из DISCOPAL
Urmat A (обсуждение | вклад) |
StasFomin (обсуждение | вклад) |
||
| (не показаны 3 промежуточные версии этого же участника) | |||
| Строка 1: | Строка 1: | ||
| − | |||
== Вопрос: Q43-08c765 == | == Вопрос: Q43-08c765 == | ||
Какое из следующих свойств должно быть верным для минимального остовного дерева (MST) связного графа G с не менее чем 3 ребрами? | Какое из следующих свойств должно быть верным для минимального остовного дерева (MST) связного графа G с не менее чем 3 ребрами? | ||
| − | *I. MST должно содержать самое минимальное ребро G. | + | * I. MST должно содержать самое минимальное ребро G. |
| − | *II. MST должно содержать второе минимальное ребро G. | + | * II. MST должно содержать второе минимальное ребро G. |
| − | *III. MST никогда не может содержать самое длинное ребро G | + | * III. MST никогда не может содержать самое длинное ребро G |
=== Ответы === | === Ответы === | ||
| − | *Ни одно | + | * Ни одно |
| − | *Только I | + | * Только I |
| − | *Правильный ответ: Только I и II | + | * Правильный ответ: Только I и II |
| − | *Только I и III | + | * Только I и III |
| − | *I,II и III | + | * I,II и III |
| Строка 22: | Строка 21: | ||
Допустим, у нас уже есть MST. У графа по условию минимум 3 ребра, значит минимум 3 вершины. | Допустим, у нас уже есть MST. У графа по условию минимум 3 ребра, значит минимум 3 вершины. | ||
| − | 1)Рассмотрим случай с 3 вершинами: | + | 1) Рассмотрим случай с 3 вершинами: |
| − | *Пусть это цикл-треугольник. Очевидно, что два минимальных по весу ребра создадут MST. | + | * Пусть это цикл-треугольник. Очевидно, что два минимальных по весу ребра создадут MST. |
| − | *Если же это граф-путь, то очевидно, что все рёбра, включая m1 и m2, войдут в MST. | + | * Если же это граф-путь, то очевидно, что все рёбра, включая m1 и m2, войдут в MST. |
| + | |||
| + | 2) Пусть у графа n>3 ребер, m>3 вершин. Пусть для него построили MST, в который не вошли m1 и m2. | ||
| + | * Тогда добавим в него m1, получим цикл. Из цикла можно убрать самое тяжёлое по весу ребро, так чтобы не потерять связности. | ||
| + | * Точно также можно проделать и с m2. | ||
| + | * Всё-таки для цикла нужно минимум три ребра, поэтому совсем необязательно в MST войдет третье по весу минимальное ребро. Приведём пример: | ||
| − | |||
| − | |||
| − | |||
| − | |||
<graph> | <graph> | ||
digraph G{ | digraph G{ | ||
| Строка 40: | Строка 40: | ||
} | } | ||
</graph> | </graph> | ||
| − | В MST войдут рёбра с весами 1,2,4. Ребро с весом 3 не войдёт, хоть оно 3 минимальное по весу. | + | |
| + | В MST войдут рёбра с весами 1,2,4. Ребро с весом 3 не войдёт, хоть оно 3 минимальное по весу. | ||
Зато вошло самое тяжёлое/длинное ребро с весом 4, что заодно опровергает утверждение III. | Зато вошло самое тяжёлое/длинное ребро с весом 4, что заодно опровергает утверждение III. | ||
| − | {{question-ok | + | {{question-ok|[[Участник:StasFomin|StasFomin]]}} |
| − | + | ||
| + | [[Категория:Алгоритмы на графах]] | ||
Текущая версия на 11:26, 20 декабря 2024
Вопрос: 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 вершины.
1) Рассмотрим случай с 3 вершинами:
- Пусть это цикл-треугольник. Очевидно, что два минимальных по весу ребра создадут MST.
- Если же это граф-путь, то очевидно, что все рёбра, включая m1 и m2, войдут в MST.
2) Пусть у графа n>3 ребер, m>3 вершин. Пусть для него построили MST, в который не вошли m1 и m2.
- Тогда добавим в него m1, получим цикл. Из цикла можно убрать самое тяжёлое по весу ребро, так чтобы не потерять связности.
- Точно также можно проделать и с m2.
- Всё-таки для цикла нужно минимум три ребра, поэтому совсем необязательно в MST войдет третье по весу минимальное ребро. Приведём пример:
В MST войдут рёбра с весами 1,2,4. Ребро с весом 3 не войдёт, хоть оно 3 минимальное по весу.
Зато вошло самое тяжёлое/длинное ребро с весом 4, что заодно опровергает утверждение III.