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