Реклама:

Исследованные графы характеризуются двумя функциональными зависимостями числа маршрутов от числа вершин ветвления (рис. 2.4). При выделении маршрутов по первому критерию в графе Г8 число маршрутов не зависит от числа вершин и определяется повторяющейся структурой между узлами.. В результате в графе Г3 выделяется только два маршрута. В графах Г\ и Г2 при выделении маршрутов по критерию Хі их число линейно возрастает при увеличении числа вершин.

При выделении маршрутов по второму критерию их число пропорционально полному числу вершин для всех типов графов. Если в графах учитывать только те вершины, в которых происходит .ветвление лв, то нХ число с точностью до единицы равно цикломатнческому числу 2 или полному числу маршрутов М:^ *

г~У—пв+2 = 2пв—пв+1=пв+1- (26)

Следовательно, все зависимости числа маршрутов от числа вершины ветвления при критерии х« совпадают. Кроме того, для графов Гх н Г? числа маршрутов совпадают, при всех трех критериях Хі. Х« и х» н равны М = лв + 1. В графах Г3 н Г3 полное число вершии, кроме вершии с ветвлением, включает единственную конечную вершину, в результате чего число маршрутов точно равно полному числу вершин. В бинарном дереве І\, в нижней половине графа нершнны не содержат ветвления и число таких вершин равно половине от общего числа. Поэтому число маршрутов в таком графе вдвое меньше полного числа вершин.

Следует отметить, что в узких графех Га число маршрутов, выделяемых по первому и нторому критериям, различается на величину, пропорциональную числу вершин (п„ — I). Число маршрутов в реальных ациклических программах (точки на рис. 2.4) при критерии %а точно соответствует цикломатнческому числу, а при критерии Хі .близко к нему. Таким' образом, при инженерных о це и-к а х числа тестируемых маршрутов целесообразно использовать выражение (2.6). Число мршрутов при их выделении по критерию Хэ в графе Г, и Г2 не изменяется, а в графе Г3 возраствет в зависимости от числа ве.ршнн значительно быстрее (2"в), чем цикломатическое число: Величину 2 в можно использовать для оценки максимального' числа маршрутов в наиболее сложных ациклических- программах.

Структурная Сложность. £ графов изменяется в более широком диапазоне, чем число маршрутов, что определило выбор логарифмического масштаба по оси ординат иа рнс. 2.5. Наименьшей структурной сложностью характеризуется граф Г3 при выделении маршрутов по первому критерию. Для таких графов структурная сложность возрастает линейно в зависимости от' числа вершии. При выделении маршрутов по второму критерию граф Г8 характеризуется' ваибольшей структурной сложностью. При 32 н более вершинах структурная сложность графа Г3 почти на порядок выше, чем графа 1\ при том же числе вершии. Относительная разница сложности этих графов при критерии х* при-' близительво сохраняется при изменении числа вершин от 16 до 128.

Такое распределение значений структурной сложности от тнлон графов обусловлено различием их ширины. Так как при критерии х* .число маршрутов в 'зависимости от пв во всех графах изменяется- одинаково, то различия структурной сложности определяются числом условий, анализируемых в каждом маршруте. Во всех маршрутах графа Га участвуют все его вершины, поэтому он имеет наибольшую структурную сложность среди рассматриваемых графов.


⇐ Предыдущая страница| |Следующая страница ⇒