Количество остовных деревьев в графе с n вершинами и n ребрами.

задан 15 Янв 3:50

изменен 15 Янв 3:57

10|600 символов нужно символов осталось
0

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

Если же граф связен, то одно остовное поддерево имеется. В нём n-1 ребро. Ещё одно ребро к нему добавляется. Пусть концы этого ребра соединены в остовном поддереве простым путём длины k. Тогда получается цикл длины k+1. Из него можно удалить любое ребро, получая остовное поддерево. Другие рёбра, не входящие в этот цикл, удалять нельзя -- дерева при этом не будет, а будет несвязный граф.

Поэтому ответом будет число k+1 -- длина простого цикла в данном графе. Такой цикл в условиях задания ровно один. Но значение k может принимать любые значения от 1 до n.

ссылка

отвечен 15 Янв 4:01

10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×665
×33

задан
15 Янв 3:50

показан
246 раз

обновлен
15 Янв 4:01

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

по почте:

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

по RSS:

Ответы

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

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