Конечное дерево
Cтраница 1
Любое непустое конечное дерево имеет хотя бы две концевые вершины и хотя бы одно концевое ребро. [1]
Теорема 4.1.2. Любое нетривиальное конечное дерево имеет хотя бы две концевые вершины и хотя бы одно концевое ребро. [2]
Итак, любое заданное конечное дерево V может быть продолжено как в дерево с конечным, но сколь угодно большим весом, так и в дерево с бесконечным весом. Таким образом, становится ясным, что для содержательности дальнейших рассмотрений нужно исходить из некоторой верхней оценки для. [3]
Понятие веса конечного дерева позволяет сформулировать тривиальную оценку для веса любого продолжения данного конечного дерева V высоты h п, в частности, для веса ограниченно-детерминированного оператора, совпадающего с V на нижних h ярусах. Для этого достаточно заметить, что К вершин базиса SS дерева V останутся попарно различимыми и при любом его продолжении. Следовательно, если вес V равен К, то вес любого продолжения будет не меньше К. [4]
Пусть заданы: конечное дерево V и натуральное число К. [5]
Следует отметить, что получение конечного дерева развертки для алгоритма функционирования блока не всегда возможно или требует прохождения большого числа ветвей дерева. В этих случаях на практике можно отсекать не только пути с тождественно ложными условиями реализуемости, но и часть реализуемых путей ( например, разворачивать циклы не более одного раза), получая тем самым систему примеров, степень полноты которых определяется степенью отсечения реализуемых путей. [6]
Ясно, что такая процедура завершается построением конечного дерева, так как все пути в результате будут состоять только из узлов блок-схемы. [7]
Правило ветвления ставит в соответствие области R некоторое конечное дерево подмножеств. Конечность дерева подмножеств следует из конечности пространства X. [8]
Понятие веса конечного дерева позволяет сформулировать тривиальную оценку для веса любого продолжения данного конечного дерева V высоты h п, в частности, для веса ограниченно-детерминированного оператора, совпадающего с V на нижних h ярусах. Для этого достаточно заметить, что К вершин базиса SS дерева V останутся попарно различимыми и при любом его продолжении. Следовательно, если вес V равен К, то вес любого продолжения будет не меньше К. [9]
Алгоритм расстановки меток ( label setting) всегда выбирает ребро, которое гарантированно является частью конечного дерева кратчайших путей. Он работает аналогично алгоритму построения минимального остовного дерева. Если ребро было добавлено кдереву, оно уже не будет удалено. [10]
Алгоритм коррекции меток ( label correcting) добавляет ребра, которые могут быть, а могут и не быть частью конечного дерева кратчайших путей. В процессе выполнения алгоритм может определить, что вместо уже имеющегося ребра в дерево должно быть добавлено другое. В этом случае алгоритм заменяет старое ребро новым и продолжает работу. Замена ребра в дереве может открыть дополнительные пути. Чтобы проверить их, алгоритму приходится повторно исследовать пути, которые были добавлены к дереву раньше и использовали удаленное ребро. [11]
Эффективно построить каноническую таблицу ( или каноническую диаграмму) оператора, имеющего вес, не превышающий К, для которого V является начальным конечным деревом. [12]
Мы не приводим формального доказательства того, что каноническая таблица, составленная согласно пунктам 1 - 3, действительно задает оператор, продолжающий заданное конечное дерево. Дополнительно отметим следующий просто проверяемый факт: всякий ограниченно-7. V веса К, может быть получен указанным путем. [13]
Указанные четыре дерева образуют монотонный переход от TI к Г4 в том смысле, что каждое последующее дерево имеет на единицу большез число общих ребер с конечным деревом. [14]
 |
Поиск в глубину с возвратом в полном дереве поиска. [15] |
Страницы: 1 2