Быстрый вопрос о минимальных остовных деревьях - PullRequest
3 голосов
/ 28 ноября 2010

Если какое-либо ребро из остовного дерева T0 содержится в некотором минимальном остовном дереве T *, означает ли это, что T0 также является минимальным остовным деревом?

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

Заранее спасибо.

1 Ответ

1 голос
/ 28 ноября 2010

Треугольник с весом ребер 2,2,1.

РЕДАКТИРОВАТЬ:

Есть три разных остовных дерева с затратами 3 (1 + 2), 3 (2 + 1) и4 (2 + 2) на этом графике.все ребра из остовного дерева со стоимостью 4 содержатся в одном из минимальных остовных деревьев со стоимостью 3, и оно НЕ минимально.

...