Предположим, вы получили взвешенный неориентированный граф G и вас попросили найти максимальное остовное дерево (остовное дерево, у которого сумма всех весов ребер максимальна). Тем не менее, вам говорят, что вы не можете изменить алгоритм Прима для минимального остовного дерева, но вам разрешено изменять сам граф, превращая G в G '. Предложите подход для создания G 'из G, который позволил бы вам запустить алгоритм Прима на G' и найти решение для Максимального остовного дерева в G (исходный граф). Вам нужно только описать изменения, которые вам нужно применить к графику.