Optprob/Выбор ребер и узлов в графе

Задача зарезервирована: Sfirstov 10:47, 10 декабря 2023 (UTC)

Есть неориентированный граф, список ребер…

в формате «узел узел стоимость»

1 49                 6   
4 5                  1 
4 48                 1 
7 17                 4 
7 33                 5 
9 10                 4 
9 18                 5 
9 21                 1 
9 22                 8 
9 41                 10 
9 45                 9 
10 6                 4 
10 13                1 
10 30                8 
10 48                1 
11 3                 8 
11 15                8 
11 20                5 
12 35                8 
13 34                2 
14 28                7 
15 47                9 
16 38                2 
17 50                7 
18 16                4 
19 12                9 
20 10                4 
20 23                7 
21 8                 7 
21 11                8 
21 12                1 
21 30                9 
22 4                 5 
22 5                 4 
22 25                2 
22 50                5 
24 27                5 
26 39                6 
27 9                 1 
29 7                 4 
29 37                2 
30 12                5 
30 26                10 
30 32                4 
31 5                 2 
31 30                8 
33 36                5 
34 1                 10 
34 46                6 
36 42                8 
37 31                2 
40 19                8 
40 24                1 
41 29                4 
41 42                6 
42 44                9 
43 9                 2 
45 6                 3 
48 2                 8 
50 14                7 
50 39                1 
50 40                5 
50 43                7

Надо выбрать пять узлов и десять ребер (по два соседствующих с каждым ребром на каждый узел), так, чтобы сумма весов всех этих ребер будет минимальна.

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.