4635
правок
Циклический участок: различия между версиями
Материал из WikiGrapp
нет описания правки
Glk (обсуждение | вклад) (Создана новая страница размером '''Циклический участок''' (''Loop region'') - конструкция, позволяющая на основе анал...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Циклический участок''' (''Loop region'') - | '''Циклический участок''' (''[[Loop region]]'') - | ||
конструкция, позволяющая на основе анализа ''уграфа'' с | конструкция, позволяющая на основе анализа ''[[уграф|уграфа]]'' с | ||
<math>n</math> вершинами и <math>m</math> дугами за время <math>O(nm)</math> выявлять | <math>n</math> [[вершина|вершинами]] и <math>m</math> [[дуга|дугами]] за время <math>O(nm)</math> выявлять циклическую структуру [[алгоритм|алгоритма]] и находить отношения частот | ||
циклическую структуру алгоритма и находить отношения частот | |||
выполнения между всеми подмножествами его элементов, которые | выполнения между всеми подмножествами его элементов, которые | ||
не противоречат ''достоверным отношениям частот выполнения'', если уграф <math>G</math> алгоритма является ''регуляризуемым''. | не противоречат ''достоверным отношениям частот выполнения'', если уграф <math>G</math> алгоритма является ''[[регуляризуемый граф|регуляризуемым]]''. | ||
Пусть <math>G_0=G, G_1, \ldots, G_r</math> | Пусть <math>G_0=G, G_1, \ldots, G_r</math> - такая последовательность | ||
уграфов, в которой только <math>G_r</math> не содержит нетривиальных | уграфов, в которой только <math>G_r</math> не содержит нетривиальных | ||
''бикомпонент'', и для любого <math>i</math> уграф <math>G_i</math> получается | ''[[бикомпонента|бикомпонент]]'', и для любого <math>i</math> уграф <math>G_i</math> получается | ||
из <math>G_{i-1}</math> удалением в каждой нетривиальной бикомпоненте | из <math>G_{i-1}</math> удалением в каждой нетривиальной бикомпоненте | ||
<math>C</math> уграфа <math>G_{i-1}</math> всех дуг, заходящих в один из ее | <math>C</math> уграфа <math>G_{i-1}</math> всех дуг, заходящих в один из ее | ||
''входов''. Эту ''входную вершину'' бикомпоненты <math>C</math> называют | ''[[вход|входов]]''. Эту ''[[входная вершина подграфа|входную вершину]]'' бикомпоненты <math>C</math> называют ее ''[[голова|головой]]'', а удаленные дуги - ''[[дуга повторения уровня i|дугами повторения уровня <math>i</math>]]''. | ||
ее ''головой'', а удаленные дуги | |||
Пусть <math>I_i</math> обозначает множество | Пусть <math>I_i</math> обозначает множество | ||
всех дуг повторения уровня <math>i</math>. | всех дуг повторения уровня <math>i</math>. | ||
Части схемы <math>G</math>, называемые ее | Части схемы <math>G</math>, называемые ее | ||
''' | '''циклическими участками''', | ||
определяются по следующим двум правилам: | определяются по следующим двум правилам: | ||
1) ''' | 1) '''Циклический участок''' нулевого уровня в уграфе <math>G</math> один; он состоит | ||
из всех тех вершин и дуг, которые принадлежат путям по <math>G_r</math> | из всех тех вершин и дуг, которые принадлежат [[путь|путям]] по <math>G_r</math> | ||
от <math>p_0</math> к <math>q_0</math>, и имеет ''головой'' вершину <math>p_0</math>; | от <math>p_0</math> к <math>q_0</math>, и имеет ''головой'' вершину <math>p_0</math>; | ||
2) пусть для некоторого <math>i</math>, <math>i>0</math>, <math>C</math> | 2) пусть для некоторого <math>i</math>, <math>i>0</math>, <math>C</math> - бикомпонента схемы | ||
<math>G_{i-1}</math> с головой <math>p</math>, тогда в <math>G</math> имеется циклический | <math>G_{i-1}</math> с головой <math>p</math>, тогда в <math>G</math> имеется циклический | ||
участок уровня <math>i</math> с головой <math>p</math>; он состоит из всех тех | участок уровня <math>i</math> с головой <math>p</math>; он состоит из всех тех | ||
| Строка 29: | Строка 27: | ||
из <math>C</math> удалением всех дуг повторения уровня <math>j>i</math>. | из <math>C</math> удалением всех дуг повторения уровня <math>j>i</math>. | ||
См. также ''Участок повторяемости.'' | ==См. также == | ||
''[[Участок повторяемости]].'' | |||
==Литература== | ==Литература== | ||
[Касьянов/88] | [Касьянов/88] | ||
