1303
правки
Регуляризуемый уграф: различия между версиями
Перейти к навигации
Перейти к поиску
нет описания правки
KVN (обсуждение | вклад) |
KVN (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Регуляризуемый уграф''' ('' | '''Регуляризуемый уграф''' (''Regularizable cf-graph, Regularizable control flow graph'') — | ||
''[[уграф]]'' <math>\,G</math>, для которого существует такая | ''[[уграф]]'' <math>\,G</math>, для которого существует такая | ||
последовательность уграфов | последовательность уграфов | ||
| Строка 13: | Строка 13: | ||
Справедлива | Справедлива | ||
теорема Касьянова—Хехта—Ульмана о том, что | '''''теорема Касьянова—Хехта—Ульмана''''' (''Kasyanov-Hecht-Ullman'') о том, что | ||
''уграф регуляризуем тогда и только тогда, когда выполняется любое из следующих свойств: <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> имеет единственный [[каркас]].'' | ||
| Строка 27: | Строка 27: | ||
такой регуляризуемый уграф, в котором имеется не более чем | такой регуляризуемый уграф, в котором имеется не более чем | ||
<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> вершин и | ||