Если веса всех ребер в графе различны, сколько может быть у такого графа остовных деревьев?

задан 8 Фев 22:07

Непонятно, как число остовных деревьев может быть связано с весами рёбер.

(8 Фев 22:36) falcao

Минимальных остовных деревьев*

(8 Фев 22:37) Иван123421

Каково определение?

Вообще, задача плохо поставлена -- не сказано, какой рассматривается граф. Он ведь может быть и не связен, и тогда остовных деревьев вообще нет.

(8 Фев 22:37) falcao

Минимальное остовное дерево - имеющее минимальный вес ребер входящих в него

(8 Фев 22:41) Иван123421

Ну я так понимаю что тут просят вообще узнать сколько всего может их быть, понятно что их может быть всего 1 или 0(если граф не связен), вопрос в том, может ли их быть больше 2?

(8 Фев 22:44) Иван123421

Хотя по определению минимальное остовное дерево ищется только в связном графе

(8 Фев 22:46) Иван123421

Если граф связен, а веса всех рёбер попарно различны, то единственность оптимального остовного дерева вытекает из обоснования алгоритма Краскала.

(9 Фев 0:05) falcao
показано 5 из 7 показать еще 2
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,475
×548

задан
8 Фев 22:07

показан
158 раз

обновлен
9 Фев 0:05

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru