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

Версия 10:54, 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. Решено: Urmat A 10:54, 20 декабря 2024 (UTC)