Регуляризуемый граф: различия между версиями
Glk (обсуждение | вклад) (Создана новая страница размером '''Регуляризуемый граф''' (''Regularizable graph'') - ''уграф'' <math>G</math>, для которого сущес...) |
KVN (обсуждение | вклад) |
||
(не показаны 3 промежуточные версии 1 участника) | |||
Строка 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>\,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>\,G</math> имеет единственный [[каркас]].'' | ||
Большинство современных языков высокого уровня являются | Большинство современных языков высокого уровня являются | ||
Строка 21: | Строка 23: | ||
Фортран-программ показывают, что <math>90\%</math> уграфов регуляризуемы, | Фортран-программ показывают, что <math>90\%</math> уграфов регуляризуемы, | ||
причем в среднем зоны занимают небольшую часть программы | причем в среднем зоны занимают небольшую часть программы | ||
(около <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>\,G,</math> <math>\,m(p)</math> — количество различных ''многовходовых зон'' | ||
уграфа <math>G</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> | ||
Поэтому в реальных случаях даже для языков "неструктурного" | Поэтому в реальных случаях даже для языков "неструктурного" | ||
программирования, как правило, уграф регуляризуем, а если | программирования, как правило, уграф регуляризуем, а если | ||
Строка 37: | Строка 39: | ||
сохранении времени счета по программе. | сохранении времени счета по программе. | ||
Другое название | Другое название — ''[[Обобщенно-сводимый уграф]], [[Регуляризуемый уграф]].'' | ||
См. также ''Аранжируемый граф, Запрещенный подграф, Каркас уграфа Одновходовый граф, Разборный граф, Сводимый управляющий граф.'' | ==См. также== | ||
* ''[[Аранжируемый граф]],'' | |||
* ''[[Запрещенный подграф]],'' | |||
* ''[[Каркас уграфа]],'' | |||
* ''[[Одновходовый граф]],'' | |||
* ''[[Разборный граф]],'' | |||
* ''[[Сводимый управляющий граф]].'' | |||
==Литература== | ==Литература== | ||
* Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука. Сиб. отд-ние, 1994. | |||
* Касьянов В.Н. Теоретико-графовые задачи анализа управляющих графов транслируемых программ // Исследования по прикладной теории графов. — Новосибирск: Наука. Сиб. отд-ние, 1986. | |||
* Касьянов В.Н. Оптимизирующие преобразования программ. — М.: Наука, 1988. | |||
* Касьянов В.Н., Евстигнеев В.А. Графы в программировании: обработка, визуализация и применение. — СПб.: БХВ-Петербург, 2003. | |||
[ | [[Категория: Сводимые и регуляризуемые графы]] |
Текущая версия от 11:51, 4 сентября 2019
Регуляризуемый граф (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] Поэтому в реальных случаях даже для языков "неструктурного" программирования, как правило, уграф регуляризуем, а если нет, то его преобразование для получения регуляризуемости не потребует даже двукратного увеличения его размера при сохранении времени счета по программе.
Другое название — Обобщенно-сводимый уграф, Регуляризуемый уграф.
См. также
- Аранжируемый граф,
- Запрещенный подграф,
- Каркас уграфа,
- Одновходовый граф,
- Разборный граф,
- Сводимый управляющий граф.
Литература
- Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука. Сиб. отд-ние, 1994.
- Касьянов В.Н. Теоретико-графовые задачи анализа управляющих графов транслируемых программ // Исследования по прикладной теории графов. — Новосибирск: Наука. Сиб. отд-ние, 1986.
- Касьянов В.Н. Оптимизирующие преобразования программ. — М.: Наука, 1988.
- Касьянов В.Н., Евстигнеев В.А. Графы в программировании: обработка, визуализация и применение. — СПб.: БХВ-Петербург, 2003.