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

Перейти к навигации Перейти к поиску
нет описания правки
(Создана новая страница размером '''Регуляризуемый граф''' (''Regularizable graph'') - ''уграф'' <math>G</math>, для которого сущес...)
 
Нет описания правки
Строка 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]]


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


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


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

Навигация