Тестирование софта - статьи


Обход полного графа и его модификаций


В данном разделе будут рассмотрены экспериментальные данные по построению обхода для следующих видов графов.

  • Полный ориентированный граф с N вершинами, обозначаемый KN.

  • Граф KM(KN), представляющий собой соединенные с помощью KM M полных графов KN. Вершины этих M графов пронумерованы числами от 0 до (N-1) и все вершины с номером 0 соединены между собой полным графом.

  • Граф KM KN, являющийся декартовым произведением полных графов. Он тоже представляется как M графов KN с пронумерованными вершинами, в которых всем вершинам с одинаковыми номерами соединены друг с другом.

В следующих таблицах приведены длины и время (в секундах) построения обхода разными обходчиками для таких графов.

Числа N и M выбраны нечетными, потому что для полного графа с нечетным количеством вершин существует эйлеров цикл.

Теоретическая оценка длины обхода KN снизу равна количеству его дуг E(KN)=N × (N - 1).

Граф dfsm, длинаdfsm, времяndfsm, длинаndfsm, времямин. длина
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).

Графdfsm, длинаdfsm, времяndfsm, длинаndfsm, времямин. длина
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, то



Начало  Назад  Вперед



Книжный магазин