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

Материал из DISCOPAL

Перейти к: навигация, поиск

Категория:

OptimizationProblems

Версия 13:40, 27 ноября 2022

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

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

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)

сотни дуг с весами

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

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

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

Категория:

OptimizationProblems

Навигация