Пусть есть связный неориентированный граф G = (V, E), на рёбрах определена весовая функция w. Пусть существуют два дерева T и T′. Возьмём их списки рёбер L и L′. Отсортируем их (дальше при упоминании списков L и L' понимается, что они отсортированные). Пусть первая позиция их весового различия k, где выполняется L[k] > L′[k].
Требуется доказать или опровергнуть следующее утверждение: существует ребро e из первых k рёбер списка L' такое, что при добавлении e в лес F, образованный первыми k - 1 рёбрами списка L, в F не возникнет цикла и количество деревьев уменьшится.
Мне кажется, что вопрос какой-то странный. Если k — первое отличие, то какой вообще смысл рассматривать рёбра от 1-го по (k-1)-е? Их нельзя добавить, ибо они и так есть в "F, образованном первыми k-1 рёбрами списка L". Остаётся только само L'[k], и оно конечно же не создаст цикла, ведь получится L'[1], L'[2], ..., L'[k-1], L'[k], что является частью дерева T'.
Если я не так понял — переформулируйте, пожалуйста, свой вопрос.
Отличие по весу. Не по самим рёбрам. Сейчас уточню в топике.
UPD. Уточнил в топике.
В каждой компоненте связности размера t леса F может быть не более t-1 ребра из списка L'[1..k]. А т. к. в лесу F только k-1 ребро, то так минимум одно из ребер списка L'[1..k] будет соединять разные компоненты.
Да точно. Спасибо.