StasFomin в 13:46, 27 сентября 2024

2024-09-27T13:46:20Z

StasFomin: Массовая правка: замена Категория:OptimizationProblems на {{Cat4Term2|{{FULLPAGENAME}}|OptimizationProblems}}

2023-12-23T11:59:18Z

Массовая правка: замена Категория:OptimizationProblems на {{Cat4Term2|{{FULLPAGENAME}}|OptimizationProblems}}

Sfirstov в 18:05, 12 декабря 2023

2023-12-12T18:05:22Z

StasFomin в 13:40, 27 ноября 2022

2022-11-27T13:40:03Z

StasFomin: Новая страница: « {{checked|}} [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%…»

2022-11-18T08:17:52Z

Новая страница: « {{checked|}} [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%…»

Новая страница

{{checked|}}

[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 Задача Штейнера о минимальном дереве].

Т.е. у нас есть неориентированный граф, где
* N=74 узлов, узлы графа двух типов:
;Терминальные: Они должны быть частью сети.
;Штейнера: Не обязательно, чтобы они были частью сети.

{| class=wikitable
|-
| <br>
| 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)

{{WikiCutBegin|сотни дуг с весами}}

{| class=wikitable
|-
| 1
| 18
| 2
|-
| 2
| 20
| 2
|-
| 3
| 1
| 1
|-
| 3
| 23
| 3
|-
| 3
| 74
| 8
|-
| 4
| 13
| 3
|-
| 5
| 3
| 2
|-
| 5
| 4
| 6
|-
| 5
| 16
| 6
|-
| 5
| 20
| 3
|-
| 5
| 47
| 6
|-
| 5
| 50
| 7
|-
| 5
| 59
| 10
|-
| 5
| 68
| 5
|-
| 6
| 32
| 1
|-
| 6
| 59
| 3
|-
| 7
| 23
| 9
|-
| 8
| 1
| 1
|-
| 8
| 33
| 5
|-
| 8
| 44
| 5
|-
| 9
| 16
| 7
|-
| 9
| 37
| 8
|-
| 10
| 12
| 8
|-
| 13
| 26
| 9
|-
| 13
| 30
| 4
|-
| 14
| 52
| 2
|-
| 14
| 54
| 2
|-
| 14
| 62
| 4
|-
| 15
| 24
| 8
|-
| 15
| 41
| 1
|-
| 16
| 15
| 9
|-
| 16
| 19
| 6
|-
| 17
| 44
| 6
|-
| 17
| 1
| 2
|-
| 18
| 24
| 2
|-
| 18
| 63
| 6
|-
| 18
| 69
| 3
|-
| 19
| 6
| 6
|-
| 19
| 38
| 8
|-
| 19
| 72
| 8
|-
| 20
| 7
| 7
|-
| 21
| 42
| 3
|-
| 22
| 11
| 4
|-
| 22
| 28
| 5
|-
| 22
| 43
| 6
|-
| 22
| 51
| 3
|-
| 23
| 39
| 5
|-
| 24
| 57
| 4
|-
| 25
| 36
| 1
|-
| 25
| 66
| 5
|-
| 26
| 16
| 10
|-
| 26
| 53
| 3
|-
| 27
| 48
| 3
|-
| 29
| 31
| 3
|-
| 31
| 48
| 9
|-
| 31
| 72
| 2
|-
| 32
| 28
| 2
|-
| 32
| 25
| 2
|-
| 33
| 13
| 9
|-
| 33
| 17
| 7
|-
| 34
| 11
| 3
|-
| 35
| 34
| 10
|-
| 35
| 42
| 1
|-
| 36
| 7
| 2
|-
| 36
| 68
| 8
|-
| 37
| 68
| 1
|-
| 37
| 73
| 10
|-
| 39
| 9
| 1
|-
| 39
| 28
| 8
|-
| 39
| 45
| 8
|-
| 39
| 54
| 3
|-
| 39
| 65
| 6
|-
| 39
| 71
| 2
|-
| 40
| 12
| 5
|-
| 40
| 27
| 2
|-
| 40
| 52
| 3
|-
| 40
| 20
| 8
|-
| 41
| 30
| 6
|-
| 41
| 52
| 2
|-
| 42
| 14
| 5
|-
| 42
| 30
| 10
|-
| 42
| 62
| 3
|-
| 42
| 72
| 7
|-
| 43
| 10
| 5
|-
| 11
| 42
| 7
|-
| 44
| 7
| 5
|-
| 44
| 59
| 6
|-
| 45
| 40
| 1
|-
| 46
| 5
| 9
|-
| 46
| 25
| 6
|-
| 46
| 15
| 7
|-
| 46
| 39
| 9
|-
| 48
| 24
| 6
|-
| 49
| 38
| 1
|-
| 49
| 47
| 6
|-
| 49
| 53
| 7
|-
| 49
| 56
| 4
|-
| 50
| 67
| 6
|-
| 50
| 71
| 6
|-
| 51
| 38
| 1
|-
| 51
| 42
| 9
|-
| 51
| 63
| 10
|-
| 51
| 70
| 8
|-
| 52
| 47
| 5
|-
| 52
| 66
| 8
|-
| 52
| 70
| 1
|-
| 53
| 9
| 8
|-
| 53
| 25
| 9
|-
| 54
| 36
| 2
|-
| 55
| 9
| 7
|-
| 55
| 17
| 1
|-
| 55
| 49
| 3
|-
| 55
| 61
| 7
|-
| 56
| 2
| 6
|-
| 56
| 59
| 3
|-
| 56
| 65
| 1
|-
| 57
| 63
| 5
|-
| 58
| 70
| 7
|-
| 60
| 15
| 2
|-
| 60
| 17
| 1
|-
| 60
| 25
| 1
|-
| 60
| 29
| 1
|-
| 61
| 8
| 8
|-
| 61
| 58
| 6
|-
| 62
| 7
| 7
|-
| 62
| 48
| 2
|-
| 62
| 58
| 2
|-
| 62
| 64
| 1
|-
| 64
| 55
| 3
|-
| 65
| 11
| 5
|-
| 66
| 39
| 10
|-
| 67
| 55
| 1
|-
| 67
| 72
| 4
|-
| 68
| 6
| 10
|-
| 68
| 19
| 5
|-
| 68
| 21
| 3
|-
| 68
| 22
| 10
|-
| 68
| 56
| 6
|-
| 68
| 64
| 7
|-
| 69
| 21
| 2
|-
| 69
| 35
| 5
|-
| 70
| 4
| 7
|-
| 70
| 23
| 5
|-
| 70
| 10
| 10
|-
| 70
| 34
| 17
|-
| 71
| 1
| 9
|-
| 72
| 2
| 7
|-
| 72
| 43
| 6
|-
| 73
| 8
| 6
|-
| 73
| 26
| 6
|-
| 74
| 10
| 5
|-
| 74
| 37
| 3
|-
| 74
| 71
| 4
|-
| 18
| 1
| 2
|-
| 20
| 2
| 2
|-
| 1
| 3
| 1
|-
| 23
| 3
| 3
|-
| 74
| 3
| 8
|-
| 13
| 4
| 3
|-
| 3
| 5
| 2
|-
| 4
| 5
| 6
|-
| 16
| 5
| 6
|-
| 20
| 5
| 3
|-
| 47
| 5
| 6
|-
| 50
| 5
| 7
|-
| 59
| 5
| 10
|-
| 68
| 5
| 5
|-
| 32
| 6
| 1
|-
| 59
| 6
| 3
|-
| 23
| 7
| 9
|-
| 1
| 8
| 1
|-
| 33
| 8
| 5
|-
| 44
| 8
| 5
|-
| 16
| 9
| 7
|-
| 37
| 9
| 8
|-
| 12
| 10
| 8
|-
| 26
| 13
| 9
|-
| 30
| 13
| 4
|-
| 52
| 14
| 2
|-
| 54
| 14
| 2
|-
| 62
| 14
| 4
|-
| 24
| 15
| 8
|-
| 41
| 15
| 1
|-
| 15
| 16
| 9
|-
| 19
| 16
| 6
|-
| 44
| 17
| 6
|-
| 1
| 17
| 2
|-
| 24
| 18
| 2
|-
| 63
| 18
| 6
|-
| 69
| 18
| 3
|-
| 6
| 19
| 6
|-
| 38
| 19
| 8
|-
| 72
| 19
| 8
|-
| 7
| 20
| 7
|-
| 42
| 21
| 3
|-
| 11
| 22
| 4
|-
| 28
| 22
| 5
|-
| 43
| 22
| 6
|-
| 51
| 22
| 3
|-
| 39
| 23
| 5
|-
| 57
| 24
| 4
|-
| 36
| 25
| 1
|-
| 66
| 25
| 5
|-
| 16
| 26
| 10
|-
| 53
| 26
| 3
|-
| 48
| 27
| 3
|-
| 31
| 29
| 3
|-
| 48
| 31
| 9
|-
| 72
| 31
| 2
|-
| 28
| 32
| 2
|-
| 25
| 32
| 2
|-
| 13
| 33
| 9
|-
| 17
| 33
| 7
|-
| 11
| 34
| 3
|-
| 34
| 35
| 10
|-
| 42
| 35
| 1
|-
| 7
| 36
| 2
|-
| 68
| 36
| 8
|-
| 68
| 37
| 1
|-
| 73
| 37
| 10
|-
| 9
| 39
| 1
|-
| 28
| 39
| 8
|-
| 45
| 39
| 8
|-
| 54
| 39
| 3
|-
| 65
| 39
| 6
|-
| 71
| 39
| 2
|-
| 12
| 40
| 5
|-
| 27
| 40
| 2
|-
| 52
| 40
| 3
|-
| 20
| 40
| 8
|-
| 30
| 41
| 6
|-
| 52
| 41
| 2
|-
| 14
| 42
| 5
|-
| 30
| 42
| 10
|-
| 62
| 42
| 3
|-
| 72
| 42
| 7
|-
| 10
| 43
| 5
|-
| 42
| 11
| 7
|-
| 7
| 44
| 5
|-
| 59
| 44
| 6
|-
| 40
| 45
| 1
|-
| 5
| 46
| 9
|-
| 25
| 46
| 6
|-
| 15
| 46
| 7
|-
| 39
| 46
| 9
|-
| 24
| 48
| 6
|-
| 38
| 49
| 1
|-
| 47
| 49
| 6
|-
| 53
| 49
| 7
|-
| 56
| 49
| 4
|-
| 67
| 50
| 6
|-
| 71
| 50
| 6
|-
| 38
| 51
| 1
|-
| 42
| 51
| 9
|-
| 63
| 51
| 10
|-
| 70
| 51
| 8
|-
| 47
| 52
| 5
|-
| 66
| 52
| 8
|-
| 70
| 52
| 1
|-
| 9
| 53
| 8
|-
| 25
| 53
| 9
|-
| 36
| 54
| 2
|-
| 9
| 55
| 7
|-
| 17
| 55
| 1
|-
| 49
| 55
| 3
|-
| 61
| 55
| 7
|-
| 2
| 56
| 6
|-
| 59
| 56
| 3
|-
| 65
| 56
| 1
|-
| 63
| 57
| 5
|-
| 70
| 58
| 7
|-
| 15
| 60
| 2
|-
| 17
| 60
| 1
|-
| 25
| 60
| 1
|-
| 29
| 60
| 1
|-
| 8
| 61
| 8
|-
| 58
| 61
| 6
|-
| 7
| 62
| 7
|-
| 48
| 62
| 2
|-
| 58
| 62
| 2
|-
| 64
| 62
| 1
|-
| 55
| 64
| 3
|-
| 11
| 65
| 5
|-
| 39
| 66
| 10
|-
| 55
| 67
| 1
|-
| 72
| 67
| 4
|-
| 6
| 68
| 10
|-
| 19
| 68
| 5
|-
| 21
| 68
| 3
|-
| 22
| 68
| 10
|-
| 56
| 68
| 6
|-
| 64
| 68
| 7
|-
| 21
| 69
| 2
|-
| 35
| 69
| 5
|-
| 4
| 70
| 7
|-
| 23
| 70
| 5
|-
| 10
| 70
| 10
|-
| 34
| 70
| 17
|-
| 1
| 71
| 9
|-
| 2
| 72
| 7
|-
| 43
| 72
| 6
|-
| 8
| 73
| 6
|-
| 26
| 73
| 6
|-
| 10
| 74
| 5
|-
| 37
| 74
| 3
|-
| 71
| 74
| 4
|}

{{WikiCutEnd}}

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

{{enddiv}}

[[Категория:OptimizationProblems]]

← Предыдущая		Версия 11:59, 23 декабря 2023
Строка 1402:		Строка 1402:
	{{enddiv}}		{{enddiv}}

−	~~[[Категория:~~OptimizationProblems]]	+	{{Cat4Term2\|{{FULLPAGENAME}}\|OptimizationProblems}}

@@ Строка 1: / Строка 1: @@
 <!-- p30 -->
 {{checked|}}
 [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 Задача Штейнера о минимальном дереве].

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

StasFomin в 13:46, 27 сентября 2024

StasFomin: Массовая правка: замена Категория:OptimizationProblems на {{Cat4Term2|{{FULLPAGENAME}}|OptimizationProblems}}

Sfirstov в 18:05, 12 декабря 2023

StasFomin в 13:40, 27 ноября 2022

StasFomin: Новая страница: « {{checked|}} [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%…»