Просмотр кода страницы Регуляризуемый уграф

'''Регуляризуемый уграф''' (''[[Regularizable graph]]'') — 
''[[уграф]]'' <math>\,G</math>, для которого существует такая
последовательность уграфов

::::::::<math>G_0=G,G_1,\ldots,G_l,</math> 

что <math>\,G_l</math> — ''[[тривиальный граф|тривиальный]]'' уграф, а каждый
<math>\,G_i,</math> <math>\,i>0,</math> является ''[[фактор-уграф|фактор-уграфом]]'' уграфа <math>\,G_{i-1}</math>
относительно некоторого множества попарно непересекающихся
''[[интервал|интервалов]]''.

[[Файл:Regularizable graph.png|700px]]

Справедлива
теорема Касьянова—Хехта—Ульмана о том, что 
''уграф регуляризуем тогда и только тогда, когда выполняется любое из следующих свойств: <math>\,G</math> — [[сводимый уграф|сводим]], <math>\,G</math> — [[аранжируемый граф|аранжируем]], <math>\,G</math> — [[разборный граф|разборный]], <math>\,G</math> — [[одновходовый граф|одновходовый]], <math>\,G</math> не содержит [[запрещенный подграф|запрещенного подграфа]], <math>\,G</math> имеет единственный [[каркас]].''

Большинство современных языков высокого уровня являются
языками структурного программирования и, таким образом,
ориентированными на написание регуляризуемых программ. Что
касается других языков, основным из которых является
Фортран, то исследования характеристик реальных
Фортран-программ показывают, что <math>90\%</math> уграфов регуляризуемы,
причем в среднем зоны занимают небольшую часть программы
(около <math>4\%</math>). С другой стороны, существует [[алгоритм]], который
эквивалентными дублированиями преобразует любой уграф <math>\,G</math> в
такой регуляризуемый уграф, в котором имеется не более чем
<math>\,2^{\min(m(p),k(p))}</math> экземпляров любой [[вершина|вершины]] <math>\,p</math> уграфа
<math>\,G,</math> <math>\,m(p)</math> — количество различных ''многовходовых зон''
уграфа <math>\,G,</math> содержащих <math>\,p,</math> а <math>\,k(p)</math> — минимальное такое
число, что имеется множество, состоящее из <math>\,k(p)</math> вершин и
включающее хотя бы по одной вершине каждой из тех
многовходовых зон уграфа <math>\,G,</math> которые целиком лежат в
максимальной многовходовой зоне, содержащей вершину <math>\,p.</math>
Поэтому в реальных случаях даже для языков "неструктурного"
программирования, как правило, уграф регуляризуем, а если
нет, то его преобразование для получения регуляризуемости не
потребует даже двукратного увеличения его размера при
сохранении времени счета по программе.

Другое название — ''[[Обобщенно-сводимый уграф]].''

==См. также== 
* ''[[Аранжируемый граф]],''
* ''[[Запрещенный подграф]],''
* ''[[Каркас уграфа]],''
* ''[[Одновходовый граф]],''
* ''[[Разборный граф]],''
* ''[[Сводимый управляющий граф]].''
==Литература==
* Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука. Сиб. отд-ние, 1994.

* Касьянов В.Н. Теоретико-графовые задачи анализа управляющих графов транслируемых программ // Исследования по прикладной теории графов. — Новосибирск: Наука. Сиб. отд-ние, 1986.

* Касьянов В.Н. Оптимизирующие преобразования программ. — М.: Наука, 1988.