У меня есть проблема из моего учебника, которая выглядит следующим образом;Предположим, что у меня есть матрица кратчайшего пути S, которая может выглядеть следующим образом:
И дерево T, состоящее из кратчайшегопути, построенные из матрицы кратчайших путей S (как минимальное остовное дерево).
Дерево обладает следующими свойствами;n - 1 ребра, все узлы связаны друг с другом.
Задача состоит в том, чтобы доказать противоречие, что если запись S_{ij} имеет минимальное значение, то эта запись должна быть ребром в деревеT.Я не совсем понимаю, что есть доказательства.Я вижу это так: если мы предположим, что T не содержит наименьший элемент из S, то в конце мы получим противоречие, поскольку будет путь, который больше, чем выбранный с помощьюсамый маленький элемент.Это не кажется мне большим доказательством, и даже если это так, я не понимаю, как можно обобщить это доказательство.