Optprob/Задача Штейнера о минимальном дереве — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
 
(не показана одна промежуточная версия этого же участника)
Строка 1: Строка 1:
 
<!-- p30 -->
 
<!-- p30 -->
 
{{checked|}}
 
{{checked|}}
−
{{reserve-task|[[Участник:Sfirstov|Sfirstov]] 18:05, 12 декабря 2023 (UTC)}}
 
  
 
[https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%A8%D1%82%D0%B5%D0%B9%D0%BD%D0%B5%D1%80%D0%B0_%D0%BE_%D0%BC%D0%B8%D0%BD%D0%B8%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D0%BE%D0%BC_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%B5 Задача Штейнера о минимальном дереве].
 
[https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%A8%D1%82%D0%B5%D0%B9%D0%BD%D0%B5%D1%80%D0%B0_%D0%BE_%D0%BC%D0%B8%D0%BD%D0%B8%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D0%BE%D0%BC_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%B5 Задача Штейнера о минимальном дереве].
Строка 1402: Строка 1401:
 
{{enddiv}}
 
{{enddiv}}
  
−
[[Категория:OptimizationProblems]]
+
{{Cat4Term2|{{FULLPAGENAME}}|OptimizationProblems}}

Текущая версия на 13:46, 27 сентября 2024

Задача Штейнера о минимальном дереве.

Т.е. у нас есть неориентированный граф, где

  • N=74 узлов, узлы графа двух типов:
Терминальные
Они должны быть частью сети.
Штейнера
Не обязательно, чтобы они были частью сети.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74
Терминальный? 0 0 0 0 0 0 0 0 0 1 1 1 0 1 0 0 0 1 0 0 0 1 0 0 0 0 1 0 1 1 0 0 1 0 0 1 1 1 0 0 0 0 0 0 1 1 1 1 0 0 1 0 0 0 1 0 1 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0
  • M=153 неориентированных ребер в весом-стоимостью, которых мы представим 306 двойными дугами, ребро (i, j, w) → в ребро i→j (w) и ребро j→i (w)

Надо найти подграф минимальной стоимости, соединающий все терминальные узлы.

Источник — «https://discopal.ispras.ru/index.php?title=Optprob/Задача_Штейнера_о_минимальном_дереве&oldid=29775»