Минимальное количество связующего дерева с учетом ребра, которое должно быть включено

Question

Меня смущает общая форма минимального остовного дерева, которая включает ребро e , которое не является частью минимального остовного дерева.Мой вопрос:

Пусть G будет взвешенным графом с весом всех ребер, равным 1. MST G не включает ребро e.Сколько MST может быть сделано с ограничением, что они включают ребро e ?

Answer 1

Когда график не взвешен, любое остовное дерево является Минимальным остовным деревом .

Идентичным весом 1 можно считатьтакой же, как невзвешенный .

В математической области теории графов Теорема Кирхгофа или теорема Кирхгофа о матричном дереве имени Густава Кирхгофа - это теорема о числесвязующие деревья на графике.

Число (MST включая e) = Число (все MST) <1> - Число (MST без e) <2>

<1> можетможно получить по теореме Кирхгофа, а

<2> можно получить по теореме Кирхгофа после удаления e из графа.