2011-gre-cs-practice-book.pdf/Q43 — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
 
(не показано 7 промежуточных версий 2 участников)
Строка 1: Строка 1:
{{reserve-task|[[Участник:Urmat A|Urmat A]] 10:28, 20 декабря 2024 (UTC)}}
 
 
== Вопрос: 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
  
  
Строка 21: Строка 20:
  
 
Допустим, у нас уже есть MST. У графа по условию минимум 3 ребра, значит минимум 3 вершины.
 
Допустим, у нас уже есть MST. У графа по условию минимум 3 ребра, значит минимум 3 вершины.
1)Рассмотрим случай с 3 вершинами:
 
*Пусть это цикл-треугольник. Очевидно, что два минимальных по весу ребра создадут MST.
 
*Если же это граф-путь, то очевидно, что все рёбра, включая m1 и m2, войдут в MST.
 
  
2)Пусть у графа n>3 ребер, m>3 вершин. Пусть для него построили MST, в который не вошли m1 и m2. Тогда добавим в него m1, получим цикл. Из цикла можно убрать самое тяжёлое по весу ребро, так чтобы не потерять связности. Точно также можно проделать и с m2. Всё-таки для цикла нужно минимум три ребра, поэтому совсем необязательно в MST войдет третье по весу минимальное ребро. Приведём пример:
+
1) Рассмотрим случай с 3 вершинами:
 +
* Пусть это цикл-треугольник. Очевидно, что два минимальных по весу ребра создадут MST.
 +
* Если же это граф-путь, то очевидно, что все рёбра, включая m1 и m2, войдут в MST.
 +
 
 +
2) Пусть у графа n>3 ребер, m>3 вершин. Пусть для него построили MST, в который не вошли m1 и m2.
 +
* Тогда добавим в него m1, получим цикл. Из цикла можно убрать самое тяжёлое по весу ребро, так чтобы не потерять связности.
 +
* Точно также можно проделать и с m2.
 +
* Всё-таки для цикла нужно минимум три ребра, поэтому совсем необязательно в MST войдет третье по весу минимальное ребро. Приведём пример:
 +
 
 
<graph>
 
<graph>
 
digraph G{
 
digraph G{
Строка 37: Строка 41:
 
</graph>
 
</graph>
  
В MST войдут рёбра с весами 1,2,4. Ребро с весом 3 не войдёт, хоть оно 3 минимальное по весу. Зато вошло самое тяжёлое/длинное ребро с весом 4, чтобы опровергает утверждение III.
+
В MST войдут рёбра с весами 1,2,4. Ребро с весом 3 не войдёт, хоть оно 3 минимальное по весу.
{{question-ok|}}
+
 
{{checkme|[[Участник:Urmat A|Urmat A]] 10:51, 20 декабря 2024 (UTC)}}
+
Зато вошло самое тяжёлое/длинное ребро с весом 4, что заодно опровергает утверждение III.
 +
{{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 войдет третье по весу минимальное ребро. Приведём пример:

[svg]

В MST войдут рёбра с весами 1,2,4. Ребро с весом 3 не войдёт, хоть оно 3 минимальное по весу.

Зато вошло самое тяжёлое/длинное ребро с весом 4, что заодно опровергает утверждение III.