Разработка компиляторов
Простейшие свойства
Граф называется сводимым тогда и только тогда, когда множество обратных дуг совпадает с множеством обратных дуг относительно глубинного остовного дерева для любого такого дерева.
Простейшие свойства нумераций Pre и Post:
- если вершина v обязательно предшествует вершине w , то Pre(v)<Pre(w), Post(v)<Post(w)
- прямые в смысле нумерации Pre дуги являются прямыми или деревянными относительно дерева
- обратные в смысле нумерации Pre дуги являются обратными или поперечными относительно дерева
- обратные в смысле нумерации Post дуги являются обратными в смысле дерева; остальные дуги являются прямыми относительно нумерации Post
- если Pre(v)>Pre(w) , то произвольный путь в графе от v до w содержит общего предка v и w в дереве
- граф сводим тогда и только тогда, когда отношение обязательного предшествования в нем и его каркасе совпадают
Сводимость является одной из основных характеристик графов потока управления. Как видно из определения, в сводимом графе обратные дуги для произвольного остовного дерева совпадают с обратными дугами относительно обязательного предшествования. Учитывая, что каждая обратная дуга определяет в графе потока управления контур (т.е. является абстракцией циклических конструкций языков программирования), циклическая структура сводимого графа является более регулярной, что упрощает анализ его свойств.
