Материал: Алгоритм распознавания единичного интервального графа
Все три алгоритма распознают единичные интервальные графы,
В программах LBFS3 и MNS3 встроен алгоритм проверки на I и UI порядок (UI включает в себя проверку на I порядок), что в некоторых случаях позволило определить интервальные графы. Конечно, это получается случайно, если порядок вершин изменить, то программы LBFS3 и MNS3 выдадут: граф не является интервальным.
Все программы также определяют, является ли граф связным.
4.1 Тестирование алгоритма четырех махов
Для подтверждения работоспособности алгоритма четырех махов были
проведены серии расчетов на тестовом графе с 22 вершинами (Рис.8, раздел 2.3).
В расчетах случайным образом менялся порядок вершин и контролировались выходные
данные. Во всех расчетах было получено, что граф является интервальным.
Некоторые из возможных получаемых порядков вершин на каждом из 4 этапов
приведены на Рис.20. Если расчет начинается с вершин 4, 21 или 22, то в
итоговом порядке вершины расположены по возрастанию. Если расчет начинается с
других вершин, то UI порядок будет
обратным, отсортированным по правой границе интервалов, и не по убыванию
порядковых номеров. Во всех случаях для данного графа на третьем этапе
получается одинаковая последовательность вершин, хотя и не являющаяся UI порядком, что требует четвертого
окончательного прохода и сортировки.
Рис. 20- Результаты работы LBFS4
на каждом этапе для 8 запусков
Результаты приведенных расчетов показывают работоспособность алгоритма 4
махов для распознавания интервальных графов. Во всех случаях, при различной
начальной перенумерации вершин тестового графа, был получен верный результат.
4.2 Исследования временных затрат алгоритмов
Исследования временных затрат алгоритмов были проведены для трех
вариантов программ: LBFS4, LBFS3, MNS3; для двух вариантов сборки исполняемого файла: Debug и Release (без оптимизации и с оптимизацией кода); для трех
типов графов: единичный интервальный, интервальный, случайный Эрдёша-Реньи. В
сериях расчетов одновременно пропорционально увеличивалось число вершин и ребер
графа для проверки линейности трудозатрат алгоритмов. Также были проведены две
серии расчетов для графов с различным соотношением числа ребер к числу вершин:
25 и 1000. В расчетах контролировалось время выполнения алгоритма. Результаты
засечек приведены в таблицах 2-5 и на рисунках 21, 22 в виде графиков.
Таблица 2 - Время счета задач, секунд. Нетбук с процессором Интел Атом 1.6GHz. Режим Debug. Число Ребер / Число вершин ~25
|
Число вершин, тысяч |
Число ребер |
LBFS 4 |
LBFS 3 |
MNS 3 |
||||||
|
|
|
ед.инт. |
инт. |
случ. |
ед.инт. |
инт. |
случ. |
ед.инт. |
инт. |
случ. |
|
20 |
500537 |
0.889 |
1.155 |
2.655 |
0.842 |
0.76 |
1.721 |
0.187 |
0.214 |
0.598 |
|
40 |
998937 |
1.544 |
2.214 |
5.028 |
1.17 |
1.517 |
3.685 |
0.343 |
0.462 |
1.186 |
|
60 |
1498010 |
2.449 |
3.464 |
7.959 |
1.779 |
2.269 |
5.331 |
0.499 |
0.674 |
1.934 |
|
80 |
1997430 |
4.02 |
4.503 |
10.13 |
2.481 |
3.037 |
7.199 |
0.718 |
0.9 |
2.54 |
|
100 |
2497160 |
5.07 |
5.687 |
12.88 |
2.948 |
3.748 |
9.049 |
0.889 |
1.104 |
3.301 |
|
120 |
2996730 |
5.726 |
6.838 |
15.77 |
3.51 |
4.569 |
11.14 |
1.092 |
1.34 |
3.834 |
|
140 |
3496650 |
6.349 |
8.071 |
18.31 |
4.664 |
5.352 |
12.91 |
1.577 |
1.54 |
4.506 |
|
160 |
3996480 |
8.034 |
9.177 |
20.92 |
5.164 |
6.046 |
14.71 |
1.513 |
1.752 |
5.047 |
|
180 |
4497290 |
8.096 |
10.39 |
23.6 |
6.115 |
6.854 |
16.66 |
2.184 |
2.007 |
5.916 |
|
200 |
4997230 |
10.37 |
11.47 |
26.28 |
7.27 |
7.589 |
18.45 |
2.215 |
2.235 |
6.326 |
|
220 |
5497100 |
10.93 |
12.62 |
28.96 |
7.753 |
8.332 |
20.38 |
2.106 |
2.447 |
7.41 |
|
240 |
5995570 |
11.45 |
13.74 |
31.42 |
7.675 |
9.041 |
22.24 |
2.387 |
8.016 |
|
|
260 |
6496380 |
12.68 |
14.9 |
34.45 |
8.143 |
9.798 |
23.95 |
2.527 |
2.904 |
8.62 |
|
280 |
6998290 |
13.65 |
16.16 |
37.17 |
9.142 |
10.65 |
25.9 |
2.886 |
3.084 |
9.348 |
|
300 |
7500650 |
14.29 |
17.31 |
39.73 |
9.843 |
11.39 |
27.69 |
3.042 |
3.312 |
10.05 |
|
320 |
8000110 |
16.08 |
18.44 |
42.44 |
10.10 |
12.09 |
29.63 |
3.338 |
3.564 |
10.85 |
|
340 |
8499520 |
16.38 |
19.49 |
45.06 |
10.62 |
12.85 |
31.44 |
3.407 |
3.789 |
11.42 |
|
360 |
8998140 |
17.64 |
20.76 |
47.92 |
11.34 |
13.64 |
33.55 |
3.686 |
4.006 |
12.22 |
|
380 |
9497400 |
19.78 |
21.93 |
50.44 |
11.94 |
14.51 |
35.47 |
4.056 |
4.247 |
12.93 |
|
400 |
9995670 |
20.49 |
23.17 |
52.98 |
13.01 |
15.29 |
37.21 |
4.109 |
4.473 |
13.6 |
|
420 |
10494700 |
21.09 |
24.27 |
55.77 |
13.36 |
16 |
38.89 |
4.288 |
4.689 |
14.25 |
|
440 |
10993800 |
22.62 |
25.37 |
58.33 |
14.73 |
16.72 |
40.8 |
4.504 |
4.891 |
15.1 |
|
460 |
11494100 |
23.80 |
26.58 |
61.18 |
15.69 |
17.51 |
42.81 |
4.765 |
5.134 |
15.63 |
|
480 |
11995100 |
24.20 |
27.71 |
63.75 |
15.91 |
18.36 |
44.58 |
5.023 |
5.341 |
16.4 |
|
500 |
12495700 |
24.67 |
28.93 |
66.49 |
16.20 |
19.08 |
46.65 |
5.242 |
5.573 |
17 |
|
520 |
12996400 |
26.02 |
30.11 |
69.23 |
16.97 |
19.9 |
48.46 |
5.429 |
5.789 |
17.74 |
|
540 |
13497300 |
27.19 |
31.24 |
71.83 |
18.00 |
20.57 |
50.22 |
5.567 |
5.995 |
18.56 |
|
560 |
13996200 |
28.79 |
32.33 |
74.34 |
19.16 |
21.36 |
51.97 |
5.852 |
6.257 |
19.16 |
|
580 |
14495400 |
29.45 |
33.57 |
77.5 |
19.99 |
22.09 |
53.87 |
6.052 |
6.468 |
19.72 |
Таблица 3 - Время счета задач, секунд. Нетбук с процессором Интел Атом 1.6GHz. Режим Release. Число Ребер / Число вершин ~25
|
Число вершин, тысяч |
Число ребер |
LBFS 4 |
LBFS 3 |
MNS 3 |
||||||
|
|
|
ед.инт. |
инт. |
случ. |
ед.инт. |
инт. |
случ. |
ед.инт. |
инт. |
случ. |
|
20 |
500537 |
0.509 |
0.576 |
2.058 |
0.276 |
0.323 |
1.373 |
0.133 |
0.141 |
0.55 |
|
40 |
998937 |
0.966 |
1.098 |
3.778 |
0.574 |
0.679 |
2.988 |
0.273 |
0.282 |
1.072 |
|
60 |
1498010 |
1.526 |
1.728 |
6.171 |
0.839 |
0.988 |
4.292 |
0.417 |
0.444 |
1.775 |
|
80 |
1997430 |
1.928 |
2.184 |
7.846 |
1.11 |
1.306 |
5.744 |
0.555 |
0.592 |
2.386 |
|
100 |
2497160 |
2.403 |
2.735 |
9.758 |
1.385 |
1.642 |
7.12 |
0.702 |
0.747 |
3.068 |
|
120 |
2996730 |
2.987 |
3.389 |
12.13 |
1.73 |
2.051 |
9.055 |
0.835 |
0.912 |
3.592 |
|
140 |
3496650 |
3.5 |
3.962 |
14.22 |
2.004 |
2.37 |
10.44 |
0.981 |
1.042 |
4.153 |
|
160 |
3996480 |
4 |
4.534 |
16.33 |
2.293 |
2.73 |
11.94 |
1.133 |
1.19 |
4.739 |
|
180 |
4497290 |
4.52 |
5.122 |
18.37 |
2.591 |
3.07 |
13.55 |
1.261 |
1.347 |
5.438 |
|
200 |
4997230 |
4.976 |
5.687 |
20.35 |
2.861 |
3.432 |
14.85 |
1.4 |
1.497 |
6.102 |
|
220 |
5497100 |
5.519 |
6.251 |
22.45 |
3.156 |
3.725 |
16.37 |
1.554 |
1.658 |
6.939 |
|
240 |
5995570 |
6.061 |
6.862 |
24.47 |
3.44 |
4.053 |
17.74 |
1.693 |
1.802 |
7.5 |
|
260 |
6496380 |
6.578 |
7.445 |
26.56 |
3.736 |
4.505 |
19.36 |
1.823 |
1.949 |
8.065 |
|
280 |
6998290 |
7.126 |
8.068 |
4.026 |
4.796 |
20.99 |
1.972 |
2.102 |
8.755 |
|
|
300 |
7500650 |
7.63 |
8.639 |
30.85 |
4.322 |
5.109 |
22.55 |
2.116 |
2.25 |
9.4 |
|
320 |
8000110 |
8.132 |
9.2 |
32.91 |
4.597 |
5.436 |
23.86 |
2.263 |
2.41 |
10.08 |
|
340 |
8499520 |
8.656 |
9.774 |
34.74 |
4.898 |
5.796 |
25.48 |
2.402 |
2.562 |
10.73 |
|
360 |
8998140 |
9.142 |
10.36 |
36.97 |
5.182 |
6.177 |
26.98 |
2.545 |
2.716 |
11.4 |
|
380 |
9497400 |
9.672 |
10.95 |
39.09 |
5.467 |
6.461 |
28.69 |
2.688 |
2.865 |
12.03 |
|
400 |
9995670 |
10.19 |
11.52 |
41.09 |
5.762 |
6.817 |
30.23 |
2.826 |
3.015 |
12.62 |
|
420 |
10494700 |
10.69 |
12.11 |
43.25 |
6.055 |
7.173 |
31.76 |
2.972 |
3.167 |
13.3 |
|
440 |
10993800 |
11.21 |
12.7 |
45.36 |
6.354 |
7.514 |
33.31 |
3.116 |
3.321 |
13.99 |
|
460 |
11494100 |
11.73 |
13.27 |
47.29 |
6.637 |
7.855 |
34.76 |
3.257 |
3.472 |
14.62 |
|
480 |
11995100 |
12.23 |
13.84 |
49.42 |
6.926 |
8.189 |
36.35 |
3.398 |
3.632 |
15.26 |
|
500 |
12495700 |
12.8 |
14.45 |
51.73 |
7.214 |
8.584 |
38.07 |
3.538 |
3.774 |
15.87 |
|
520 |
12996400 |
13.28 |
15.03 |
53.74 |
7.512 |
8.931 |
39.44 |
3.679 |
3.925 |
16.54 |
|
540 |
13497300 |
13.8 |
15.62 |
55.85 |
7.799 |
9.249 |
40.91 |
3.824 |
4.089 |
17.25 |
|
560 |
13996200 |
14.26 |
16.14 |
57.64 |
8.102 |
9.639 |
42.53 |
3.966 |
4.23 |
17.83 |
|
580 |
14495400 |
14.86 |
16.91 |
60.13 |
8.368 |
9.925 |
43.83 |
4.103 |
4.377 |
18.39 |
Таблица 4 - Время счета задач, секунд. Нетбук с процессором Интел Атом 1.6GHz. Режим Debug. Число Ребер / Число вершин ~1000
|
Число вершин, тысяч |
Число ребер |
LBFS 4 |
LBFS 3 |
MNS 3 |
||||||
|
|
|
ед.инт. |
инт. |
случ. |
ед.инт. |
инт. |
случ. |
ед.инт. |
инт. |
случ. |
|
0.5 |
124750 |
0.721 |
0.718 |
0.891 |
0.463 |
0.47 |
0.576 |
0.102 |
0.043 |
0.054 |
|
1 |
499500 |
1.313 |
1.299 |
1.606 |
1.008 |
1.014 |
1.26 |
0.198 |
0.084 |
0.105 |
|
1.5 |
1124300 |
2.163 |
2.153 |
2.674 |
1.478 |
1.429 |
1.785 |
0.333 |
0.139 |
0.172 |
|
2 |
1512800 |
2.727 |
2.668 |
3.287 |
1.926 |
1.93 |
2.406 |
0.456 |
0.188 |
0.233 |
|
2.5 |
2352000 |
3.529 |
3.425 |
4.137 |
2.49 |
2.361 |
3.042 |
0.588 |
0.238 |
0.313 |
|
3 |
2508400 |
4.253 |
4.205 |
5.271 |
3.059 |
3.081 |
3.827 |
0.699 |
0.280 |
0.407 |
|
3.5 |
3410000 |
5.004 |
4.961 |
6.052 |
3.521 |
3.515 |
4.376 |
0.845 |
0.330 |
0.445 |
|
4 |
3506500 |
5.759 |
5.627 |
7.029 |
4.067 |
4.093 |
5.051 |
0.916 |
0.374 |
0.552 |
|
4.5 |
4431000 |
6.519 |
6.38 |
7.941 |
4.586 |
4.617 |
5.722 |
1.066 |
0.421 |
0.570 |
|
5 |
4499600 |
7.147 |
7.044 |
8.771 |
5.094 |
5.003 |
6.279 |
1.146 |
0.472 |
0.663 |
|
5.5 |
5443200 |
7.868 |
7.797 |
9.708 |
5.597 |
5.55 |
6.944 |
1.316 |
0.530 |
0.679 |
|
6 |
5489300 |
8.599 |
8.552 |
10.68 |
6.106 |
6.048 |
7.506 |
1.418 |
0.579 |
0.781 |
|
6.5 |
6443100 |
9.302 |
9.293 |
11.57 |
6.631 |
6.602 |
8.143 |
1.552 |
0.614 |
0.858 |
|
7 |
6482800 |
10.1 |
10.06 |
12.49 |
7.147 |
7.193 |
8.865 |
1.692 |
0.680 |
0.862 |
|
7.5 |
7439000 |
10.8 |
10.77 |
13.37 |
7.659 |
7.707 |
9.566 |
1.775 |
0.749 |
|
|
8 |
7469000 |
11.54 |
11.48 |
14.25 |
8.136 |
8.166 |
10.17 |
1.933 |
0.780 |
0.982 |
|
8.5 |
8437300 |
12.26 |
12.18 |
15.11 |
8.654 |
8.712 |
10.81 |
2.048 |
0.836 |
1.042 |
|
9 |
8472800 |
13.03 |
12.92 |
16.02 |
9.118 |
9.21 |
11.47 |
2.153 |
0.879 |
1.107 |
|
9.5 |
9442700 |
13.71 |
13.66 |
16.94 |
9.642 |
9.723 |
12.14 |
2.276 |
0.934 |
1.169 |
|
10 |
9477600 |
14.4 |
14.37 |
17.8 |
10.2 |
10.24 |
12.76 |
2.38 |
0.980 |
1.254 |
|
10.5 |
10448000 |
15.15 |
15.09 |
18.74 |
10.72 |
10.78 |
13.39 |
2.533 |
1.032 |
1.313 |
|
11 |
10471000 |
15.87 |
15.83 |
19.61 |
11.27 |
11.29 |
14.1 |
2.664 |
1.024 |
1.368 |
|
11.5 |
11449000 |
16.61 |
16.56 |
20.53 |
11.75 |
11.81 |
14.69 |
2.778 |
1.107 |
1.407 |
|
12 |
11477000 |
17.32 |
17.25 |
21.41 |
12.23 |
12.31 |
15.34 |
2.88 |
1.164 |
1.467 |
|
12.5 |
12451000 |
18.11 |
18.02 |
22.36 |
12.72 |
12.87 |
16.03 |
2.999 |
1.209 |
1.536 |
|
13 |
12479000 |
18.79 |
18.74 |
23.37 |
13.23 |
13.41 |
16.68 |
3.117 |
1.26 |
1.612 |
|
13.5 |
13458000 |
19.54 |
19.48 |
24.19 |
13.81 |
13.93 |
17.28 |
3.255 |
1.291 |
1.631 |
|
14 |
13476000 |
20.2 |
20.12 |
24.98 |
14.36 |
14.58 |
17.93 |
3.365 |
1.366 |
1.703 |
|
14.5 |
14458000 |
21.05 |
20.91 |
26.01 |
14.8 |
14.92 |
18.52 |
3.48 |
1.409 |
1.786 |
Таблица 5 - Время счета задач, секунд. Нетбук с процессором Интел Атом 1.6GHz. Режим Release. Число Ребер / Число вершин ~1000
|
Число вершин, тысяч |
Число ребер |
LBFS 4 |
LBFS 3 |
MNS 3 |
||||||
|
|
|
ед.инт. |
инт. |
случ. |
ед.инт. |
инт. |
случ. |
ед.инт. |
инт. |
случ. |
|
0.5 |
124750 |
0.201 |
0.238 |
0.312 |
0.126 |
0.151 |
0.198 |
0.053 |
0.024 |
0.030 |
|
1 |
499500 |
0.362 |
0.421 |
0.551 |
0.277 |
0.334 |
0.439 |
0.105 |
0.050 |
0.061 |
|
1.5 |
1124300 |
0.605 |
0.713 |
0.935 |
0.389 |
0.466 |
0.607 |
0.176 |
0.084 |
0.101 |
|
2 |
1512800 |
0.739 |
0.854 |
1.164 |
0.510 |
0.608 |
0.793 |
0.24 |
0.114 |
0.135 |
|
2.5 |
2352000 |
0.943 |
1.074 |
1.478 |
0.649 |
0.743 |
1.033 |
0.310 |
0.145 |
0.188 |
|
3 |
2508400 |
1.177 |
1.375 |
1.854 |
0.842 |
1.016 |
1.338 |
0.358 |
0.165 |
0.222 |
|
3.5 |
3410000 |
1.379 |
1.597 |
2.139 |
0.960 |
1.142 |
1.532 |
0.423 |
0.196 |
0.258 |
|
4 |
3506500 |
1.566 |
1.826 |
2.438 |
1.096 |
1.316 |
1.742 |
0.476 |
0.221 |
0.295 |
|
4.5 |
4431000 |
1.786 |
2.079 |
2.76 |
1.258 |
1.514 |
1.994 |
0.549 |
0.257 |
0.339 |
|
5 |
4499600 |
1.934 |
2.261 |
3.061 |
1.356 |
1.634 |
2.149 |
0.601 |
0.288 |
0.381 |
|
5.5 |
5443200 |
2.18 |
2.537 |
3.387 |
1.518 |
1.823 |
2.385 |
0.698 |
0.326 |
0.401 |
|
6 |
5489300 |
2.402 |
2.801 |
3.711 |
1.633 |
1.974 |
2.61 |
0.746 |
0.353 |
0.446 |
|
6.5 |
6443100 |
2.606 |
3.051 |
4.019 |
1.804 |
2.162 |
2.831 |
0.804 |
0.382 |
0.473 |
|
7 |
6482800 |
2.825 |
3.33 |
4.37 |
1.946 |
2.348 |
3.073 |
0.880 |
0.409 |
0.507 |
|
7.5 |
7439000 |
3.026 |
3.563 |
4.673 |
2.103 |
2.53 |
3.328 |
0.942 |
0.442 |
0.542 |
|
8 |
7469000 |
3.216 |
3.794 |
4.965 |
2.218 |
2.687 |
3.515 |
1.01 |
0.474 |
0.590 |
|
8.5 |
8437300 |
3.424 |
4.003 |
5.215 |
2.868 |
3.762 |
1.081 |
0.506 |
0.618 |
|
|
9 |
8472800 |
3.617 |
4.256 |
5.551 |
2.527 |
3.046 |
3.978 |
1.148 |
0.536 |
0.662 |
|
9.5 |
9442700 |
3.837 |
4.52 |
5.927 |
2.678 |
3.209 |
4.225 |
1.213 |
0.566 |
0.691 |
|
10 |
9477600 |
4.059 |
4.776 |
6.228 |
2.801 |
3.382 |
4.449 |
1.271 |
0.595 |
0.720 |
|
10.5 |
10448000 |
4.245 |
5.003 |
6.551 |
2.956 |
3.559 |
4.686 |
1.348 |
0.625 |
0.759 |
|
11 |
10471000 |
4.439 |
5.249 |
6.867 |
3.084 |
3.728 |
4.907 |
1.418 |
0.658 |
0.827 |
|
11.5 |
11449000 |
4.668 |
5.506 |
7.185 |
3.24 |
3.896 |
5.152 |
1.486 |
0.687 |
0.845 |
|
12 |
11477000 |
4.85 |
5.719 |
7.498 |
3.376 |
4.067 |
5.4 |
1.544 |
0.716 |
0.867 |
|
12.5 |
12451000 |
5.089 |
5.991 |
7.853 |
3.54 |
4.288 |
5.633 |
1.602 |
0.745 |
0.917 |
|
13 |
12479000 |
5.265 |
6.246 |
8.211 |
3.664 |
4.429 |
5.826 |
1.666 |
0.776 |
0.944 |
|
13.5 |
13458000 |
5.479 |
6.489 |
8.554 |
3.82 |
4.61 |
6.064 |
1.751 |
0.810 |
1.005 |
|
14 |
13476000 |
5.655 |
6.666 |
8.746 |
3.974 |
4.836 |
6.34 |
1.801 |
0.838 |
1.012 |
|
14.5 |
14458000 |
5.919 |
7.002 |
9.229 |
4.084 |
4.93 |
6.485 |
1.856 |
0.864 |
1.058 |