Четкое минимальное остовное дерево

Question

Для связного взвешенного неориентированного графа G: G имеет уникальный MST, если для каждого среза G существует уникальный край минимального веса, пересекающий срез.

Является ли это утверждение верным?

Я считаю ложным, потому что для следующего графика в данной ссылке может быть несколько MST.

https://drive.google.com/file/d/1yDK3juPxeDBdS-aEOx0aAsphy4odZ55l/view?usp=drivesdk

Answer 1

Если вы имеете в виду связанный граф G, с граничными затратами, которые все различны.Тогда G имеет уникальное минимальное остовное дерево.

доказательство: предположим, что есть два разных MST, назовите их T1 и T2, у которых есть разные наборы ребер - {t11, t12,… t1n-1} для T1и {t21, t22,… t2n-1} для T2.Итак, пусть ti будет ребром с наименьшим весом только в T1 (не в T2).Поскольку он наименьший, его необходимо включить в «каждый выбор» MST.Таким образом, оба MST T1 и T2 имели бы это.Но это противоречит определению ti.