Регуляризуемый граф

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

[math]\displaystyle{ G_0=G,G_1,\ldots,G_l, }[/math]

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

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

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

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

См. также Аранжируемый граф, Запрещенный подграф, Каркас уграфа Одновходовый граф, Разборный граф, Сводимый управляющий граф.

Литература

[Касьянов/88],

[Евстигнеев-Касьянов/94],

[Касьянов/86]