Каркас уграфа: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''Каркас уграфа''' (''DAG of control flow graph'') - такой ''уграф'' <math>K</math>, что <math>K</math> --- ''...)
 
 
(не показаны 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> --- ''ациклический остов'' уграфа <math>G</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>.
==Литература==
==Литература==
[Касьянов/88],
* Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука. Сиб. отд-ние, 1994.
* Касьянов В.Н. Оптимизирующие преобразования программ. — М.: Наука, 1988.
* Касьянов В.Н., Евстигнеев В.А. Графы в программировании: обработка, визуализация и применение. — СПб.: БХВ-Петербург, 2003.
 


[Евстигнеев-Касьянов/94]
[[Категория: Сводимые и регуляризуемые графы]]

Текущая версия от 11:52, 4 сентября 2019

Каркас уграфа (DAG of control flow graph) — такой уграф [math]\displaystyle{ K }[/math], что [math]\displaystyle{ K }[/math]ациклический остов уграфа [math]\displaystyle{ G }[/math], каркасом которого он является, и добавление в [math]\displaystyle{ K }[/math] еще одной любой дуги [math]\displaystyle{ G }[/math] нарушает ацикличность [math]\displaystyle{ K }[/math].

DAG of control flow graph.png

Справедливы следующие свойства:

(1) Для любого простого пути [math]\displaystyle{ P }[/math] по [math]\displaystyle{ G }[/math] от ее начальной вершины [math]\displaystyle{ p_0 }[/math] существует такой каркас [math]\displaystyle{ K }[/math] уграфа [math]\displaystyle{ G }[/math], что [math]\displaystyle{ P }[/math] является путем по [math]\displaystyle{ K }[/math].

(2) Каркас любого аранжируемого уграфа [math]\displaystyle{ G }[/math] может быть получен из [math]\displaystyle{ G }[/math] удалением всех дуг назад.

(3) Уграф [math]\displaystyle{ G }[/math] является регуляризуемым тогда и только тогда, когда имеет единственный каркас.

(4) Уграф [math]\displaystyle{ G }[/math] является регуляризуемым тогда и только тогда, когда существует такое разбиение множества его дуг [math]\displaystyle{ U }[/math] на два подмножества [math]\displaystyle{ U_1 }[/math] и [math]\displaystyle{ U_2 }[/math], что [math]\displaystyle{ U_1 }[/math] образует каркас уграфа, а для любой дуги [math]\displaystyle{ (p, q)\in U_2 }[/math] вершина [math]\displaystyle{ q }[/math] обязательно предшествует вершине [math]\displaystyle{ p }[/math] в [math]\displaystyle{ G }[/math].

Литература

  • Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука. Сиб. отд-ние, 1994.
  • Касьянов В.Н. Оптимизирующие преобразования программ. — М.: Наука, 1988.
  • Касьянов В.Н., Евстигнеев В.А. Графы в программировании: обработка, визуализация и применение. — СПб.: БХВ-Петербург, 2003.