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

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

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

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

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

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

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

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

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

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

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

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

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

→ Ответить
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Хм, наверно действительно лучше к преподу. Спасибо

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

    Ну вообще, обычно, когда говорят k-связный граф, имеют в виду вершинную связность. Но, конечно, уточнить не помешает.

    → Ответить