Регуляризуемый граф: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
Строка 1: Строка 1:
'''Регуляризуемый граф''' (''[[Regularizable graph]]'') -
'''Регуляризуемый граф''' (''[[Regularizable graph]]'')
''[[уграф]]'' <math>G</math>, для которого существует такая
''[[уграф]]'' <math>\,G</math>, для которого существует такая
последовательность уграфов
последовательность уграфов


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


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


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


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


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


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


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


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

Версия от 12:23, 25 мая 2011

Регуляризуемый граф (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] относительно некоторого множества попарно непересекающихся интервалов.

Regularizable graph.png

Справедлива теорема Касьянова—Хехта—Ульмана о том, что уграф регуляризуем тогда и только тогда, когда выполняется любое из следующих свойств: [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] Поэтому в реальных случаях даже для языков "неструктурного" программирования, как правило, уграф регуляризуем, а если нет, то его преобразование для получения регуляризуемости не потребует даже двукратного увеличения его размера при сохранении времени счета по программе.

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

См. также

Литература

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