Аноним

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

Материал из WikiGrapp

Регуляризуемый граф (посмотреть исходный код)

Версия от 11:45, 4 сентября 2019

1373 байта добавлено ,  4 сентября 2019
→‎Литература
(Создана новая страница размером '''Регуляризуемый граф''' (''Regularizable graph'') - ''уграф'' <math>G</math>, для которого сущес...)
 
 
(не показаны 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>i>0</math>, является ''фактор-уграфом'' уграфа <math>G_{i-1}</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> — [[сводимый уграф|сводим]], <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>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>
Поэтому в реальных случаях даже для языков "неструктурного"
Поэтому в реальных случаях даже для языков "неструктурного"
программирования, как правило, уграф регуляризуем, а если
программирования, как правило, уграф регуляризуем, а если
Строка 37: Строка 39:
сохранении времени счета по программе.
сохранении времени счета по программе.


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


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


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


[Касьянов/86]
[[Категория: Сводимые и регуляризуемые графы]]
Источник — http://pco.iis.nsk.su/grapp/index.php/Служебная:Сравнение_версий/4400...10852