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

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

 

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

(2) Каркас любого ''[[аранжируемый граф|аранжируемого уграфа]]'' <math>G</math> может быть получен из <math>G</math> удалением всех ''дуг назад''.

(3) Уграф <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>.