Crowdly
Додати до Chrome
Розглянемо граф G = (V, E) , кожне ребро e якого має вагу w e . Припустимо, ...
✅ Перевірена відповідь на це питання доступна нижче. Наші рішення, перевірені спільнотою, допомагають краще зрозуміти матеріал.
Розглянемо граф G = (V, E), кожне ребро e якого має вагу we. Припустимо, що всі ребра мають додатні та унікальні ваги. Нехай T - мінімальне кістякове дерево для G та P - найкоротший шлях в G від деякої вершини s до деякої вершини t. Тепер припустимо, що вага кожного ребра e в G зросла на 1 і стала рівною we + 1. Назвемо цей граф G'. Яке з тверджень є справедливим відносно G'?
✅
❌
❌
❌