- если мы встретим путь в G, который имеет больше ребер (по сравнению с некоторым другим путем), но наименьший вес при суммировании весов ребер (по сравнению со всеми возможными путями), мы выиграли не рассматриваете это как MST?
Я предполагаю, что под "путем" вы имели в виду писать "дерево"? (« путь » - это совершенно другое понятие: у него всего две конечные точки без разветвленной структуры.)
A дерево связный граф без циклов, поэтому каждое дерево с n вершинами имеет ровно n −1 ребер. Таким образом, если граф имеет n вершин, то каждое остовное дерево этого графа должно иметь ровно n -1 ребер. Так что если у вас есть подграф с больше , чем n -1 ребер, то это не дерево, так что это не остовное дерево, так что, как вы и предполагали, это не минимальное остовное дерево.
Но учтите, что если подграф соединяет все вершины, этот подграф обязательно будет содержать хотя бы одно остовное дерево; и если нет ребер с отрицательным весом, то эти остовные деревья будут иметь вес, меньший или равный весу подграфа. Поэтому, хотя ваш пример не является минимальным остовным деревом, он вполне может содержать минимальное остовное дерево.
Входит ли в игру понятие MST, только если у нас есть несколько связующих деревьев для G? иначе Spanning tree = MST?
Если в графе есть только одно остовное дерево, то это остовное дерево является минимальным остовным деревом, да. Но обратите внимание, что это происходит только в том случае, если сам граф является деревом (в этом случае это его собственное минимальное остовное дерево); в противном случае у него наверняка будет несколько связующих деревьев.
Конечно, даже если у него несколько связующих деревьев, возможно, что все они имеют одинаковый вес в любом случае , и в этом случае они все будут быть минимальным охватом деревьев.