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

'''Регуляризуемый граф''' (''[[Regularizable graph]]'') -

''[[уграф]]'' <math>G</math>, для которого существует такая

что <math>G_l</math> --- ''[[тривиальный граф|тривиальный]]'' уграф, а каждый

<math>G_i</math>, <math>i>0</math>, является ''[[фактор-уграф|фактор-уграфом]]'' уграфа <math>G_{i-1}</math>

теорема Касьянова---Хехта---Ульмана о том, что  

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

эквивалентными дублированиями преобразует любой уграф <math>G</math> в

<math>2^{\min(m(p),k(p))}</math> экземпляров любой [[вершина|вершины]] <math>p</math> уграфа

<math>G</math>, <math>m(p)</math> --- количество различных ''многовходовых зон''

уграфа <math>G</math>, содержащих <math>p</math>, а <math>k(p)</math> --- минимальное такое

число, что имеется множество, состоящее из <math>k(p)</math> вершин и

многовходовых зон уграфа <math>G</math>, которые целиком лежат в

максимальной многовходовой зоне, содержащей вершину <math>p</math>.

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

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

[Касьянов/88],

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

[Касьянов/86]