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

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

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


algorithm graph-theory minimum-spanning-tree
person Bushra    schedule 16.03.2011    source источник
comment
Как может include одновременно быть не частью?   -  person Dante May Code    schedule 16.03.2011
comment
вот мой вопрос. Есть ли какая-то общая форма, скажем, у нас есть дерево с n вершинами. есть одно ребро e, когда включаем это ребро, у MST есть цикл, и он больше не будет MST. Теперь мне нужно создать MST, имеющий это ребро. e. Есть ли какая-нибудь общая форма, с помощью которой я могу узнать, сколько MST возможно?   -  person Bushra    schedule 16.03.2011
comment
@Princess, не могли бы вы поделиться ссылкой на то, что вы говорили?   -  person Dante May Code    schedule 16.03.2011
comment
У меня нет ссылки. Это утверждение дано мне в качестве викторины. Я не нашел его ответа. Сэр сказал, что если существует MST с n вершинами, то будет n-1 MST, включающих ребро e. но, насколько мне известно, это невозможно. Я видел в презентации в Интернете, что если у нас есть дерево с 4 вершинами, то MST может быть 8. Меня очень смущает это утверждение. Я тоже пытался найти ответ на этот вопрос в Интернете, но так и не получил ответа. После этого я нашел ссылку на этот сайт и разместил здесь свой вопрос.   -  person Bushra    schedule 16.03.2011
comment
Итак, вопрос в том, действительно ли если существует MST с n вершинами, тогда будет n-1 MST, включающих ребро e?   -  person Dante May Code    schedule 16.03.2011
comment
Точная постановка вопроса такова: пусть G - взвешенный граф с весом всех ребер, равным 1. Пусть T - MST графа G, не содержащая ребра e. Тогда сколько MST может иметь ребро?   -  person Bushra    schedule 16.03.2011
comment
Что меня смущает, так это Пусть T будет MST группы G, которая не включает ребро e, поскольку это предложение кажется ненужным.   -  person Dante May Code    schedule 16.03.2011
comment
T - минимальное остовное дерево, которое является частью графа G, а e - это ребро, которое не является частью MST, но является частью графа.   -  person Bushra    schedule 16.03.2011
comment
@Princess, без этого предложения вопрос остается в силе .... У меня есть для вас ответ.   -  person Dante May Code    schedule 16.03.2011
comment
Я понял. Большое вам спасибо за ваше руководство   -  person Bushra    schedule 16.03.2011
comment
@Princess, так что проверьте мой ответ XD   -  person Dante May Code    schedule 16.03.2011

Ответы (1)


arrow_upward
1
arrow_downward

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

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

В математической области теории графов используется теорема Кирхгофа или теорема Кирхгофа о дереве матриц, названная в честь Густава Кирхгофа. теорема о количестве остовных деревьев в графе.

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

‹1> можно вывести по теореме Кирхгофа, а

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

person Dante May Code    schedule 16.03.2011
comment
Спасибо за ссылку на теорему Кирхгофа! Я такого раньше не видел, но это потрясающий результат! - person templatetypedef; 13.06.2013