Обход полного графа и его модификаций
В данном разделе будут рассмотрены экспериментальные данные по построению обхода для следующих видов графов.
Полный ориентированный граф с N вершинами, обозначаемый KN.
Граф KM(KN), представляющий собой соединенные с помощью KM M полных графов KN. Вершины этих M графов пронумерованы числами от 0 до (N-1) и все вершины с номером 0 соединены между собой полным графом.
Граф KM KN, являющийся декартовым произведением полных графов. Он тоже представляется как M графов KN с пронумерованными вершинами, в которых всем вершинам с одинаковыми номерами соединены друг с другом.
В следующих таблицах приведены длины и время (в секундах) построения обхода разными обходчиками для таких графов.
Числа N и M выбраны нечетными, потому что для полного графа с нечетным количеством вершин существует эйлеров цикл.
Теоретическая оценка длины обхода KN снизу равна количеству его дуг E(KN)=N × (N - 1).
| K3 | 14 | 0 | 8 | 0 | 6 |
| K5 | 60 | 0 | 24 | 0 | 20 |
| K7 | 154 | 0 | 48 | 0 | 42 |
| K51 | 46750 | 9 | 2600 | 1 | 2550 |
| K53 | 52364 | 11 | 2808 | 1 | 2756 |
| K55 | 58410 | 12 | 3024 | 1 | 2970 |
| K57 | 64904 | 13 | 3248 | 1 | 3192 |
| K59 | 71862 | 15 | 3480 | 1 | 3422 |
| K61 | 79300 | 17 | 3720 | 1 | 3660 |
Таблица 3.Длина и время обходов полных графов.
Отметим тот факт, что обходчик ndfsm проходит на (N-1) дуг больше, чем нужно по минимуму для обхода полного графа KN.
Оценка длины обхода графа KM(KN) снизу тоже равна количеству его дуг
E(KM(KN)) = M × E(KN) + E(KM) = M × N × (N - 1) + M × (M - 1).
| K3(K51) | 140264 | 29 | 7810 | 2 | 7656 |
| K5(K51) | 233810 | 53 | 13028 | 3 | 12770 |
| K7(K51) | 327404 | 80 | 18254 | 5 | 17892 |
| K3(K53) | 157106 | 35 | 8434 | 2 | 8264 |
| K5(K53) | 261880 | 60 | 14068 | 4 | 13800 |
| K7(K53) | 366702 | 94 | 19710 | 6 | 19334 |
| K3(K55) | 175244 | 40 | 9082 | 2 | 8916 |
| K5(K55) | 292110 | 71 | 15148 | 4 | 14870 |
| K7(K55) | 409024 | 108 | 21222 | 6 | 20832 |
Таблица 4. Длина и время обходов графов KM(KN).
Отметим, что длина обхода этих графов с помощью dfsm может быть вычислена по той же формуле, что и количество дуг: если D(G) обозначает длину обхода графа G с помощью dfsm, то
D(KM(KN))=M × D(KN) + D(KM). Можно предположить, что при обходе графа, состоящего из нескольких слабо связанных (при помощи одной-двух дуг) частей, длина его обхода получается сложением длин обходов частей и количества проходов по связывающим дугам. Оценка длины обхода графа KM KN снизу также равна количеству его дуг
E(KM × KN) = M × E(KN) + N × E(KM) = M × N × (N + M - 2).
| K3× K51 | 269265 | 62 | 8108 | 1 | 7956 |
| K5× K51 | 804614 | 186 | 14024 | 5 | 13770 |
| K7× K51 | 1694413 | 406 | 20348 | 5 | 19992 |
| K3× K53 | 301095 | 68 | 8744 | 2 | 8576 |
| K5× K53 | 898884 | 216 | 15104 | 4 | 14840 |
| K7× K53 | 1890675 | 302 | 21888 | 5 | 21520 |
| K3× K55 | 335337 | 50 | 9404 | 2 | 9240 |
| K5× K55 | 1000234 | 164 | 16224 | 3 | 15950 |
| K7× K55 | 2101501 | 365 | 23484 | 5 | 23100 |
