Блог пользователя nicky_ua

Задача остовных деревьев в k-связном графе
Автор nicky_ua, 12 лет назад, По-русски

тема курсовой работы "Задача остовных деревьев в k-связном графе" облазил интернет и не нашел формулировки этой задачи. вообще ничего похожего нет. можете сформулировать эту задачу?

  • Проголосовать: нравится
  • +4
  • Проголосовать: не нравится

»
12 лет назад, скрыть # |
 
Проголосовать: нравится -8 Проголосовать: не нравится

http://acmp.ru/index.asp?main=task&id_task=142 Вот

→ Ответить
  • »
    »
    12 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

    Я тоже вначале подумал про это. Но причем тут k-связное дерево? И почему задача остовнЫХ деревьев (ну, множественное число)? Еще у меня есть вариант, что это надо посчитать количество остовных деревьев в графе, но тут тоже к-саязность не причем (

    → Ответить
»
12 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +5 Проголосовать: не нравится

С такими вопросами нужно обращаться не сюда, а к преподавателю, давшему Вам такую тему для курсовой работы.

Во-первых, неясно, про какую именно k-связность идет речь: вершинную или реберную.

Во-вторых, что нужно делать с k-связными графами? Искать в них остовное дерево (которое по определению k-связного графа существует)? Или найти количество таких деревьев? Если речь идет о количестве, то оно тривиально находится по матричной теореме Кирхгофа. Или Вам нужно найти какие-либо нижние/верхние оценки для этого количества?

Повторюсь еще раз: идите и подробно расспросите своего препода.

→ Ответить