Можно предположить, что при обходе

D(KM(KN))=M × D(KN) + D(KM). Можно предположить, что при обходе графа, состоящего из нескольких слабо связанных (при помощи одной-двух дуг) частей, длина его обхода получается сложением длин обходов частей и количества проходов по связывающим дугам. Оценка длины обхода графа KM KN снизу также равна количеству его дуг
E(KM × KN) = M × E(KN) + N × E(KM) = M × N × (N + M - 2).

Графdfsm, длинаdfsm, времяndfsm, длинаndfsm, времямин. длина

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

Таблица 5. Длина и время обходов графов KM KN. Теперь длина обхода с помощью dfsm уже не может быть определена с помощью аналогичной формулы. Приведенные таблицы показывают, что на многих графах обходчик ndfsm работает эффективнее dfsm, и, если проверка детерминизма графа не является необходимым элементом тестирования, предпочтительнее использовать первый обходчик. Можно заметить, что при увеличении количества дуг длина обхода с помощью dfsm составляет порядка 50% от произведения количества дуг на количество состояний, что означает практическую невозможность использования dfsm-обходчика в случае насыщенных графов с сотнями состояний.

Содержание Назад Вперед