Рубрики

ВОРОТА | GATE CS 2012 | Вопрос 27

Пусть G — взвешенный граф с весами ребер больше единицы, а G'be — граф, построенный путем возведения в квадрат весов ребер в G. Пусть T и T '- минимальные остовные деревья G и G' соответственно с полными весами t и т'. Какие из следующих утверждений верно?
(A) T '= T с общим весом t' = t 2
(B) T '= T с общим весом t' <t 2
(C) T '! = T, но общий вес t' = t 2
(D) Ничего из вышеперечисленного

Ответ: (D)
Объяснение: Возведение в квадрат весов ребер в взвешенном графике не изменит минимальное остовное дерево . Предположим противное, чтобы получить противоречие. Если минимальное остовное дерево изменяется, то по крайней мере одно ребро из старого графа G в старом минимальном остовном дереве T должно быть заменено новым ребром в дереве T 'из графа G' с квадратами весов ребер. Новое ребро из G 'должно иметь меньший вес, чем ребро из G. Это означает, что существуют такие веса C1 и C2, что C1 <C2 и C12> = C22. Это противоречие.
Источник: http://www.cs.nyu.edu/courses/spring06/V22.0310-001/hw3.htm

Суммы квадратов из двух или более чисел всегда меньше квадрата суммы.
Пример: 2 ^ 2 + 2 ^ 2 <(4) ^ 2

Но

there is one counter example when the graph has only one edge.  
         In that case, the two values are same. 

Тест на этот вопрос

Рекомендуемые посты:

ВОРОТА | GATE CS 2012 | Вопрос 27

0.00 (0%) 0 votes