683
правки
Glk (обсуждение | вклад) (Создана новая страница размером '''Каркас уграфа''' (''DAG of control flow graph'') - такой ''уграф'' <math>K</math>, что <math>K</math> --- ''...) |
KVN (обсуждение | вклад) Нет описания правки |
||
(не показаны 3 промежуточные версии 1 участника) | |||
Строка 1: | Строка 1: | ||
'''Каркас уграфа''' (''DAG of control flow graph'') | '''Каркас уграфа''' (''[[Dag of control flow graph|DAG of control flow graph]]'') — такой ''[[уграф]]'' <math>K</math>, что <math>K</math> — ''ациклический [[остов]]'' уграфа <math>G</math>, [[каркас|каркасом]] которого он является, и добавление в <math>K</math> еще одной любой [[дуга|дуги]] <math>G</math> нарушает ацикличность <math>K</math>. | ||
такой ''уграф'' <math>K</math>, что <math>K</math> | |||
каркасом которого он является, и добавление | [[Файл:DAG of control flow graph.png|700px]] | ||
в <math>K</math> еще одной любой дуги <math>G</math> нарушает ацикличность <math>K</math>. | |||
Справедливы следующие свойства: | Справедливы следующие свойства: | ||
(1) Для любого ''простого пути'' <math>P</math> по <math>G</math> от ее ''начальной вершины'' | (1) Для любого ''[[простой путь|простого пути]]'' <math>P</math> по <math>G</math> от ее ''[[начальная вершина|начальной вершины]]'' <math>p_0</math> существует такой каркас <math>K</math> уграфа <math>G</math>, что <math>P</math> является [[путь|путем]] по <math>K</math>. | ||
<math>p_0</math> существует такой каркас <math>K</math> уграфа <math>G</math>, что <math>P</math> | |||
является путем по <math>K</math>. | |||
(2) Каркас любого ''аранжируемого уграфа'' <math>G</math> может быть получен из | (2) Каркас любого ''[[аранжируемый граф|аранжируемого уграфа]]'' <math>G</math> может быть получен из <math>G</math> удалением всех ''дуг назад''. | ||
<math>G</math> удалением всех ''дуг назад''. | |||
(3) Уграф <math>G</math> является ''регуляризуемым'' тогда и только тогда, | (3) Уграф <math>G</math> является ''[[регуляризуемый граф|регуляризуемым]]'' тогда и только тогда, | ||
когда имеет единственный каркас. | когда имеет единственный каркас. | ||
(4) Уграф <math>G</math> является регуляризуемым тогда и только тогда, | (4) Уграф <math>G</math> является регуляризуемым тогда и только тогда, когда существует такое разбиение множества его дуг <math>U</math> на два подмножества <math>U_1</math> и <math>U_2</math>, что <math>U_1</math> образует каркас уграфа, а для любой дуги <math>(p, q)\in U_2</math> [[вершина]] <math>q</math> ''обязательно предшествует'' вершине <math>p</math> в <math>G</math>. | ||
когда существует такое разбиение множества его дуг <math>U</math> на | |||
два подмножества <math>U_1</math> и <math>U_2</math>, что <math>U_1</math> образует каркас | |||
уграфа, а для любой дуги <math>(p, q)\in U_2</math> вершина <math>q</math> | |||
''обязательно предшествует'' вершине <math>p</math> в <math>G</math>. | |||
==Литература== | ==Литература== | ||
* Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука. Сиб. отд-ние, 1994. | |||
* Касьянов В.Н. Оптимизирующие преобразования программ. — М.: Наука, 1988. | |||
* Касьянов В.Н., Евстигнеев В.А. Графы в программировании: обработка, визуализация и применение. — СПб.: БХВ-Петербург, 2003. | |||
[ | [[Категория: Сводимые и регуляризуемые графы]] |