В университете мне была предложена следующая проблема:
Пусть G = (V, E) - (неориентированный) граф с затратами c e >= 0 на ребрах e & isin; E. Предположим, вам присвоено дерево G с минимальными затратами T в G. Теперь предположим, что к G добавлен новый край, соединяющий два узла v, t v & isin; V со стоимостью c.
- Дайте эффективный алгоритм для тестирования, если T остается деревом с минимальными затратами с новым краем, добавленным в G (но не с деревом T). Сделайте свой алгоритм во времени O (| E |). Можете ли вы сделать это в O (| V |) раз? Обратите внимание на любые предположения о том, какая структура данных используется для представления дерева T и графа G.
- Предположим, что T больше не является связующим деревом минимальной стоимости. Дайте алгоритм с линейным временем (время O (| E |)), чтобы обновить дерево T до нового дерева привязки минимальной стоимости.
Это решение, которое я нашел:
Let e1=(a,b) the new edge added
Find in T the shortest path from a to b (BFS)
if e1 is the most expensive edge in the cycle then T remains the MST
else T is not the MST
Кажется, что это работает, но я могу легко выполнить этот пробег в O (| V |), тогда как проблема задает время O (| E |). Я что-то пропустил?
Кстати, мы уполномочены просить о помощи у кого-нибудь, поэтому я не обманываю: D