Предположим, что e - это ребро взвешенного графа, инцидентное вершине v, такое что вес e не превышает веса любого другого ребра, инцидентного v. Покажите, что существует минимальное остовное дерево, содержащее это ребро.
Докажите, что существует минимальное остовное дерево из вершины, всегда содержащее кратчайшее ребро из этой вершины.
comment
Когда спрашиваете о домашнем задании (1) Помните о вашей школьной политике: просьба здесь о помощи может быть обманом. (2) Укажите, что это домашнее задание. (3) Сначала постарайтесь решить проблему самостоятельно (включите свой код в свой вопрос). (4) Спросите о конкретной проблеме с вашей существующей реализацией; Минимальный, полный, проверяемый пример
- person Frieder schedule 01.12.2019
Ответы (1)
Доказательство противным
Предположим, что существует вершина v такая, что MST не использует ребро с наименьшим весом, e, а вместо этого использует другое инцидентное ребро, назовем это x. Теперь предположим, что мы добавляем ребро e обратно в MST, чтобы образовался цикл. Теперь мы можем удалить предыдущее использованное ребро x в этом цикле. На данный момент у нас есть еще один MST с более низкой общей стоимостью, чем ранее найденное связующее дерево. Это противоречие, потому что остовное дерево с ребром x на самом деле не было MST, если оно имело более высокую стоимость, чем остовное дерево с ребром e.
person
anaidu
schedule
18.04.2020
